文章

第一次进行的边是权值最小的边，所以该解是最优解的其中之一。
假设前s个点满足要求，把连接这些点的边命名为$n_1,n_2\dots n_{s-1}$设未确定最小边相连的已确定节点是$n_k$。假设不是，那么，该未确定最小边一定和最小生成树构成回路，该回路某一边一定和$n_1,n_2\dots n_{s-1}$中的两点相交，其中一点是$n_k$，另一点设为$n_i$，该回路中比存在与$n_i$相邻的一条边比该未确定最小边大，用该未确定最小边代替这个比它大的这个边，结果仍然是生成树，该生成树比最小生成树还要小，这是矛盾的，因此，该未确定最小边一定是最优边。
综上，算法成立。

贪婪算法

叙述

初始最小生成树的边数为0，每次迭代都选择一条可行的边加入到树中。

将图中的所有边按从小到大排列。
图中的n个顶点应看作n棵树，从小到大进行选择，所选边连接的两点应属于不同的树，将这两条树合并为一棵树。
重复上一步，直到生成树有n-1条边或n个顶点。

证明

使用反证法进行可行性，最优性的证明。

假定第k步首次出现了错误，算法选了$E_1$，但实际上必须选另一条边$E_2$才能得到最小生成树$T_0$
$E_1$连接了两个连通分支，这两个连通分支在最终的$T_0$里是连通的，所以把$T_0$和$E_1$放在一起之后形成的图有一个环，在这个环里一定有k步或之后新选的边（如果没有的话仅凭前k-1条边和$E_1$不会构成环），依照$E_1$的定义，这个环里存在比$E_1$长的边，用$E_1$换掉这条边之后得到的树$T_1$比$T_0$更短，矛盾
综上，算法成立。

利用最小生成树的结果找旅行路径

邻域搜索的扩展

确定起点
把已经访问过的作为A，把未访问过的作为B。最开始A只有起点，B为所有其他点，寻找A与B的最短路径，并将这条边连接的点加入A中。
不断重复上述流程，直到A中有所有点。

贪婪算法的扩展

把所有边进行从小到大的排序。
把每个点按边的顺序依次添加，直到所有点都已经访问过。
找到其中的起点，从起点出发，输出结果。

利用最小生成树的结果找旅行路径

图顶点的深度优先搜索算法

确定顶点V，作为起始点，并标记为已经访问过。
搜索所有与V相邻的点，判断这些点是否被访问过。如果存在未被访问过的点，则任选一点进行访问；如果没有未被访问过的点，则回退到上一次访问的点。
不断重复上一步，直到所有点都被访问。

遗传算法找最短路径

遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。

生成原始染色体种群

随机以n个数作为可行解（染色体），生成n个。
生成适应度函数

适应度函数在通常情况下求的是最大值，但在本文中是用来求最短路径的，所以取路程和的倒数作为适应度。
选择染色体

采用轮盘赌算法（$\mbox{染色体i被选择的概率} = \mbox{染色体i的适应度}{\div}\mbox{所有染色体的适应度之和}$)产生父代染色体。
编码

把权值作为基因，n个基因组合成一个染色体。
交叉

依概率选出偶数个染色体，将两个染色体的中间一段基因进行交换，以此生成N-M个自带染色体
变异

对上述N-M个染色体，随机选出染色体上的几个基因进行随机修改。
复制

对父代染色体中适应度较高的M个进行复制，作为子代。
解码
逐代进化

上述的经过交叉变异的N-M个染色体和经过复制的M个染色体作为子代，再重复操作不断进化。

总结

最小生成树

对于最小生成树的Prim算法，记一共有v个顶点，则时间复杂度为$O(v^2)$。
对于最小生成树的Kruskal算法，记一共有e条边，则时间复杂度为$O(e\log_{2}{e}) $。
对两种算法而言，点相对多的树宜采用Kruskal算法，边相对多的树宜采用Prim算法。

旅行商问题

Prim算法和Kruskal算法扩展后不是最优解，两者为近似算法，是近似解。

近似算法所得出的近似解与实际最优解的近似比为1到2之间。

代码

例题图：

	0	1	2	3	4
0	100	3	5	5	3
1	3	100	4	2	3
2	5	4	100	3	4
3	5	2	3	100	4
4	3	3	4	4	100

import numpy as np


# 邻域搜索算法的拓展，array为邻接矩阵，first为起点下标，n为城市个数
def prim(array, first):
    # a为已访问过的城市列表
    a = [first]
    length = 0
    n = len(array)
    array_copy = [[0 for i in range(n)] for j in range(n)]
    for i in range(0, n):
        for j in range(0, n):
            array_copy[i][j] = array[i][j]
    copy = [array_copy[first]]
    while len(a) < n:
        # 下一个去的城市
        new_to = np.argmin(copy[-1]) % n
        a.append(new_to)
        copy += [array_copy[new_to]]
        for i in range(0, len(copy)):
            for j in a:
                copy[i][j] = 100
    a.append(first)
    for i in range(0, n):
        length += array[a[i]][a[i + 1]]
    print("Prim结果为 " + str([i + 1 for i in a]) + "长度 " + str(length))


# 贪婪搜索算法的拓展，array为邻接矩阵，first为起点下标，n为城市个数
def krul(array, first):
    n = len(array)
    length = 0
    copy = [[0 for i in range(n)] for j in range(n)]
    for i in range(0, 5):
        for j in range(0, 5):
            copy[i][j] = array[i][j]
    a = []

    while len(a) < n:
        new_to = np.argmin(copy) % n
        new_from = (np.argmin(copy) - new_to) // n
        copy[new_from][new_to] = 100
        copy[new_to][new_from] = 100
        if new_to not in a and new_from not in a:
            a.append(new_from)
            a.append(new_to)
        if new_to in a and new_from not in a:
            a.append(new_from)
        if new_to not in a and new_from in a:
            a.append(new_to)
    result = [i + 1 for i in a]
    copy_result = result[:]
    for i in copy_result:
        if i != (first + 1):
            result.pop(0)
            result.append(i)
        else:
            break
    result.append(first + 1)

    for i in range(0, n):
        length += array[result[i] - 1][result[i + 1] - 1]
    print("Kruskal结果为 " + str(result) + "长度 " + str(length))


if __name__ == '__main__':
    array = [[100, 3, 5, 5, 3],
             [3, 100, 4, 2, 3],
             [5, 4, 100, 3, 4],
             [5, 2, 3, 100, 4],
             [3, 3, 4, 4, 100]]
    prim(array, 1)
    krul(array, 1)

运行结果：

Prim结果为 [2, 4, 3, 5, 1, 2]长度 15
Kruskal结果为 [2, 4, 1, 5, 3, 2]长度 18