Pythonのショートパスアルゴリズムのための機能的解答

Question

私はLearn You Some Erlang for Great Good!を読んで興味深いパズルを見つけました。私はPythonで最も機能的な方法で実装することに決めました。

私のコードを参照してください：

def open_file(): 
    file_source = open('resource/path.txt', 'r') # contains 50\n 10\n 30\n 5\n 90\n 20\n 40\n 2\n 25\n 10\n 8\n 0\n 
    return file_source 


def get_path_tuple(file_source, pathList=[]): 
    try: 
     node = int(next(file_source)), int(next(file_source)), int(next(file_source)) 
     pathList.append(node) 
     get_path_tuple(file_source, pathList) 
    except StopIteration: 
     pass 
    return pathList 


def short_step(pathList, n, stepList): 
    try: 
     stepA = pathList[n][0] + pathList[n][1] 
     stepB = pathList[n][1] + pathList[n][2] 
     stepList.append(min([stepA, stepB])) 
     short_step(pathList, n+1, stepList) 
    except IndexError: 
     pass 
    return stepList 


pathList = get_path_tuple(open_file(), []) 
pathList.reverse() 
print(short_step(pathList, 0, [])) 

をしかし、私は問題にヒット、私は現在の場所の状態を維持する方法がわかりません。結果は[8, 27, 95, 40]です。 コードを修正するのを助けてください。

Answer 1

この特定の場合には

、およびデータ構造を使用して、あなたが並列に2つのシナリオを実行することができるはずと思われる：Bの

コストの

• コストを

現在のコストを維持することができます。収集したデータは、第3要素の「切り替えにかかるコスト」をもたらします。

あなたは質問する必要があります：どちらが安いですか？開始経路に留まるか、もう一方の経路に切り替えるか？

path_list = [ 
     (50, 10, 30), 
     (5, 90, 20), 
     (40, 2, 25), 
     (10, 8, 0), 
] 

A = 0 
B = 1 
Switch = 2 

def cheapest_path(path_list, path=None, history=None): 
    if history is not None: 
     # Terminate when path_list is empty 
     if not path_list: 
      return history 

     # Determine cost to stay this path, vs. cost to switch 
     step = path_list[0] 
     path_list = path_list[1:] 

     stay_on_path = cheapest_path(path_list, path, history + [step[path]]) 
     switch_path = cheapest_path(path_list, B if path == A else A, history + [step[path], step[Switch]]) 

     return switch_path if sum(switch_path) < sum(stay_on_path) else stay_on_path 
    else: 

     pathA = cheapest_path(path_list, A, []) 
     pathB = cheapest_path(path_list, B, []) 
     return pathA if sum(pathA) < sum(pathB) else pathB 

print(", ".join(map(str, cheapest_path(path_list)))) 

Answer 2

実際、すべての経路探索の問題と同様に、開始から終了までの経路長の合計を計算する必要があります。次に、AへのパスリストとBへのパスリストの両方を計算する必要があります。

再帰アルゴリズムがエクササイズの一部であるかどうかわかりませんが、単純なループを使用しました。

pathList = [[50,10,30],[5,90,20],[40,2,25],[10,8,999999]] 

def all_steps(pathList): 

    stepListA,stepListB = [],[] 
    for n in range(0,len(pathList)): 

     #Step to A 
     if pathList[n][0]<=pathList[n][1] + pathList[n][2]:#A to A 
      new_stepListA = list(stepListA) 
      new_stepListA.append(pathList[n][0]) 
     else: #B to A 
      new_stepListA = list(stepListB) 
      new_stepListA.extend([pathList[n][1],pathList[n][2]])   

     #Step to B 
     if pathList[n][1]<=pathList[n][2] + pathList[n][2]:#B to B 
      new_stepListB = list(stepListB) 
      new_stepListB.append(pathList[n][1]) 
     else: #A to B 
      new_stepListB = list(stepListA) 
      new_stepListB.extend([pathList[n][0],pathList[n][2]]) 

     stepListA = list(new_stepListA) 
     stepListB = list(new_stepListB) 

    if sum(stepListA)<=sum(stepListB): 
     print "finish on A" 
     return stepListA 
    else: 
     print "finish on B" 
     return stepListB 


print all_steps(pathList)