Лучший путь в сетке
У меня есть лучшая проблема пути, чтобы решить.
Учитывая nxn сетку, заполненную пригодными для прохода плитками и неприступаемыми плитками, я должен достичь точки B из точки A по кратчайшему пути.
Хитрость в том, что некоторые из проходных плиток содержат очки. Чтобы быть верным решением, когда я достигну цели, у меня должно быть определенное количество очков.
Плитки имеют различное количество точек (или их нет), и мне нужен кратчайший путь, чтобы достичь цели, но я также набрал как минимум М точек на пути.
Я попробовал алгоритм A *, который находит кратчайший путь между двумя точками и пытался настроить его так, чтобы он имел условие остановки не только тогда, когда он достигает цели, но также имел необходимые точки. Это не работает так, как я сделал, потому что я блокирую пути.
Если у вас есть какие-либо предложения по подходу к этой проблеме или другой алгоритм, который будет более подходящим, я был бы признателен за помощь.
Благодарю.
Решение
Если вы все еще застряли в этой проблеме, так как другие ответы / комментарии дают вам только частичный ответ — вот пробел в проблемном пространстве.
На самом деле вы можете использовать A * с несколькими модификациями для захвата (в основном) неупорядоченного пути точки M. Единственное, что вам нужно изменить, — это эвристический критерий и критерий завершения.
Сначала вам нужно изменить свою эвристику, чтобы учесть пути через M точек. Эвристика должна быть допустимой и последовательной, поэтому она должна равняться значению, меньшему или равному истинной стоимости пути, и может уменьшаться только по мере приближения к цели (должно быть монотонным увеличением).
Вы можете думать о пути, который вы сейчас выбираете, как о M подпутях, которые вы должны пройти, каждый из которых действует как обычный путь. Таким образом, для одного точечного графа (только с конечным пространством) вы можете использовать стандартную эвристику, такую как евклидово расстояние. Это жадная оценка, которая предполагает, что прямой путь является оптимальным, и для которого вы не можете добиться большего успеха в идеальных условиях (это допустимо).
Для более чем одного пути жадный подход также говорит о том, что прямой путь между точками без блокировки является самым быстрым, что вы можете пройти. Это также все еще последовательная эвристика, потому что вы не можете отойти еще дальше и при этом иметь лучший результат. Сложной частью является выбор того, какой порядок M точек является самым быстрым без препятствий для поддержания допустимой эвристики. Вы можете найти оптимальный выбор M точек на графике, где все плитки можно пройти по ширине, сначала просматривая евклидово расстояние от вашей текущей плитки до каждой из M точек, до каждой из M-1 оставшихся точек, …, чтобы завершающий квадрат. Эта операция стоит дорого, так как вам нужно делать это для каждого квадрата, которого вы достигнете, но вы можете использовать динамическое программирование или кэширование поиска, чтобы довести требуемые амортизированные вычисления до O (M) за шаг.
Теперь, когда у вас есть M точечных путей, которые будут самыми быстрыми без препятствий, вы можете использовать евклидово расстояние между каждой точкой на этом пути и вашим текущим положением в качестве эвристики. Это жадная оценка движения, поэтому она всегда допустима (вы не можете превзойти расчетную стоимость), и она последовательна, потому что вы не можете уйти от следующей жадной оптимальной точки и снизить свои затраты, потому что выбираете другую жадную точку из текущей плитки не будет допустимым.
Наконец, ваш критерий завершения должен измениться, чтобы достичь M точек, где последняя точка — это конечный элемент. Это имитирует ходячий M графиков без необходимости строить M! возможные графики для ходьбы. Предоставленная эвристика позволит A * творить чудеса без изменения базового алгоритма и должна быть максимально эффективной при сохранении необходимых ограничений на эвристику в общих сетках.
Другие решения
Вы можете добавить слои на свой график, когда вы находитесь на уровне глубины X -> вы собрали по крайней мере X точки. Добавьте соответствующие ребра на вашем графике от верхнего слоя к слою +N где N количество точек на текущем тайле
Ваш график бесконечен, но вы можете просто динамически добавлять номер слоя к дескриптору вершины, когда пересекаете какое-то ребро. И так как он бесконечен, вы не можете сказать, достижим ли финиш, но вы можете проверить, существует ли путь на базовом графе и есть ли хотя бы одна точка.
Вы должны поставить финиш на уровнях >M,
Если вам нужны пояснения, спросите =)
редактировать
Как сказал @Pyrce, вы также должны предоставить согласованную эвристику, если вы планируете использовать A * http://en.wikipedia.org/wiki/Consistent_heuristic