高效排序生成器路径以找到最长路径

Question

我正在尝试写一个函数，计算在给定燃料限制内，可以到达的网格中未探索的单元格的最大数量。比如说，我有一个10x10的网格，网格中的每个单元格都是相互连接的，它们之间的权重是曼哈顿距离。然后我从这个网格创建一个邻接矩阵，大小是100x100，并使用networkx库从这个邻接矩阵创建一个图。接着，我使用all_simple_paths函数，这个函数会返回一个生成器，里面包含从源节点到目标节点的所有路径。

现在问题来了，当我试图遍历这个生成器，以找到包含最多未探索单元格的路径（在这种情况下，路径长度就是未探索单元格的数量）时，我的程序要么耗尽内存，要么执行时间非常长。

我尝试把生成器转换成一个列表，然后按路径长度从长到短排序，但这样会导致我的Python脚本的内存不断增加，直到占满我电脑上的所有可用内存（16GB）。我还尝试使用sorted函数来排序生成器，如下所示，但这也需要很长时间执行，最终同样会耗尽内存。

G = nx.from_numpy_array(A)
sorted_paths = sorted(nx.all_simple_paths(G, source=current_node, target=target_node), key=len, reverse=True)

如果有人有建议，能帮我解决这个问题，我将非常感激。无论是排序生成器，还是使用networkx或其他Python库中的某个函数，帮助我找到网格中未探索单元格的最大数量。

Answer 1

正如我在上面的评论中提到的，我建议直接在网格图上进行搜索，而不是在曼哈顿距离的图上搜索。

1. 网格图的规模比曼哈顿距离的图要小得多，因此可能的路径搜索空间也更小。

2. 每次移动一个网格位置的路径，至少和“跳过”一个网格位置的路径一样好。

3. 使用网格图后，可以发现更多的优化。例如，如果A和B之间的曼哈顿距离是偶数，那么只需要考虑最大长度为偶数的路径。假设A和B之间的距离是10，而最大路径长度是15。那么只需要查看最大长度为14的路径，因为在A和B之间不会有长度为15的路径。这可以轻松带来2倍的速度提升。

import networkx as nx
import time

g = nx.grid_2d_graph(10, 10)

for maximum_distance in range(17, 21):
    tic = time.time()
    paths = list(nx.all_simple_paths(g, (0, 0), (9, 9), maximum_distance))
    toc = time.time()
    print(f"Maximum distance: {maximum_distance}; total paths: {len(paths)}; time elapsed: {toc-tic:.1f} seconds")

# Maximum distance: 17; total paths: 0; time elapsed: 25.8 seconds
# Maximum distance: 18; total paths: 48620; time elapsed: 62.9 seconds
# Maximum distance: 19; total paths: 48620; time elapsed: 178.0 seconds
# Maximum distance: 20; total paths: 621452; time elapsed: 462.2 seconds