使用Python解决TSP问题

Question

我被分配了一份作业，需要编写Python程序来解决旅行商问题。在课堂上，他们解释了它的工作原理，并展示了一个例子。

path_map = [[0,10,15,20],
        [5,0,9,10],
        [6,13,0,12],
        [8,8,9,0]]

这是一个示例地图。 我以为这是一个流行的问题，我可以在互联网上找到解决此问题的算法。但我没有找到。我尝试了自己的版本，但失败了。希望得到任何帮助。 以下是我目前所拥有的。

class TSP:

def __init__(self, init, path_map):
    self.init = init
    self.cost = 0
    self.path_map = path_map
    self.vertices = [i for i in range(1,len(path_map)+1)]

def min_path(self, start):
    if not self.vertices:
        return self.path_map[start-1][init-1]
    else:
        m = [i for i in range(len(self.vertices)+1)]
        i=0
        for v in self.vertices:
            tv = self.vertices.pop(v-1)
            m[i]=self.cost + self.min_path(v)
            self.vertices.insert(v-1,tv)
            i = i + 1
        self.cost = self.cost + min(m)

    return cost `

当我尝试运行它时，我得到的是：

>>> t = TSP(1,path_map)
>>> t.min_path(1)
Traceback (most recent call last):
  File "<pyshell#54>", line 1, in <module>
    t.min_path(1)
  File "/home/wanhrust/python/TSP.py", line 42, in min_path
    m[i]=self.cost + self.min_path(v)
  File "/home/wanhrust/python/TSP.py", line 42, in min_path
    m[i]=self.cost + self.min_path(v)
  File "/home/wanhrust/python/TSP.py", line 42, in min_path
    m[i]=self.cost + self.min_path(v)
  File "/home/wanhrust/python/TSP.py", line 41, in min_path
    tv = self.vertices.pop(v)
IndexError: pop index out of range

- user1322731

---

你的教练有提到过“图”或“图论”吗？ - Jon Clements

“你说的‘失败’是什么意思？它能运行吗？它会抛出异常吗？有时它会给出正确的解决方案吗？你是否遇到了奇怪的错误？你具体遇到的问题是什么？” - phant0m

是的，他提到了图论。我们下一节课会开始学习它。这个程序出错了。我已经在我的问题中添加了错误信息。 - user1322731

Answer 1

1. 生成大量随机解决方案。
2. 按长度对这些解决方案进行排序。
3. 删除最差的50％。
4. 以某种方式将最好的50％彼此组合（拼接在一起）。
5. 返回步骤2。

重复以上步骤，直到获得稳定的解决方案。它（几乎肯定）不会是最优的，但比随机选择要好得多。

- Paul Collingwood

---

谢谢。但任务是找到最好的一个。 - user1322731

你还应该在问题中提到寻找最佳解决方案的要求，对于TSP来说，这意味着相当重要的事情。 - Paul Collingwood

Answer 2

IndexError: 弹出索引超出范围 - 当迭代索引不存在于列表中时，例如list = [1,2,3]，有3个元素，而您尝试获取list[10]时，就会出现该错误

- Arturas Lapinskas