递归思维：最小生成树的 Prim 算法

一、什么是递归

​ 递归算法的定义是通过重复将问题分解为同类的子问题而解决问题的方法。定义略微抽象，可以简单理解为如果每次调用自身可以将问题简化一点点，并且它的最简单的形式是容易求解的，那么这个问题就可以通过有限次调用自身实现递归求解。这个思路非常类似数学归纳法。

1. 先看一个简单的例子：阶乘，即 ”给定一个正整数 N, 求出 1x2x...xN 的值”。

   假定读者对编程有一点了解，那么我们使用递归方式求解的做法如下：

   1 2 3 4 5 6

   int f(int n){ if(n==1) // 如果 n 为 1，返回 1 return 1; else // 如果 n 不为 1，返回 n 乘 f(n-1) return n*f(n-1); }

   例如 n 为 3，因为 3 不为 1，返回 3*f(2) ;

   此时 n 为 2，因为 2 不为 1，返回 2*f(1)，结合刚刚的 3 就是 3*2*f(1) ;

   此时 n 为 1，因为 1 等于 1，返回 1，综合以上得到最终结果 3*2*1=6 ;

   可能有人会认为使用循环来解决问题可以避免这样抽象的做法，但这只是一个方便理解的简单例子，在更多的时候，递归的算法可以简化问题，达到很好的效果，我相信读者在接下来两个例子中会不断有更加深入的体会。

2. 插入排序：将 N 个数据按从小到大的顺序排列起来，已知数据的移动成本可以忽略。

   这里仅说明思路：以现实中扑克牌排序为例，假设前 N-1 张牌已经排好了顺序，那么只需要将第 N 张放到正确的位置，那么第 N-1 张当然是在假定前N-2 张排好顺序的基础上放置的。以此类推，第 2 张是在第 1 张放好的前提下进行的。对于第 1 张，它自身就是已经排好顺序了。

 事实上现实中人们取扑克牌的时候一直在使用这种方法，尽管可能没有意识到。

二、最小生成树问题

​ 我们跳过图论中比较复杂的概念，给出一个实际问题，现在我们有一个数组保存有 N个点的位置坐标，如何将所有的点连接起来，要求所有线段的长度的和最小。以使用 MATLAB 生成的如图 200 个点为例。

​ 如果 N 比较小，你当然可以使用穷举法；但在 N 相对较大(事实上只需要稍微大一点点)的情况下，两点之间连接的可能非常多，穷举非常不现实的，如图可见一斑。

三、Prim 算法

​ 对于最小生成树问题，可能很多人的第一感觉是无从下手。考虑到我们平时做题时，遇到无法解决的问题，有一个很自然的想法是先试着解决一个更简单的问题，然后看怎么将简单问题的解法推广过来。那么，对于从如何这个 N 个点的最小生成树问题中找到一个更简单的问题呢？很自然的想法是将 N 减 1，考虑 N-1 个点的情形，这与刚刚我们使用递归的方法解决扑克牌插入排序问题的方式不谋而合。

​ 对的，假设前 k-1 个点已经正确连接，那么我们只需要将第 k 个点连接到这 k-1 个点中离它最近的那个点上。依次递推，对于第一个点，或者说，我们只需要先随便取出来一个点，然后进行刚刚提到的连接操作就可以了。这就是 Prim 算法。

以下给出一个 MATLAB 的简单实现，或许读者可以对它进行优化。

1
2
3
4
5
6
7

locaTopu=Prim(loca,locaA);
for i=1:length(locaTopu)
    plot([loca(locaTopu(i,1)),loca(locaTopu(i,2))],".-");
    hold on
end
title("Prim 算法得到的最小生成树")
hold off

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

function treeTopu =Prim(loca,locaA) % treeTopu需要连接的点的拓扑 loca位置向量 locaA距离矩阵
    constFAR=2;
    function [oldP,minP] = primNewP(treeYes,locaB) % oldP已有点位置 minP新连接点位置
        minP=NaN; % 最小点位置
        minDist=constFAR; % 最小点距离
        oldP=0;
        for i=treeYes
            if min(locaB(i,:)) < minDist
                if min(locaB(i,:))~=constFAR
                  [minDist,minP]=min(locaB(i,:));
                  oldP=i;
                end
            end
            %disp([minDist,minP])
        end
    end

    locaB=locaA;
    locaB(locaB==0)=constFAR;
    treeTopu=[]; % 最小生成树的拓扑：0不连接，1连接
    treeYes=1; % 已经在树中的
    treeNo=2:length(loca); % 待排的
    locaB(:,1)=constFAR;
    while(~isempty(treeNo))
        [oldP,newP]=primNewP(treeYes,locaB);
        treeTopu=[treeTopu;oldP,newP];
        locaB(:,newP)=constFAR; % 销毁已经使用过的最小值，以免重复
        treeYes=[treeYes,newP];
        treeNo(find(treeNo==newP,1))=[];
    end
end

最后可以得到结果如图

注：因为这里面包含了部分笔者的作业内容，为证明作业真实由笔者所做，已将笔者身份包含在了随机数种子中。转载还请注明出处，以免对笔者造成不必要的麻烦。