使用最佳优先策略构建图形路径

Question

我希望我的程序从给定的列表列表中使用最佳优先（贪婪）策略构建路径（即选择路径中的下一个点将是最接近当前点的那个）距离，其中 distances[i][j] 是点 i 到点 j 之间的距离。

我的代码片段中有一个问题，该片段负责查找最低距离：

        for i in range(len(pointsLeft) - 1):
            if i in pointsLeft and i not in path: #only looks at points still not in path
                lowDist = distances[lastPoint][i]
                nextDist = distances[lastPoint][i + 1]
                if nextDist < lowDist:
                    lowDist = nextDist

我注意到在前几个循环中代码运行正常，但随后找到了错误的最小值。

Answer 1

您必须将 lowDist 重新初始化为任意高的值，否则您可能会保留不需要的 lowDist 以前的值。此外，您只检查标记为 [0, len(pointsLeft)-1) 的节点，而不是剩余的特定节点，而是您想要

lowDist = 100000000  # just set this value to anything greater than all the edges
for i in pointsLeft:
     nextDist = distances[lastPoint][i]
     if nextDist < lowDist:
          lowDist = nextDist

它检查所有且仅检查 pointsLeft 中的节点。另请注意，pointsLeft 中的任何节点都将自动不在路径中，因此您无需单独检查。

使用最佳优先策略构建图形路径

Constructing a graph path using a best first strategy

python

graph

greedy

best-first-search