662旅行推销员问题( Traveling salesman problen) 旅行推销员问题(TSP):设v,v2,…,Vn为n个已知城市,城市 之间的旅程也是已知的,要求推销员从v出发,走遍所有城 市一次且仅一次又回到出发点,并使总旅程最短 ·这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路 问题 一般旅行推销员问题(GTSP):允许点重复的TSP ·当网路边权满足三角不等式时,一般旅行推销员问题就等价 于最小哈密尔顿回路问题 当网路边权不满足三角不等式时,只要用两点间最短路的距 离代替原来的边权,就可以满足三角不等式,在此基础上求 最小哈密尔顿回路 典型的应用: 乡邮员的投递路线 邮递员开邮箱取信的路线问题 ·邮车到各支局的转趟问题
6.6.2 旅行推销员问题(Traveling Salesman Problem) • 旅行推销员问题(TSP)：设v1 , v2 , ...,vn 为 n 个已知城市，城市 之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城 市一次且仅一次又回到出发点，并使总旅程最短 • 这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路 问题 • 一般旅行推销员问题(GTSP)：允许点重复的TSP • 当网路边权满足三角不等式时，一般旅行推销员问题就等价 于最小哈密尔顿回路问题 • 当网路边权不满足三角不等式时，只要用两点间最短路的距 离代替原来的边权，就可以满足三角不等式，在此基础上求 最小哈密尔顿回路 典型的应用： • 乡邮员的投递路线 • 邮递员开邮箱取信的路线问题 • 邮车到各支局的转趟问题
TSP的启发式算法( Heuristic algorithm) 穷举法:指数算法 分支定界法:隐枚举法 二交换法(mwo- option,Lin' algorithm) 哈密尔顿回路可以用点的序列表示 从任一个哈密尔顿回路(即任何一个序列出发 按照一定顺序试图交换相邻两个点的顺序,若路程减少则完 成交换,继续下一个交换;若没有改善,则不进行本次交换 尝试下一个交换;若所有的相临交换都试过而不能改善,则 算法结束,得到一个局部最优点 模拟退火( Simulated annealing) 随机地采用二交换法 当交换后没有使目标函数改善,也可能以瓌尔兹曼分布概率 被接受,但这种概率是随模拟的温度下降而减少的 发挥了计算机的优点,尽量减少陷入局部极值点 模拟物理机制
TSP 的启发式算法(Heuristic algorithm) • 穷举法：指数算法 • 分支定界法：隐枚举法 • 二交换法 (two-option, Lin’s algorithm) – 哈密尔顿回路可以用点的序列表示 – 从任一个哈密尔顿回路(即任何一个序列)出发 – 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完 成交换，继续下一个交换；若没有改善，则不进行本次交换， 尝试下一个交换；若所有的相临交换都试过而不能改善，则 算法结束，得到一个局部最优点 • 模拟退火 (Simulated Annealing) – 随机地采用二交换法 – 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率 被接受，但这种概率是随模拟的温度下降而减少的 – 发挥了计算机的优点，尽量减少陷入局部极值点 – 模拟物理机制
二交换法举例 23 23 ① 3 3 10 6 6 初始解:1-2-3-4-5 →1-3-2-4-5 3 3 10 10 ⑤。④ 1-3-2-4-5→1-3-4-2-5 1-3-4-25→1-3-45-2 →5-3-4-2-1×→3-1-4-2-5×
二交换法举例 2 3 5 4 1 11 23 2 6 10 1 3 1 17 8 2 5 4 11 23 2 6 10 1 1 1 3 初始解：1-2-3-4-5 → 1-3-2-4-5 1 23 1 2 6 10 3 1 2 3 5 4 1-3-2-4-5 → 1-3-4-2-5 2 3 5 4 1 1 2 10 3 1 1-3-4-2-5 → 1-3-4-5-2 → 5-3-4-2-1 → 3-1-4-2-5