Den kürzesten Weg in einem Labyrinth finden

Question

Ich bin Amateur-Programmierer lernen, wie man programmiert. Ich habe nie irgendwelche Informatik Kurse hatte so ich harte Zeiten mit diesem trivialen Problem habe:

class Room { 
    String name; 
    ArrayList<Room> neighbors = new ArrayList<Room>(); 

    // constructor with name 
    // getters 
    void addNeighbor(Room room) { 
     neighbors.add(room); 
    } 
} 

class Finder { 
    void findShortestPath(Room start, Room end) { 
     // ? 
    } 
} 

Jedes Zimmer einige Nachbarn hat. Mehr als 4, also kein matrixorientiertes Problem. Sie erhalten einen End-Raum und Sie müssen den kürzesten Weg vom Startraum finden (Vergleich der Namen der Räume). Ergebnis sollte "Art und Weise" wie:

Start: Küche

Ende: WC

Pfad: Küche, Wohnzimmer, Flur, Schlafzimmer, WC

Ich glaube, ich muss einige Rekursion verwenden für die Räume und ich denke ich sollte sparen wo ich schon in einem Stapel war. Aber ich weiß nicht wirklich, wie ich anfangen soll.

Können mir einige CS Jungs helfen? Danke

Answer 1

Sie suchen nach BFS.

In Ihrem Fall der Graph G = (V,E) ist eigentlich V= { all rooms } und E = {(u,v), (v,u) | u and v are neighboring rooms }

Beachten Sie, dass Sie nicht, dass Sie kümmern sich nicht alle Kanten haben [Nachbarn], bevor der Algorithmus beginnt - Sie wissen, wie das entsprechende Set berechnen von Kanten [und Räumen] im laufenden Betrieb mit dem Feld neighbors.
Dies ist richtig, da jede "Kante", die Sie für Ihren Pfad verwenden müssen, "entdeckt" wurde, als Sie den Raum entdeckten, der näher am Pfad zur Quelle liegt.

Sie können sehen this post - wie Sie den tatsächlichen Pfad nach dem Ausführen eines BFS finden können.

Answer 2

Sie möchten eine Breitensuche erstellen. Zu diesem Thema sind viele Ressourcen verfügbar.