Нахождение пути: SAT решение

Question

Нам дают n*m сетку, в которой есть препятствия в разных точках, в начальной и конечной локациях бота. Задача - найти путь без столкновений от начала до конца. Эта проблема должна быть смоделирована как проблема SAT.

Пожалуйста, объясните мне, что нужно сделать в этом случае, чтобы получить оптимальное решение.

Answer 1

Я бы предположил, что оптимальный означает самый короткий. Используя подход, который я описал здесь, вы можете сделать первые шаги:

1. определить сетку
2. сформулировать задачу выполнимости

На этом этапе решатель возвращает вам случайный путь, который удовлетворяет всем ограничениям. Важно помнить - вы можете определить количество шагов k, которые необходимы для достижения цели! Итак, вы просто начинаете с k = 0. Можно ли достичь цели с 0 действиями? Возможно, нет, пока агент уже не достиг цели. Тогда просто увеличьте k = 1. Возможно ли это сейчас? Если нет, увеличивайте больше! Как это реализовать? Просто установите все k выше определенного предела в False и увеличивайте этот предел каждую итерацию.

Если вы знаете верхние пределы, вы можете использовать бинарный поиск, чтобы найти кратчайший путь, который может быть более эффективным.

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