使用字典中的特定键构建列表（python）？

Question

我正在用 Python 实现 Dijkstra 搜索算法。在搜索结束时，我使用前驱图重建最短路径，从目标节点的前驱开始。例如：

path = []
path.append(destination)
previous = predecessor_map[destination]
while previous != origin:
    path.append(previous)
    previous = predecessor_map[previous]

有什么方法可以用更少的代码行来做到这一点（例如列表理解）？

Answer 1

我唯一的建议是消除轻微的代码重复：

path = []
previous = destination
while previous != origin:
    path.append(previous)
    previous = predecessor_map[previous]

除此之外，我认为您的代码实际上非常清晰，并且不太可能从任何缩短代码的尝试中受益。

最后，值得注意的是，当 destination == origin 时，上述内容也适用，而您的原始版本很可能不会（取决于 predecessor_map 的填充方式）。不知道这是否与您的用例相关。

Answer 2

这可能有效：

path = [destination]
path += iter(lambda: predecessor_map[path[-1]], origin)

它的行为与您的原始代码相同。但你已经写的就很好了。

如果destination可以等于origin：

path = []
path += iter(lambda: predecessor_map[path[-1]] if path else destination, origin)

它的行为与@aix 的代码。

Answer 3

def backwalk(mymap, start, origin):
    yield start
    current = mymap[start]
    while current != origin:
        yield current
        current = mymap[current]

path = list(backwalk(predecessor_map, destination, origin))

这将步行和收集任务分开。

如果你能确保你永远不会从原点开始，你可以简化为

def backwalk(mymap, start, origin):
    current = start
    while current != origin:
        yield current
        current = mymap[current]

Answer 4

您可以递归地遍历边，假设 predecessor_map 是一个 dict 将节点映射到父节点，并且 None 是根：

predecessor_map={0: None, 1: None, 2: 1, 3: 1, 4: 0, 5: 1}

定义一个遍历的递归函数反向树：

def path(node, predecessors):
    return [None] if node is None else [node] + path(predecessors.get(node), predecessors)

或者，如果你敢的话，Y 组合器：

Y=lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))
path=Y(lambda f: lambda node, p: [None] if node is None else [node] + f(p.get(node), p))

使用中（使用列表理解）：

>>> print [node for node in path(None, predecessor_map)]
[None]
>>> print [node for node in path(0, predecessor_map)]
[0, None]
>>> print [node for node in path(1, predecessor_map)]
[1, None]
>>> print [node for node in path(2, predecessor_map)]
[2, 1, None]
>>> print [node for node in path(3, predecessor_map)]
[3, 1, None]
>>> print [node for node in path(4, predecessor_map)]
[4, 0, None]
>>> print [node for node in path(5, predecessor_map)]
[5, 1, None]

Answer 5

另一种可能的解决方案是使用带有延迟输出的函数式编程：

from itertools import tee, chain, imap, takewhile

predecessor_map = {2:1, 3:2}
destination = 3
origin = 1

def backwalk(predecessor_map, start, origin):

    def deffered_output():
        for i in output:
            yield i

    result, a = tee(deffered_output())
    b = imap(predecessor_map.get,a)
    output = takewhile(lambda x: x!=origin,chain([start],b))

    return result

print(list(backwalk(predecessor_map,destination,origin)))

我个人不会使用这种方法。但对于训练来说这很有趣。

说明
关键元素是 deferred_output，它推迟对 output 的调用。
然后我们使用 tee 将 output 拆分为 2 个迭代器。
然后，我们将 predecessor_map.get 应用于名为 a 的第二个迭代器，并将新迭代器分配给 b。
然后我们用 takewhile 控制输出，并在到达 origin 时停止。

Answer 6

我认为你无法通过理解来完成这次迭代。也许你可以稍微简化一下，就像这样：

    path, previous = [], destination
    while True:
        path.append(previous)
        previous = predecessor_map[previous]
        if previous == origin:
            break

上面的循环使用 do..while 看起来会更好，但 Python 缺少它