Domanda Trovare il percorso più breve tra due punti su una griglia, usando Haskell


Questo è un problema che posso facilmente risolvere in modo non funzionale.

Ma risolverlo in Haskell mi sta dando grossi problemi. Essere inesperto quando si parla di programmazione funzionale è sicuramente un motivo.

Il problema:

Ho un campo 2D diviso in rettangoli di uguali dimensioni. Una griglia semplice. Alcuni rettangoli sono spazi vuoti (e possono essere passati attraverso) mentre altri sono impraticabili. Dato un rettangolo di partenza UN e un rettangolo di destinazione B, come potrei calcolare il percorso più breve tra i due? Il movimento è possibile solo verticalmente e orizzontalmente, in passaggi di un singolo rettangolo di grandi dimensioni.

Come potrei fare per realizzare questo in Haskell? Snippet di codice sicuramente graditi, ma certamente non necessariamente necessari. E i link a ulteriori risorse sono anche i benvenuti!

Grazie!


10
2018-03-15 23:09


origine


risposte:


Rappresenterei la griglia come una lista di liste, tipo [[Bool]]. E definirei una funzione per sapere se un elemento della griglia è pieno:

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

Quindi definirei una funzione per trovare i vicini:

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

Per trovare vicini non pieni di point puoi filtrare con filter (not . isFullAt) $ neighbors point.

A questo punto, definirei due strutture dati:

  • Mappare ogni punto a Maybe Cost
  • Archivia tutti i punti con costo noto in un heap

Inizializza con solo il quadrato iniziale UN nell'heap, con costo zero.

Quindi loop come segue:

  • Rimuovi un quadrato a costo minimo dall'heap.
  • Se non è già nella mappa finita, aggiungila e il suo costo ce aggiungi tutti i vicini non pieni allo heap con un costo c+1.

Quando l'heap è vuoto, avrai i costi di tutti i punti raggiungibili e puoi cercare B nella mappa finita. (Questo algoritmo può essere chiamato "algoritmo di Dijkstra", ho dimenticato).

Puoi trovare mappe finite in Data.Map. Presumo che ci sia un mucchio (aka coda di priorità) da qualche parte nella vasta biblioteca, ma non so dove.

Spero che questo sia sufficiente per iniziare.


12
2018-03-16 01:02



Bene, i tuoi tipi determineranno i tuoi algoritmi.

Quale tipo di dati vuoi utilizzare per rappresentare la griglia? Un array bidimensionale? Una lista di liste? Un albero? Un grafico?

Se vuoi solo il percorso più breve in un grafico diretto, usare qualcosa dal FGL (pacchetto grafico funzionale) sarebbe il migliore.


3
2018-03-15 23:25