Построение пути графа с использованием лучшей первой стратегии

Question

Я хочу, чтобы моя программа строила путь, используя лучшую первую (жадную) стратегию (т. Е. Следующая точка, выбранная как находящаяся на пути, будет ближайшей к текущей точке) из заданного списка списков расстояний, где расстояния [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), а не указанные c оставшиеся узлы, и вместо этого вы хотите что-то вроде

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 автоматически не будет уже в пути, поэтому вам не нужно проверять это отдельно.