Encontrando o caminho mais curto entre dois pontos em uma grade, usando Haskell

Question

Esse é um problema que posso resolver o suficiente de uma maneira não funcional.

Mas resolvê -lo em Haskell está me dando grandes problemas. Eu sendo inexperiente quando se trata de programação funcional é certamente uma razão.

O problema:

Eu tenho um campo 2D dividido em retângulos de tamanho igual. Uma grade simples. Alguns retângulos são espaço vazio (e podem ser passados), enquanto outros são intransitáveis. Dado um retângulo inicial UMA e um retângulo de destino B, como eu calcularia o caminho mais curto entre os dois? O movimento é possível apenas vertical e horizontalmente, em degraus um único retângulo grande.

Como eu conseguiria realizar isso em Haskell? Os trechos de código certamente são bem -vindos, mas também certamente não são necessários. E links para outros recursos também muito bem -vindos!

Obrigado!

Answer 1

Eu representaria a grade como uma lista de listas, digite [[Bool]]. E eu definiria uma função para saber se um elemento de grade está cheio:

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

Então eu definiria uma função para encontrar vizinhos:

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

Para encontrar vizinhos não cheios de point você pode filtrar com filter (not . isFullAt) $ neighbors point.

Neste ponto, eu definiria duas estruturas de dados:

• Mapear cada ponto para Maybe Cost
• Armazene todos os pontos com custo conhecido em uma pilha

Inicialize apenas com o quadrado de partida UMA Na pilha, com custo zero.

Em seguida, faça um loop da seguinte maneira:

• Remova um quadrado de custo mínimo da pilha.
• Se ainda não estiver no mapa finito, adicione -o e seu custo c, e adicione todos os vizinhos não cheios à pilha com custo c+1.

Quando a pilha estiver vazia, você terá os custos de todos os pontos acessíveis e pode olhar para cima B no mapa finito. (Este algoritmo pode ser chamado de "algoritmo de Dijkstra"; eu esqueci.)

Você pode encontrar mapas finitos em Data.Map. Suponho que haja uma pilha (também conhecida como fila prioritária) em algum lugar da vasta biblioteca, mas não sei onde.

Espero que isso seja suficiente para começar.

Answer 2

Bem, seus tipos determinarão seus algoritmos.

Qual tipo de dados você deseja usar para representar a grade? Uma matriz bidimensional? Uma lista de listas? Uma árvore? Um gráfico?

Se você deseja apenas um caminho mais curto em um gráfico direcionado, o uso de algo do FGL (pacote de gráficos funcionais) seria o melhor.