Я сделал решатель C ++, который слишком длинный (187 строк), чтобы поместиться здесь удобно, поэтому вместо этого я поместил его в pastebin: http://pastebin.com/3G4dfTjR. Программа либо вычисляет оптимальное (минимально возможное количество ходов)) решение или сообщает, что ничего не возможно.
Использование
Запустите программу как racetrack startX startY goalX goalY [circleX circleY radius] .
В программе предполагается, что сетка 100x100 может содержать одно круговое препятствие, центр и радиус которого вы укажете.Вы должны дополнительно указать начальное местоположение автомобиля и местоположение одной цели.Хотя эти ограничения несколько ограничивающие, при взгляде на код должно быть очевидно, что они не ограничивают алгоритм в целом - вся соответствующая логика инкапсулирована в подпрограммах isMoveValid() и isGoalState(), поэтому, если кто-то можетНадоело реализовывать более общие версии этих подпрограмм (например, позволяя пользователю указывать битовую карту местоположений сетки и / или разрешать множественные местоположения целей), тогда это может быть включено без затруднений.
Единственное небольшое осложнение будет вполучить целевое местоположение, которое будет таким же (или близко, но «на другой стороне») от стартового местоположения, что вам нужно, если вы хотите, чтобы ваш трек был трассой.В этом случае, чтобы избежать того, чтобы решатель просто развернул автомобиль или сразу же остановился, вам нужно указать невидимую «стартовую линию» и изменить isMoveValid(), чтобы запретить «обратные» движения по этой линии.
Как это работает
Поскольку каждый шаг стоит ровно 1, можно использовать поиск в ширину в пространстве состояний 4D, чтобы найти оптимальное решение.Всякий раз, когда мы посещаем данное состояние s, которое состоит из 4-х кортежей (x, y, dx, dy), где dx и dy являются вектором скорости, который мы использовали для получения (x, y), мы рассматриваем все 9 состояний, которые мыможно добраться от с одним движением.Для любого такого состояния t, которое еще не было замечено, этот путь к t (то есть через s) гарантированно будет оптимальным, поскольку BFS всегда посещает узлы в порядке их минимального расстояния от корня.Всякий раз, когда мы определяем оптимальный путь для состояния, мы записываем состояние предшественника, позволяя в конце создать трассировку полного пути.
BFS проще и, следовательно, быстрее, чем алгоритм Дейкстры или A* поиск, которые являются более общими алгоритмами, которые позволяют перемещениям иметь различные затраты - гибкость, которая нам здесь не нужна.A * может быть быстрее, если существует несколько препятствий, мешающих его эвристике, но на каждом этапе ему нужно искать узел с минимальными затратами, что обычно выполняется с использованием кучи, тогда как для BFS узел с минимальными затратами всегда доступен вначало очереди.
Примеры
беговая дорожка секундомера 30 3 90 10
Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
No obstacle.
11-step solution:
(90, 10) (dx=10, dy=4)
(80, 6) (dx=9, dy=3)
(71, 3) (dx=8, dy=2)
(63, 1) (dx=7, dy=1)
(56, 0) (dx=6, dy=0)
(50, 0) (dx=5, dy=0)
(45, 0) (dx=5, dy=0)
(40, 0) (dx=4, dy=0)
(36, 0) (dx=3, dy=-1)
(33, 1) (dx=2, dy=-1)
(31, 2) (dx=1, dy=-1)
(30, 3) (dx=0, dy=0)
128113 states were examined in the process.
stopwatch: Terminated. Elapsed time: 343ms
stopwatch: Process completed with exit code 0.
беговая дорожка секундомера 30 3 90 10 5020 25
Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
A circular obstacle of radius 25 is centred at (50, 20).
22-step solution:
(90, 10) (dx=5, dy=-8)
(85, 18) (dx=5, dy=-7)
(80, 25) (dx=4, dy=-6)
(76, 31) (dx=4, dy=-5)
(72, 36) (dx=5, dy=-4)
(67, 40) (dx=6, dy=-3)
(61, 43) (dx=7, dy=-2)
(54, 45) (dx=8, dy=-1)
(46, 46) (dx=7, dy=0)
(39, 46) (dx=6, dy=1)
(33, 45) (dx=5, dy=2)
(28, 43) (dx=4, dy=3)
(24, 40) (dx=3, dy=4)
(21, 36) (dx=2, dy=5)
(19, 31) (dx=1, dy=6)
(18, 25) (dx=0, dy=6)
(18, 19) (dx=-1, dy=5)
(19, 14) (dx=-2, dy=4)
(21, 10) (dx=-3, dy=3)
(24, 7) (dx=-3, dy=2)
(27, 5) (dx=-2, dy=1)
(29, 4) (dx=-1, dy=1)
(30, 3) (dx=0, dy=0)
949565 states were examined in the process.
stopwatch: Terminated. Elapsed time: 3076ms
stopwatch: Process completed with exit code 0.
Обратите внимание на то, как оптимальное решение здесь сначала должно «двинуться назад», подняться вверх и снова, а затем снова вниз, так как круговое препятствие простирается до самого днаgrid.
Небольшая ошибка: код, который был опубликован, даст короткий (но ненулевой!) ответ, если вы установите цель цели равной начальной позиции.Очевидно, что это можно проверить как особый случай, но я уже поместил код на pastebin, когда понял, что это ...:)