Что может быть хорошим пространством для собак, обнаруживающих проблему?

Question

Предположим, что у нас есть лабиринт M * N, а некоторые и что K собак в разных клетках этой лабиринта ищут свои дома (их уникальные дома также расположены в какой-то камере в лабиринте). на каждом этапе все собаки могут оставаться на своих местах или перемещаться в соседнюю клетку в лабиринте (допустимые движения: вверх, вниз, вправо, влево, если это возможно). что может быть хорошим пространством для этой проблемы?

• Уникальные дома означают, что у каждой собаки есть свой специфический c дом, расположенный где-то в лабиринте.

• Две собаки тоже могут стоять в одной камере.

Лично я считаю, что сумма манхэттенских расстояний для каждой собаки от ее дома может быть хорошей эвристикой c, но я мог бы Сам не могу определить хорошее пространство состояний.

Вот ссылка на изображение образца для k = 2 и лабиринта 5 * 5: Пример

Answer 1

Поскольку все животные независимы (они не блокируют друг друга и имеют уникальные индивидуальные цели), вам не следует моделировать совместные действия всех агентов. Вы действительно решаете K независимых задач поиска пути, где каждый из них может использовать манхэттенское расстояние heuristi c индивидуально, учитывая 4-связное движение. Если вы решаете их совместно, вы увеличиваете проблему в геометрической прогрессии, когда это не обязательно.

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