Pythonアルゴリズム、返すべきものを返さない

Question

TSPランダム反復アルゴリズム（Python）

私はかなり新しいPythonです。私が行くようにそれを拾う。私が今打たれている問題はおそらく非常に恣意的な問題です。しかし私はあきらめた。すべての反復パスから「ベスト」を戻すと、最後に送信されたパスが返されます。なぜそれがこれを行うのかわかりません。 ifステートメントは、whileステートメントの終わりまで最適なパスとコストをソートする必要があります。

アルゴリズムは言ったツアーは、新たなツアーがあまりにも最高のツアーを設定して、前のツアーより安い場合は、各ツアーのコストを計算しすぎて、その後の私のマトリックスのためのランダム異なるパスを作成します。

しかし、それはdoesntの。

from random import randint 
from random import shuffle 
from time import * 

class main(): 

def calc(self, path, matrix, w): 

    pathen = path 
    matrix = matrix 
    nCost = 0 

    for x in range(int(w)): 
     if pathen[x] == 0: 
      first = x 
      prev = x 

    for x in range(int(w)): 
     for y in range(int(w)): 
      if pathen[y] == x: 
       next = y 

     nCost += matrix[prev][next] 
     prev = next 

    nCost += matrix[prev][first] 

    return nCost 

def ranIterative(self, matrix, w, stop): 
    best = 9999 
    path = [0 for x in range(int(w))] 
    bestPath = path 

    print(path) 

    while stop: 

     cost = 0 

     for x in range(int(w)): 
      path[x] = x 

     shuffle(path) 

     print(path) 

     for x in range(int(w)): 
      if path[x] == 0: 
       first = x 
       prev = x 

     for x in range(1, int(w)): 
      for y in range(int(w)): 
       if path[y] == x: 
        next = y 

      cost += matrix[prev][next] 

      prev = next 

     cost += matrix[prev][first] 

     print("Cost: " + str(cost)) 
     print("Bst: " + str(best)) 

     if cost < best: 
      best = cost 
      bestPath = path 
      bestest = bestPath 
      print(path) 
      print("Best path1: " + str(bestPath)) 

     stop -= 1 
     print("Best path2: " + str(bestPath)) 

    print("Best path3: " + str(bestPath)) 
    print("Best path3: " + str(bestest)) 
    return bestest 


def matrix(self, w): 
    matrix = [[0 for x in range(int(w))] for y in range(int(w))] 

    for x in range(int(w)): 
     for y in range(int(w)): 
      if y < x: 
       matrix[x][y] = randint(1, 9) 
       matrix[y][x] = matrix[x][y] 
    return matrix 


main = main() 
print("How many cities?") 
w = input() 
matrix = main.matrix(int(w)) 
print("How many iterations?") 
stop = input() 
path1 = main.ranIterative(matrix, int(w), int(stop)) 
cost = main.calc(path1, matrix, int(w)) 
print("With " + str(stop) + " iterations on " + str(w) + " cities gives:") 
print("Best path :" + str(path1)) 
print("Costs: " + str(cost)) 

OUTPUT：

How many cities? 
5 
How many iterations? 
10 
[0, 0, 0, 0, 0] 
[0, 1, 3, 4, 2] 
Cost: 30 
Bst: 9999 
[0, 1, 3, 4, 2] 
Best path1: [0, 1, 3, 4, 2] 
Best path2: [0, 1, 3, 4, 2] 
[0, 3, 4, 2, 1] 
Cost: 28 
Bst: 30 
[0, 3, 4, 2, 1] 
Best path1: [0, 3, 4, 2, 1] 
Best path2: [0, 3, 4, 2, 1] 
[4, 3, 0, 1, 2] 
Cost: 29 
Bst: 28 
Best path2: [4, 3, 0, 1, 2] 
[3, 1, 4, 0, 2] 
Cost: 25 
Bst: 28 
[3, 1, 4, 0, 2] 
Best path1: [3, 1, 4, 0, 2] 
Best path2: [3, 1, 4, 0, 2] 
[0, 4, 3, 1, 2] 
Cost: 33 
Bst: 25 
Best path2: [0, 4, 3, 1, 2] 
[2, 0, 1, 3, 4] 
Cost: 26 
Bst: 25 
Best path2: [2, 0, 1, 3, 4] 
[3, 0, 2, 4, 1] 
Cost: 28 
Bst: 25 
Best path2: [3, 0, 2, 4, 1] 
[2, 3, 0, 4, 1] 
Cost: 32 
Bst: 25 
Best path2: [2, 3, 0, 4, 1] 
[0, 1, 3, 2, 4] 
Cost: 32 
Bst: 25 
Best path2: [0, 1, 3, 2, 4] 
[2, 1, 4, 0, 3] 
Cost: 32 
Bst: 25 
Best path2: [2, 1, 4, 0, 3] 
Best path3: [2, 1, 4, 0, 3] 
Best path3: [2, 1, 4, 0, 3] 
With 10 iterations on 5 cities gives: 
Best path :[2, 1, 4, 0, 3] 
Costs: 32 

ご覧のとおり、私の結果は、このような単純な作業のために非常に間違っています。 私もこの問題を解決する方法を見つけるように見える傾けます。

Answer 1

あなたは何の違いを確認する必要があり可変（list、dict、set、...）と（int、float、str、tuple、...）

のでpathものではありませんlistあるので、それは、古典的なエラーがこれです、可変です：

bestPath = path 

あなたあなたが最良のパスを格納（およびそれを凍結）bestPath変数に、しかし、あなたはちょうどpath配列への別の参照を取得しているしていると思います。 pathのその後の変化はbestPathに反映し、あなたは常に計算された最後の値を取得します。

（それらは不変種類によって保存されているので、それは整数、浮動小数点、文字列のような値のために働くだろう：元を変更すると、コピーを変更しません）

作成することによって、それを修正例えば次のようなコピー：

bestPath = list(path)