求建立货郎担模型运筹学中著名的旅
所谓旅行推销员问题是：
推销员从驻地出发经过所要去的城市至少一次返回原地，应如何安排使其总的旅行距离最短。
类似的可以使费用最小或时间最短等。称符合要求的巡游路线为一个巡回。 巡回的概念里不包含优化指标的比较，只是一个可行方安。从旅行推销员问题的概念来看它的本质是哈密尔顿圈的应用与延伸若把城市作为一个顶点，哈密尔顿圈只要求过每一个顶点一次且仅一次；
而推销员回路是至少一次必要时允许重复通过。 （补充类使问题还有“中国邮路问题”，详细内容见参考资料）。
旅行推销员问题中各个顶点重复通过主要是考虑巡回线路的最佳化问题。对于确定的图，欧拉回路如果存在则回路是唯一的，而哈密尔顿圈若存在则可能有...全部
所谓旅行推销员问题是：
推销员从驻地出发经过所要去的城市至少一次返回原地，应如何安排使其总的旅行距离最短。
类似的可以使费用最小或时间最短等。称符合要求的巡游路线为一个巡回。
巡回的概念里不包含优化指标的比较，只是一个可行方安。从旅行推销员问题的概念来看它的本质是哈密尔顿圈的应用与延伸若把城市作为一个顶点，哈密尔顿圈只要求过每一个顶点一次且仅一次；
而推销员回路是至少一次必要时允许重复通过。
（补充类使问题还有“中国邮路问题”，详细内容见参考资料）。
旅行推销员问题中各个顶点重复通过主要是考虑巡回线路的最佳化问题。对于确定的图，欧拉回路如果存在则回路是唯一的，而哈密尔顿圈若存在则可能有多条。
定义：
1。
推销员回路：
在过各个顶点的巡回线路中，若每个顶点至少经过一次，则称为推销员回路
2
哈密尔顿回路
在过各个顶点的巡回线路中，若每个顶点只经过一次，则称为哈密尔顿回路。
一般情况下，在同一网络中最优推销员回路与最优哈密尔顿回路是不同的。
$$$$!!!!!推销员回路与哈密尔顿回路间的关系
网络N=(V,A,W)中，任二个顶点Vi,Vj,若能满足下列三角不等式
Wij<=Wik+Wkj;
Vi,Vi,Vk属于V(打不出数学符号），Vk！=Vi,Vk!=Vj,Vi!=Vj
则最优推销员回路与最优哈密尔顿回路相等！！
证明过程你找一些数学建模或运筹图论论的书（我也是在数模培训是老师讲时记住的）。
据此我们导出了最优推销员回路与最优哈密尔顿回路的等价条件：对于一般的无向网络，我们可以应用任意顶点对之间的最短路算法构造一个等价网络，在该网络中个顶点对之间的距离（权值）由最短路代替，显然，在等价网络中三角不等式均能满足，据此，解得的最由哈密尔顿回路可以方便的还原为原网络中的最由推销员问题。
同理，在有向或混合网络中只要网络是强连通的，以上转换均可实现。
最由推销员回路问题是个NP问题!!!!
说这么多够了吧！
求解这种问题一般都有两类解法：
一类是精确解法，他是个np问题精确解法的恐怖我就不说了，但可通过一些方法来逼近多项式解法，我就搞过用贪心法和分支定界法综和运用使问题的复杂度缩小很多，
另外就是近似解法，有局部搜索法，但我用模拟退货和遗传算法也解过还算理想，但细节上有些困难。
。收起
