最短路線優化工作不

Question

我試圖解決的紅寶石測驗問題在Python 60，這裏給出： http://rubyquiz.com/quiz60.html

一個基本上必須找到從一個號碼到另一個的最短路徑僅加倍，減半或將數字加2。

編寫一個程序來真正解決這個問題並不太難：

def maze_solver(a, b): 
    paths = [[a]] 
    final = [] 

    for ind, path in enumerate(paths): 

     if path[-1] == b: 
      return path 

     last = path[-1] 

     paths.append(path + [last * 2]) 
     paths.append(path + [last + 2]) 
     if last % 2 == 0: 
      paths.append(path + [last/2]) 


print maze_solver(979, 2) 


>>> maze_solver(9, 2) 
[9, 18, 20, 10, 12, 6, 8, 4, 2] 
>>> maze_solver(2, 9) 
[2, 4, 8, 16, 18, 9] 

但是，當我試圖去優化它，它失敗了。我認爲，如果兩條路徑具有相同的終點，一條路徑比另一條路徑短，則可以消除較長的路徑。

我想這種優化：

def maze_solver(a, b): 
    paths = [[a]] 
    final = [] 

    for ind, path in enumerate(paths): 

     if path[-1] == b: 
      return path 

     for other in paths: 
      if ind != paths.index(other): 
       if path[-1] == other[-1] and len(other) >= len(path): 
        paths.remove(other) 

     last = path[-1] 

     paths.append(path + [last * 2]) 
     paths.append(path + [last + 2]) 
     if last % 2 == 0: 
      paths.append(path + [last/2]) 

但這並不甚至會得到正確的答案：

>>> maze_solver(9, 2) 
[9, 11, 22, 24, 48, 24, 12, 6, 8, 4, 2] 

我不知道爲什麼這段代碼不工作，因此，如果任何人都可以向我解釋我做錯了什麼，這將是非常有益的，謝謝！

Answer 1

在遍歷整個列表時修改列表可能很危險。

見this answer