Den kürzesten Pfad zwischen zwei Punkten auf einem Gitter finden, mit Haskell

Question

Dies ist ein Problem, das ich leicht genug in einer nicht funktionalen Weise lösen kann.

Aber die Lösung in Haskell gibt mir große Probleme. Ich bin unerfahren, wenn es um funktionale Programmierung geht, ist sicherlich ein Grund.

Das Problem:

Ich habe ein 2D-Feld in Rechtecken gleicher Größe unterteilt. Ein einfaches Gitter. Einige Rechtecke sind leerer Raum (und können durchgelassen werden), während andere unpassierbar sind. Gegeben ein Startrechteck A und ein Zielrechteck B, wie würde ich den kürzesten Weg zwischen den beiden berechnen? Bewegung ist nur vertikal und horizontal möglich, in Schritten ein einzelnes Rechteck groß.

Wie würde ich dies in Haskell erreichen? Codefragmente sind sicherlich willkommen, aber auch nicht unbedingt notwendig. Und Links zu weiteren Ressourcen sind ebenfalls sehr willkommen!

Danke!

Answer 1

Ich würde das Raster als Liste von Listen darstellen, geben Sie [[Bool]] ein. Und ich würde eine Funktion wissen definieren, ob ein Gitterelement ist voll:

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

Dann würde ich eine Funktion definieren Nachbarn zu finden:

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

Um nicht voll Nachbarn von point finden Sie kann mit filter (not . isFullAt) $ neighbors point filtern.

An diesem Punkt habe ich zwei Datenstrukturen definieren würde:

• jeden Punkt Karte zu Maybe Cost
• Shop alle Punkte mit bekannten Kosten in einem Haufen

initialisieren nur mit dem Startfeld A im Heap, mit Kosten Null.

Dann Schleife wie folgt:

• Entfernen eines min-Cost-Platz aus dem Haufen.
• Wenn es nicht bereits in der endlichen Karte ist, fügen Sie es und seine Kosten c hinzu, und fügen Sie dem Heap alle nicht vollständigen Nachbarn mit Kosten hinzu.

Wenn der Heap leer ist, werden Sie die Kosten aller erreichbaren Punkte haben und B in der Finite-Karte nachschlagen kann.(Dieser Algorithmus kann "Dijkstra-Algorithmus" genannt werden; ich habe vergessen.)

Sie können finite Karten in Data.Map finden. Ich nehme an, es gibt irgendwo in der riesigen Bibliothek einen Haufen (auch Prioritätswarteschlange genannt), aber ich weiß nicht wo.

Ich hoffe, das ist genug, um Sie zu beginnen.

Answer 2

Nun, Ihre Typen werden Ihre Algorithmen bestimmen.

Welchen Datentyp möchten Sie zur Darstellung des Rasters verwenden? Ein zweidimensionales Array? Eine Liste von Listen? Ein Baum? Ein Graph?

Wenn Sie nur den kürzesten Pfad in einem gerichteten Graphen möchten, wäre die Verwendung von etwas aus dem FGL (Functional Graph Package) am besten.