Если вы все еще застряли в этой проблеме, поскольку другие ответы / комментарии дают вам только частичный ответ - вот трещина в проблемном пространстве.
На самом деле вы можете использовать A * с несколькими модификациями для захвата (в основном) неупорядоченного пути M точек. Единственное, что вам нужно изменить, это эвристика и критерии завершения.
Сначала вам нужно изменить свою эвристику, чтобы учитывать пути через M точек. Эвристика должна быть допустимой и непротиворечивой, поэтому она должна равняться значению, меньшему или равному истинной стоимости пути, и может только уменьшаться по мере приближения к цели (должна быть монотонно возрастающей).
Вы можете думать о пути, по которому вы сейчас идете, как о М подпутях, которые вы должны пройти, каждый из которых действует как обычный путь. Таким образом, для одноточечного графика (только с завершающим пробелом) вы можете использовать стандартную эвристику, такую как евклидово расстояние. Это жадная оценка, которая предполагает, что прямой путь оптимален и для которого вы не можете добиться большего в идеальных условиях (это допустимо).
Для более чем одного пути жадный подход также говорит, что незаблокированный прямой путь между точками — это самый быстрый путь, который вы можете пройти. Кроме того, это по-прежнему последовательная эвристика, потому что вы не можете сделать шаг дальше и при этом получить лучший результат. Трудная часть состоит в том, чтобы выбрать, какой порядок M точек является самым быстрым без препятствий, чтобы поддерживать допустимую эвристику. Вы можете найти оптимальный выбор M точек в графе, где все плитки можно пройти по ширине, сначала найдя евклидово расстояние от вашей текущей плитки до каждой из M точек, до каждой из M-1 оставшихся точек, ..., до завершающий квадрат. Эта операция является дорогостоящей, так как вам нужно выполнять ее для каждого достигнутого квадрата, но вы можете использовать динамическое программирование или кэширование поиска, чтобы сократить требуемые амортизированные вычисления до O(M) за шаг.
Теперь, когда у вас есть пути из M точек, которые были бы самыми быстрыми без препятствий, вы можете использовать евклидово расстояние между каждой точкой этого пути и вашим текущим положением в качестве эвристики. Это жадная оценка движения, поэтому она всегда допустима (вы не можете превзойти оценочную стоимость) и непротиворечива, потому что вы не можете уйти от следующей жадной оптимальной точки и уменьшить свою стоимость, выбрав другую жадную точку из текущего тайла. было бы недопустимо.
Наконец, ваши критерии завершения должны измениться на достижение M точек, где последней точкой является завершающая плитка. Это имитирует ходячие M-графы без необходимости построения M! возможные графики для прогулки. Предоставленная эвристика позволит A* творить чудеса без изменения базового алгоритма и должна быть настолько эффективной, насколько это возможно, при сохранении требуемых ограничений эвристики на общих сетках.
person
Pyrce
schedule
17.04.2013
