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

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

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

Проблема:

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

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

Спасибо!

Ответы

Ответ 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
  • Хранить все точки с известной стоимостью в куче

Инициализируйте только начальный квадрат A в куче, с нулевой стоимостью.

Затем выполните следующие шаги:

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

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

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

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

Ответ 2

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

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

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