人工智能--贪婪算法（启发式搜索）

程序员文章站 2022-06-04 16:17:38

...

作者：沈聪

贪婪算法是启发式算法的代表算法之一，其核心思想是每次都选择局部最优解，但该算法并不能保证最后得出的结果是全局最优解。贪婪算法比较典型的案例就是最短路径搜索。之前，大部分的贪婪算法都是基于图的方式寻找最优路径。本篇文章主要借助路径动态规划的案例利用贪婪算法讲解树的最优路径。

相对于图来说，在树的搜索过程中，贪婪算法会遇到很多不可行解，这就需要程序能否返回到最近的一个节点，重新寻找其他的可行路径。下面通过一个示例说明贪婪最佳优先搜索和改进贪婪优化算法具体过程。

问题描述

下图展示了城市之间的路径图，该图包含了城市节点，城市之间的路径以及路径的大小。
人工智能--贪婪算法（启发式搜索）利用贪婪算法寻找节点1到节点19的路径。

贪婪算法和核心思路从节点1开始，每次都选择最短的路径，直到到达节点19，其路径显示图如下：
人工智能--贪婪算法（启发式搜索）

可以看出路径经历了3次死循环后，得出了最后的路径。

在贪婪算法的基础上，我们尝试的每次搜索N个节点，并把这N个节点的路径进行比较，这就是提出的改进贪婪算法。其思路从节点1开始，每次选择N个最短路径进行比较，然后选择N个叠加后的最短路径。以N=2为例，其选择路径为：

人工智能--贪婪算法（启发式搜索）
该算法在大型的图或树中，可提高搜索效率，但对于过大的N来说，其会导致搜索来回震荡。

MATLAB程序及仿真结果（贪婪算法）

function Best_Path = Greedy_search (Distance_Matrix, Begin_Point, End_Point)

% 该程序主要利用贪婪算法寻找两个节点之间的最小距离
% Distance_Matrix 的格式为：
% 节点  1    2    3    4    5.... 21
%  1    0    92   86   0    0  
%  2    92   0    0    83   0 ...
%  3    86   0    0    0    76
%  ...
%  21   0    0    0    0     0

% Distance_Matrix 主要描述了节点和节点之间的连接关系及距离
% Begin_Point 为起始的节点编号
% End_Point 为目标的节点编号
% History 显示了贪婪算法历经的路径
% Best_Path 显示了贪婪算法最后找出的最优结果

Dist_Matrix=Distance_Matrix;
History=[Begin_Point]; % 记录了当次的寻找路径
Next_Point = Begin_Point;

while Next_Point~=End_Point           
    Next_Point1 = Min_Find(Dist_Matrix(Next_Point,:)); % 找出当前节点下，最优的下一个节点
    Dist_Matrix = Trace_Find(Dist_Matrix,Next_Point, Next_Point1); % 更新搜索树，把已经寻找到的路径删除
Next_Point = Next_Point1;
    History=[History Next_Point];
    if isempty(Next_Point)
        % 倒回到一个节点，如果这个节点除了上游的节点，下游的节点，begin的节点外还有其他的一个节点想相连，则说明它可以作为另外一条路的起点
        History(end)=[];
        for i = length(History):-1:1 % 从最后一个节点开始寻找
            Point = History(i);
            % 判断这一行是否都为零，如果有不为零的，需要判断这个节点是否在History里面，如果在的也要去除该节点
            x = find(Dist_Matrix(Point,:)>0);
            if ~isempty(x)
                for ii = 1 : length(x)
                    Find_x = find(History==x(ii));
                    if ~isempty(Find_x) % 如果x不为空集，则说明这个节点连接了上游、下游、begin的节点之一，需要去除。
                        Dist_Matrix=Trace_Find(Dist_Matrix,Point, x(ii)); % 更新搜索树，把已经寻找到的路径删除
                    end
                end
            end
            % 去除在History里面的连接后，寻找新的路径
            x = find(Dist_Matrix(Point,:)>0);
            if ~isempty(x)
                Next_Point1 =Min_Find(Dist_Matrix(Point,:));
                Dist_Matrix = Trace_Find(Dist_Matrix,Point, Next_Point1); % 更新搜索树，把已经寻找到的路径删除
                Next_Point = Next_Point1;
                History=[History Next_Point];
                break;
            else % 如果该节点没有新的路径，寻找下一个节点的新的路径
                History(i)=[];
                continue;
            end
        end        
    end
