Функциональное решение для алгоритма коротких путей в Python

Я читаю « Узнай, что ты, Эрланг, за великое благо! и узнал интересную головоломку. Я решил реализовать его на 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] . Не могли бы вы помочь исправить мой код.

    2 Solutions collect form web for “Функциональное решение для алгоритма коротких путей в Python”

    В этом конкретном случае и с использованием вашей структуры данных кажется, что вы должны иметь возможность запускать два сценария параллельно:

    • Стоимость A
    • Стоимость B

    Вы можете поддерживать текущую стоимость, а собранные вами данные обеспечивают «стоимость переключения» в третьем элементе.

    Поэтому вам нужно спросить: что дешевле? Пребывание на стартовом пути или переход на другой путь?

     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)))) 

    На самом деле, я думаю, что, как и во всех проблемах с поиском путей, вам нужно вычислить общую длину пути от начала до каждой точки. Затем вам нужно вычислить оба списка, путь к 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) 
    Python - лучший язык программирования в мире.