实例讲解Python基于回溯法子集树模板解决旅行商问题（TSP）-木庄网络博客

本文摘自php中文网，作者巴扎黑，侵删。

这篇文章主要介绍了Python基于回溯法子集树模板解决旅行商问题（TSP）,简单描述了旅行商问题并结合实例形式分析了Python使用回溯法子集树模板解决旅行商问题的相关实现步骤与操作技巧,需要的朋友可以参考下

本文实例讲述了Python基于回溯法子集树模板解决旅行商问题（TSP）。分享给大家供大家参考，具体如下：

问题

旅行商问题（Traveling Salesman Problem,TSP）是旅行商要到若干个城市旅行，各城市之间的费用是已知的，为了节省费用，旅行商决定从所在城市出发，到每个城市旅行一次后返回初始城市，问他应选择什么样的路线才能使所走的总费用最短？

分析

此问题可描述如下：G=(V,E)是带权的有向图，找到包含V中每个结点一个有向环，亦即一条周游路线，使得这个有向环上所有边成本之和最小。

这个问题与前一篇文章http://www.jb51.net/article/122933.htm的区别就是，本题是带权的图。只要一点小小的修改即可。

解的长度是固定的n+1。

对图中的每一个节点，都有自己的邻接节点。对某个节点而言，其所有的邻接节点构成这个节点的状态空间。当路径到达这个节点时，遍历其状态空间。

最终，一定可以找到最优解!

显然，继续套用回溯法子集树模板！！！

Python编程从入门到实践第2版

￥69.8元 人民邮电出版社

python入门书籍，非常畅销，超高好评，python官方公认好书。