BFS-Algorithmus - kürzester Weg auf Gitter mit eingeschränkten Schritten

Question

Das Problem ist wie folgt: Ein Wanderer beginnt auf den Gitterkoordinaten (x, y) und will die Koordinaten (0,0) erreichen. Von jedem Gitterpunkt aus kann der Wanderer 8 Schritte nach Norden ODER 3 Schritte nach Süden ODER 5 Schritte nach Osten ODER 6 Schritte nach Westen (8N/3S/5E/6W) gehen.

Wie kann ich die kürzeste Route von (X, Y) nach (0,0) mit der Breitensuche finden?

Clarifications:

• unbegrenzt grid
• Negative Koordinaten
• Eine Warteschlange sind erlaubt (verknüpfte Liste oder eines Arrays) sind
• keine Hindernisse vorhanden

Answer 1

Ich werde weitermachen und meine eigene Frage für die Zukunft zu beantworten.

Psuedocode:

while (true) { 
    if (destination reached) 
     break; 
    addToQueue(go north); 
    addToQueue(go south); 
    addToQueue(go east); 
    addToQueue(go west); 
    getNextFromQueue; 
} 

Es sollte auch, dass die Ausführungszeit wächst sehr für diese Anwendung festgestellt werden, sehr schnell, so testen Sie es aus mit kleinen Werten koordinieren. Zum Beispiel ergeben die Koordinaten (1,1) 7 Ebenen von Breite und erfordern 16384 Iterationen.

Answer 2

Der Algorithmus verwendet werden, Dieses Problem wäre:

Für jede Achse Schritt in diese Richtung, bis Ihre Position auf der anderen Achse ist 0.

Pseudocode:

while (x!=0) { 
    if (x>0) x-=6; 
    else x+=5; 
} 
while (y!=0) { 
    if (y>0) y-=8; 
    else y+=3; 
} 

Aber ich verstehe nicht, warum Sie nach einer Route suchen müssen - es ist nicht das ist, kompliziert.

Answer 3

Wie "thejh" bemerkte, gibt es keine Notwendigkeit für eine Suche, aber Ihre Aufgabe erfordert eine.

Ein sinnvoller Ansatz ist

1. analysieren. Ist alles möglich für beliebige (x, y) Startposition? Wenn Sie die erlaubten Bewegungen überprüfen, sehen Sie, dass sie kombiniert werden können, um horizontale Ein-Schritt-Bewegungen und vertikale Ein-Schritt-Züge zu erzielen. Die Antwort darauf ist ja (Ihr Hand-in liefert die Details dazu).

2. Herauszufinden, was "Breitensuche" ist. Wikipedia ist dein Freund (obwohl, wenn du Zugang zu einer Universitätsbibliothek hast, empfehle ich wirklich Patrick Henry Winstons altes Artifical Intelligence, es sind wirklich gute, sehr klare Erklärungen). Probieren Sie es mit einem einfacheren Problem aus.

3. Führen Sie das Problem in etwa auf die gleiche Weise aus. Fragen Sie hier, wenn Sie auf ein technisches C++ - Problem stoßen.

Beifall & hth.,

Answer 4

Hier ist meine Antwort (wirklich basiert weg Antwort von thejh ist), die eine Warteschlange verwendet:

//set x to start position 
//set y to start position 
do { 
    if (x<0) Queue.Push(8N); 
    if (x>0) Queue.Push(3S); 
    if (y<0) Queue.Push(5E); 
    if (y>0) Queue.Push(6W); 
    while (!Queue.Empty()) 
    { 
    Move(Queue.Pop()); 
    } 
} while (x && y); 

Es ist gewunden, sondern folgt den Anweisungen.