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

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

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

Эта проблема:

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

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

Спасибо!

Источник

2 ответа

Решение

Я бы представил сетку в виде списка списков, введите [[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, Я предполагаю, что где-то в обширной библиотеке есть куча (приоритетная очередь), но я не знаю, где.

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

Источник

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

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

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

Источник
Другие вопросы по тегам