TSP的启发式算法( Heuristic algorithm) 穷举法:指数算法 分支定界法:隐枚举法 二交换法(mwo- option,Lin' algorithm) 哈密尔顿回路可以用点的序列表示 从任一个哈密尔顿回路(即任何一个序列出发 按照一定顺序试图交换相邻两个点的顺序,若路程减少则完 成交换,继续下一个交换;若没有改善,则不进行本次交换 尝试下一个交换;若所有的相临交换都试过而不能改善,则 算法结束,得到一个局部最优点 模拟退火( Simulated annealing) 随机地采用二交换法 当交换后没有使目标函数改善,也可能以瓌尔兹曼分布概率 被接受,但这种概率是随模拟的温度下降而减少的 发挥了计算机的优点,尽量减少陷入局部极值点 模拟物理机制TSP 的启发式算法(Heuristic algorithm) • 穷举法：指数算法 • 分支定界法：隐枚举法 • 二交换法 (two-option, Lin’s algorithm) – 哈密尔顿回路可以用点的序列表示 – 从任一个哈密尔顿回路(即任何一个序列)出发 – 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完 成交换，继续下一个交换；若没有改善，则不进行本次交换， 尝试下一个交换；若所有的相临交换都试过而不能改善，则 算法结束，得到一个局部最优点 • 模拟退火 (Simulated Annealing) – 随机地采用二交换法 – 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率 被接受，但这种概率是随模拟的温度下降而减少的 – 发挥了计算机的优点，尽量减少陷入局部极值点 – 模拟物理机制