Поиск кратчайшего пути между двумя точками на сетке, используя Haskell

Question

Это проблема, которую я могу легко решить не функциональным способом.

Но решение этого вопроса в Haskell дает мне большие проблемы. Разумеется, я неопытна, когда речь заходит о функциональном программировании.

Проблема:

У меня есть 2D поле, разделенный на прямоугольники одинакового размера. Простая сетка. Некоторые прямоугольники являются пустым пространством (и могут быть пропущены), а другие непроходимы. Учитывая начальный прямоугольник A и прямоугольник назначения B, как бы рассчитать кратчайший путь между ними? Движение возможно только по вертикали и по горизонтали, по шагам - один прямоугольник большой.

Как я мог бы выполнить это в Haskell? Фрагменты кода, безусловно, приветствуются, но также, безусловно, не обязательно. И ссылки на дополнительные ресурсы также очень приветствуются!

Спасибо!

Answer 1

Я бы представил сетку в виде списка списков, типа [[Bool]]. И я бы определить функцию, чтобы знать, если элемент сетки полон:

type Grid = [[Bool]] 
isFullAt :: Grid -> (Int, Int) -> Bool -- returns True for anything off-grid 

Тогда я бы определить функцию для поиска соседей:

neighbors :: (Int, Int) -> [(Int, Int)] 

Чтобы найти неполноэкранные сосед point вы может фильтровать с filter (not . isFullAt) $ neighbors point.

На данный момент я бы определить две структуры данных:

• переводящих точку Maybe Cost
• магазин все точки с известной стоимостью в куче

Initialize только с начальной площади A в куче, с нулевой стоимостью.

Затем цикл следующим образом:

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

Когда куча пуста, вы будете иметь расходы всех достижимых точек и может искать B в конечной карте.(Этот алгоритм можно назвать «алгоритмом Дейкстры», я забыл.)

Вы можете найти конечные карты в Data.Map. Я предполагаю, что в огромной библиотеке есть куча (ака приоритетная очередь), но я не знаю, где.

Надеюсь, этого достаточно, чтобы вы начали.

Answer 2

Ну, ваши типы будут определять ваши алгоритмы.

Какой тип данных вы хотите использовать для представления сетки? Двумерный массив? Список списков? Дерево? Граф?

Если вам нужен только самый короткий путь в ориентированном графе, лучше всего использовать что-то из FGL (функциональный пакет графа).