Funktionelle Lösung für Short-Path-Algorithmus in Python

Question

Ich lese Learn You Some Erlang for Great Good! und fand interessante Puzzle. Ich habe mich entschlossen, es in Python auf möglichst funktionale Weise zu implementieren.

Bitte siehe meinen Code:

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, [])) 

Aber ich traf in Problem, ich weiß nicht, wie Zustand der aktuellen Position zu halten. Ergebnis ist: [8, 27, 95, 40]. Könnten Sie bitte helfen, meinen Code zu beheben.

Answer 1

In diesem speziellen Fall und Ihre Datenstruktur verwendet wird, scheint es, dass Sie in der Lage sein sollten zwei Szenarien parallel laufen zu lassen:

• Kosten eines
• Kosten B

Sie können aktuelle Kosten verwalten, und die Daten, die Sie sammeln, stellen eine "Kosten für den Wechsel" im dritten Element bereit.

Sie müssen also fragen: Was ist billiger? Auf dem Startweg bleiben oder auf den anderen Weg wechseln?

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

In der Tat, ich denke, dass wie bei allen Pathfinding-Probleme müssen Sie die gesamte Pfadlänge von Anfang bis zu jedem Punkt berechnen. Dann müssen Sie beide berechnen, Liste der Pfad zu A und Liste der Pfad zu B.

Ich weiß nicht, ob rekursive Algorithmus Teil der Übung ist, aber ich habe eine einfache Schleife.

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)