Как нечистить алгоритм A * для поддержки многопользовательского поиска в лабиринте

Question

Если у меня есть функция A *, которая поддерживает поиск оптимального пути от начальной точки до цели в лабиринте, как мне изменить эвристическую функцию допустимо, так что если есть несколько целей, функция все равно возвращает оптимальный результат.

Answer 1

Предполагая, что проблема посетить только одну цель:

Первое решение, которое приходит на ум в цикле по всем возможным целям, вычислить допустимую эвристическое значение для каждого из них, а затем, наконец, вернуть минимум этих значений в качестве окончательной эвристической ценности. Таким образом, вы уверены, что эвристика все еще допустима (не переоценивает расстояние до любой цели).

EDIT: Теперь если предположить, что проблема посетить все цели:

В этом случае А * может даже не обязательно наилучший алгоритм для использования. Вы можете использовать A * с эвристикой, как описано выше, чтобы сначала найти кратчайший путь к ближайшей цели. Затем, достигнув первой (ближайшей) цели, вы можете запустить ее снова таким же образом, чтобы найти ближайшую ближайшую цель и т. Д.

Но это может не дать оптимального общего решения. Возможно, что сначала полезно посетить вторую ближайшую цель (например), потому что в некоторых случаях это может позволить более дешевый путь последующей передачи к второй цели.

Если вы хотите оптимальное общее решение, вы, вероятно, захотите взглянуть на другой общий подход. Ваша проблема будет похожа на Travelling Salesman Problem (хотя это не совсем то же самое, так как я думаю, что вам разрешено посещать одну и ту же точку несколько раз, например). Этот link также может вам помочь.