Soluzione funzionale per algoritmo di percorso breve in Python

Question

Sto leggendo Learn You Some Erlang for Great Good! e ho scoperto un interessante puzzle. Ho deciso di implementarlo in Python in un modo più funzionale.

Si prega di vedere il mio codice:

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

Ma mi ha colpito nel problema, non so come mantenere lo stato di posizione corrente. Il risultato è: [8, 27, 95, 40]. Potrebbe aiutarmi a risolvere il mio codice.

Answer 1

In questo caso specifico, e utilizzando la struttura dei dati, sembra che si dovrebbe essere in grado di eseguire due scenari in parallelo:

• costo di un
• Costo del B

È possibile mantenere un costo corrente e i dati raccolti forniscono un "costo per passare" nel terzo elemento.

Quindi è necessario chiedere: quale è più economico? Rimanere sul percorso di partenza o passare all'altro percorso?

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 effetti, penso che, come in tutti i problemi di pathfinding, sia necessario calcolare la lunghezza totale del percorso dall'inizio alla fine di ogni punto. Quindi devi calcolare entrambi, l'elenco del percorso in A e l'elenco del percorso in B.

Non so se l'algoritmo ricorsivo fa parte dell'esercizio ma ho usato un ciclo semplice.

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)