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

事实上，我认为在所有寻路问题中，你必须计算从起点到每个点的总路径长度。然后你必须同时计算，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)

Answer 2

在这种特定情况下，使用您的数据结构，您似乎应该能够并行运行两个场景：

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