end
Best_Path =History;

其结果为
人工智能--贪婪算法（启发式搜索）

function Min_Value_Index = Min_Find(Vector)
% 这个函数主要是寻找一个行向量的非零的最小值
Min_Value_Vector = find(Vector>0);
if ~isempty(Min_Value_Vector)
    Min_Value_Index = Min_Value_Vector(1);
    Min_Value = Vector(Min_Value_Index);
    for i = 1 : length(Vector)
        if Vector(i)>0
            if Min_Value > Vector(i)
                Min_Value = Vector(i);
                Min_Value_Index = i;
            end
        else
            continue;
        end
    end
else
    Min_Value_Index=[];
end

该程序的难点在于贪婪算法能搜索到很多不可行的路径，程序需要返回到原来的节点重新进行搜索。

改进贪婪算法（N-型贪婪算法），该程序的难点是遇到不可行解后，怎么退回找到原来的路径。这个算法对于大型的图或者树来说，能够提高搜索速度。但对于小的图来说，会引起算法的震荡。

程序为：

function Best_Path = Greedy_search_N_Step (Distance_Matrix, Begin_Point, End_Point,N)

Dist_Matrix=Distance_Matrix;
History=[Begin_Point]; % 记录了当次的寻找路径
Next_Point = Begin_Point;
while isempty(find(History==End_Point))
    [Min_Value_Index, Dist_Matrix] = Min_Find_N_step(Dist_Matrix, Next_Point,N,Begin_Point);
  if ~isempty(Min_Value_Index)
    Next_Point = Min_Value_Index(end);
  else
      Next_Point=[];
  end
  History=[History Min_Value_Index];
    if isempty(Next_Point)
        % 倒回到一个节点，如果这个节点除了上游的节点，下游的节点，begin的节点外还有其他的一个节点想相连，则说明它可以作为另外一条路的起点
        History(end)=[];
        for i = length(History):-1:1 % 从最后一个节点开始寻找
            Point = History(i);
            % 判断这一行是否都为零，如果有不为零的，需要判断这个节点是否在History里面，如果在的也要去除该节点
            x = find(Dist_Matrix(Point,:)>0);
            if ~isempty(x)
                for ii = 1 : length(x)
                    Find_x = find(History==x(ii));
                    if ~isempty(Find_x) % 如果x不为空集，则说明这个节点连接了上游、下游、begin的节点之一，需要去除。
                        Dist_Matrix=Trace_Find(Dist_Matrix,Point, x(ii)); % 更新搜索树，把已经寻找到的路径删除
                    end
                end
            end
            % 去除在History里面的连接后，寻找新的路径
            x = find(Dist_Matrix(Point,:)>0);
            if ~isempty(x)
                 [Min_Value_Index, Dist_Matrix] = Min_Find_N_step(Dist_Matrix, Point,N,Begin_Point);
                %Next_Point1 =Min_Find(Dist_Matrix(Point,:));
                %Dist_Matrix = Trace_Find(Dist_Matrix,Point, Next_Point1); % 更新搜索树，把已经寻找到的路径删除
                Next_Point = Min_Value_Index(end);
                History=[History Min_Value_Index];
                break;
            else % 如果该节点没有新的路径，寻找下一个节点的新的路径
                History(i)=[];
                continue;
            end
        end        
    end
end
Best_Path =History;