Kürzester Weg in einer ungerichteten Grafik?

Question

Also dachte ich, dass dies (obwohl etwas grundlegend) hier gehört:

Sagen Sie, ich habe ein Diagramm von 100 Knoten, die in einem 10x10 -Muster angeordnet sind (denken Sie an Schachbrett). Die Grafik ist ungerichtet und ungewichtet. Wenn Sie sich durch die Grafik bewegen, werden drei Felder vorwärts und einen Raum nach rechts oder nach links verschoben (ähnlich wie sich ein Schachritter über eine Platine bewegt).

Wie würde man bei einem festen Anfängerknoten den kürzesten Weg zu einem anderen Knoten auf der Platine finden?

Ich stellte mir vor, dass es nur eine Kante zwischen Knoten geben würde, die lebensfähige Bewegungen sind. Angesichts dieser Informationen möchte ich den kürzesten Weg von einem Startknoten zu einem Endknoten finden.

Mein erster Gedanke war, dass jede Kante mit Gewicht 1 gewichtet wird. Die Grafik ist jedoch ungerichtet, sodass Djikstras keine ideale Passform sein würde. Daher habe ich beschlossen, dies mit einer veränderten Form einer ersten Suche zu tun.

Ich konnte jedoch nicht für das Leben von mir visualisieren, wie ich mit der Suche den kürzesten Weg bekommen kann.

Eine andere Sache, die ich ausprobiert habe, war die Einstellung des Diagramms in Baumform mit dem Startknoten als Wurzel und dann das flachste (niedrigste Zeilenzahl) Ergebnis, das mir den gewünschten Endknoten gab ... das funktionierte, war aber unglaublich ineffizient und so und so Würde nicht für ein größeres Diagramm funktionieren.

Hat jemand Ideen, die mich in die richtige Richtung zeigen könnten?

Vielen Dank.

(Ich habe versucht, eine Visualisierung des Diagramms zu erstellen, war aber aufgrund meines geringen Rufs nicht in der Lage.)

Answer 1

Wenn die Kanten in der Grafschaft nur gültige Bewegungen zwischen bestimmten Positionen darstellen, würde die Verwendung von Dijkstra von dijkstra gut funktionieren. Da die Grafik jedoch ungewichtet ist, wäre es übertrieben. Eine einfache Breite zuerst die Suche gibt die optimale Antwort.

Answer 2

Nicholas gab bereits eine perfekte Antwort. Lassen Sie mich jedoch Ihren ursprünglichen Versuch ansprechen, die Tiefe-First-Suche zu verwenden.

Erstens entweder Dijkstra (was gut mit ungewichteten Knoten funktioniert, wie von Nicholas Mancuso angegeben) oder die Breite, die zuerst die Exponentialverschwendung Ihres Gedächtnisses entspricht. Ihr Vorteil ist jedoch, dass sie niemals Knoten erneut expandieren, während sie garantiert optimale Lösungen finden. Leider ist ihre Einschränkung sehr wichtig und sie sollten nicht angemessen erwartet werden.

Wenn Sie große Instanzen Ihres Problemgebrauchs lösen möchten Iterativen Tiefe-First-Tiefe Suche (IDFS). Geben Sie einfach eine Tiefensuche von Ihrem Startzustand mit einer maximalen Tiefe auf einen bestimmten Schwellenwert, $ d_ {max} $ aus. Wenn Sie die Lösung nicht gefunden haben, erhöhen Sie die Tiefe der letzten Iteration durch einen festen konstanten $ k $. In der Iteration $ i $ -TH wird also eine Tiefensuche in der Tiefe $ d_ {max} + i mal k $ gestartet (wobei die erste Iteration 0 nummeriert ist). Wenn $ d_ {max} = k = 1 $ $ dann ist garantiert, dass Sie die optimale Lösung finden, während Sie in der Tiefe der Lösung den Speicher linear verwenden.

Nun, Sie denken vielleicht, dass es eine eher schlechte Idee ist, Knoten wieder zu erweitern. Gar nicht! Dies garantiert einen linearen Speicherverbrauch, während die Iteration, die die Gesamtlaufzeit dominiert B $ ist der effektive Verzweigungsfaktor, und dies ist eindeutig eine sehr kleine Strafe, die bei schweren Problemen berücksichtigt wird.

Prost,