Нахождение кратчайшего пути между двумя точками на сетке, использование Haskell
Это - проблема, которую я могу легко достаточно решить нефункциональным способом.
Но решение его в Haskell дает мне большие проблемы. Так как меня неопытен когда дело доходит до функционального программирования, конечно, причина.
Проблема:
Мне разделили 2D поле на прямоугольники равного размера. Простая сетка. Некоторые прямоугольники являются вакуумом (и может пройтись), в то время как другие непроходимы. Учитывая стартовый прямоугольник A и целевой прямоугольник B, как я вычислил бы кратчайший путь между двумя? Перемещение возможно только вертикально и горизонтально на шагах единственный большой прямоугольник.
Как я пошел бы о выполнении этого в Haskell? Фрагменты кода, конечно, добро пожаловать, но также и конечно не необходимые. И ссылки на дальнейшие ресурсы, также очень приветствующиеся!
Спасибо!
2 ответа
Я бы представил сетку в виде списка списков, введите [[Bool]] . И я бы определил функцию, чтобы узнать, заполнен ли элемент сетки:
type Grid = [[Bool]]
isFullAt :: Grid -> (Int, Int) -> Bool -- returns True for anything off-grid
Затем я бы определил функцию для поиска соседей:
neighbors :: (Int, Int) -> [(Int, Int)]
Чтобы найти неполных соседей точки , вы можете отфильтровать с фильтром (не isFullAt) $ neighbors point .
На этом этапе я бы определил две структуры данных:
- Сопоставить каждую точку с
Может быть Стоимость - Хранить все точки с известной стоимостью в куче
Инициализировать только с начальным квадратом в куче, с нулевой стоимостью.
Затем выполните следующий цикл:
- Удалите из кучи квадрат минимальной стоимости.
- Если его еще нет в конечной карте, добавьте его и его стоимость
cи добавьте всех неполных соседей в кучу со стоимостьюc + 1.
Когда куча пуста, у вас будет стоимость всех достижимых точек, и вы сможете найти B на конечной карте. (Этот алгоритм можно назвать «алгоритмом Дейкстры»; я забыл.)
Вы можете найти конечные карты в Data.Map . Я предполагаю, что где-то в обширной библиотеке есть куча (она же приоритетная очередь), но я не знаю где.
Надеюсь, этого достаточно, чтобы вы начали.
Что ж, ваши типы будут определять ваши алгоритмы.
Какой тип данных вы хотите использовать для представления сетки? Двумерный массив? Список списков? Дерево? Граф?
Если вам просто нужен кратчайший путь в ориентированном графе, лучше всего использовать что-нибудь из FGL (пакет функциональных графов).