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 • 当网路边权满足三角不等式时，一般旅行推销员问题就等价 于最小哈密尔顿回路问题 • 当网路边权不满足三角不等式时，只要用两点间最短路的距 离代替原来的边权，就可以满足三角不等式，在此基础上求 最小哈密尔顿回路 典型的应用： • 乡邮员的投递路线 • 邮递员开邮箱取信的路线问题 • 邮车到各支局的转趟问题