4

旅行者のセールスマンの問題を解決するための 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
4

2 に答える 2

1
  1. 多数のランダムなソリューションを生成します。
  2. これらのソリューションを長さで並べ替えます。
  3. 最悪の 50% を削除
  4. 最良の 50% を何らかの方法で組み合わせる (スプライスする)
  5. 後藤2。

安定した解が得られるまでこれを繰り返します。これは (ほぼ確実に) 最適ではありませんが、ランダムよりははるかに優れています。

于 2012-12-08T12:29:23.173 に答える