文档介绍：贪心算法求解(TSP) 旅行商问题
-
问题描述
旅行商问题(Traveling Salesman Problem, TSP):有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的具有最短路程的环路。
例如给定一个城市和城市间的距离集合,求经过所有城市恰好一次的最短回路,
即;给定图G=(V,E,W),其中V为顶点集合,|V|=n,E为边集合,W为边权函数,求集合{1,2,…n}的一个排列使得下式最小。
解决思路:
借助矩阵把问题转化为矩阵中点的求解:
首先构造距离矩阵,任意节点到自身节点的距离为无穷大(在这里我用100来表示无穷大),在第一行找到最小项a[1][j],从而跳到第j行;再找到最小值a[j][k],从而跳到第k行进行查找……
然后构造各行允许数组row[n]={1,…,1},各列允许数组colable[n]={0,1,…,1},其中1表示允许访问,即该节点未被访问;0表示不允许访问,即该节点已被访问。如果该行或该列不允许访问,则跳过该点访问下一节点。
核心算法说明:
1)输入节点数n和连接矩阵a
2)定义行、列允许矩阵row[n]={1,…,1}、row[n]={1,…,1}
3)赋初值:s=0,i=0
4)While row[i]=1
5) j=0,m=a[i][0],k=0
6) 找到第一个允许访问的节点a[i][j]
7) 寻找a[i][j~n-1]中的最小元素
8)End while
特殊说明:
程序在访问最后一个节点钱,所访问的行中至少有1个允许访问的节点,依次访问这些节点找到最小即可:在访问最后一个节点后,再次访问,会返回k=0,即实现了访问源节点。所以,各个节点都被访问,且访问路径为一简单回路。
实例演示:
例题:
以4个节点为例,演示算法运行过程(以100表示无大):
输入连接矩阵:
100 3 9 2
3 100 1 4
9 1 100 7
2 4 7 100
实例演示:
运算过程:
(1)
(2)
(3)
(4)
实例演示:
对应连线图:
运行结果:
贪心选择性质(n>=2):
因为旅行商问题是一个典型的NP问题,找不到一个算法能保证在多项式时间内得到最优解。所以无需证明其贪心选择性质,而本算法只要求找到近似解,而在多项式时间内结束。
最优子结构性质(n>=2):
设sn是此问题的最优解,那么可以把它分解为sn=s2+sn-1;
假设存在s’n-1为n-1规模是的最优解,则sn<s2+s’n-1,
而这与假设矛盾,所以可以得出旅行商问题具有最优子结构性质。