商旅问题(TSP)之组合优化传统解法

穷举法

如果有a b c d四个点，通过穷举(n-1)！的排列组合，可以精确得到最优解

近邻法

如果有a b c d四个点

寻找一条从a出发，不经过重复节点，最终回到a的环路

近邻法通过选取最近的一个点为下一个节点

不断迭代

然后回到a

复杂度为n^2

tsp-neareast

2-opt

有a b c d e....个节点，

• 随机一个序列得到总长度minLen
• 随机选择两个点 p q
• 颠倒线段p q并计算curLen
• 如果curLen<minLen，则minLen = curLen
• 迭代上述过程若干次，停止

k-opt

• 随机一个序列得到总长度minLen
• 随机选择k个点p1 p2 .. pk
• 通过穷举k个线段的排列组合，计算curLen
• 如果curLen<minLen，则minLen = curLen
• 迭代上述过程若干次，停止

如果k比较大，排列组合会相当大，而且穷举组合难度也相当大

Lin-Kernighan

为了解决K-opt的k过大导致高计算复杂度的问题

提出以下算法

• 把点划分两个自己n1 n2
• 遍历n1选择元素i，选择n2中的元素j，交换，直到交换完所有元素
• 计算总长度p，如果小于最小值，则替换
• 迭代上述过程t次，并结束

分支限界法

• 上界：通过贪心算法找到一个解，设为上界
• 下界：每个子集，寻找每行最小的两个元素相加，得到下界。因为每个地点必然有一出一入

使用深度遍历算法，如果累加超过上界，则抛弃

如果子集的下界超过上界，抛弃

最终返回准确解