Функциональное решение для алгоритма коротких путей в 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) 
     
    Interesting Posts for Van-Lav

    IOError: Разрешение отклонено при попытке открыть скрытый файл в режиме «w»

    «Стандартный» способ создания файла конфигурации, подходящего для Python и Java вместе

    Как найти количество аргументов функции Python?

    Перенаправление страницы Python + Django

    Как сохранить список в виде CSV-файла с помощью python с новыми строками?

    Поиск и замена регулярных выражений Python

    Как настроить ipython для отображения целых чисел в шестнадцатеричном формате?

    Как установить старую версию Django на virtualenv?

    Связать клиент Java с Python-сервером

    Python – Telnet закрывается перед ожиданием функции чтения печати

    Pandas: сохраняйте строки, если хотя бы одна из них содержит определенное значение

    Попытка использовать open (имя файла, 'w') дает IOError: Нет такого файла или каталога:

    Django: Где поставить вспомогательные функции?

    Каков правильный способ взять путь к каталогу как пользовательский ввод?

    Какую кодировку используют обычные строки python?

    Python - лучший язык программирования в мире.