Die zeitliche Komplexität von Backtracking -Algorithmen ist im Allgemeinen exponentiell , speziell oft als o (b^d) ausgedrückt , Wo:

* b ist der Verzweigungsfaktor (die Anzahl der möglichen Entscheidungen an jedem Entscheidungspunkt).

* d ist die Tiefe des Suchbaums (die maximale Anzahl von Entscheidungen, die getroffen werden müssen, um eine Lösung zu erreichen).

Erläuterung:

Backtracking untersucht alle möglichen Lösungen, indem eine Kandidatenlösung voneinander systematisch aufgebaut wird. Bei jedem Schritt prüft es, ob der aktuelle Kandidat vielversprechend ist (d. H. Wenn er möglicherweise zu einer gültigen Lösung führen könnte). Wenn der Kandidat vielversprechend ist, untersucht der Algorithmus die weiteren Entscheidungen rekursiv. Wenn der Kandidat nicht vielversprechend ist (eine "Sackgasse"), ist der Algorithmus * zurück zum vorherigen Schritt und versucht eine andere Wahl.

Da der Algorithmus einen Baum mit Möglichkeiten erforscht und die Anzahl der Zweige schnell wachsen kann, kann die zeitliche Komplexität sehr groß werden, insbesondere wenn die Tiefe von D` steigt.

Warum exponentiell?

Stellen Sie sich das wie eine Baumsuche vor. Wenn jeder Knoten im Baum `B` Kinder (Verzweigungsfaktor` b`) hat und die maximale Tiefe des Baumes `D` ist, können Sie im schlimmsten Fall möglicherweise alle" B^D` -Knoten "untersuchen.

Wichtige Überlegungen:

* Worst-Case-Szenario: Die Zeitkomplexität von O (b^d) ist typischerweise ein * Worst-Case * -Szenario. Die tatsächliche Laufzeit hängt stark von dem Problem und der Wirksamkeit des Beschneidung ab (wie effektiv der Algorithmus identifizieren und vermeiden kann, nicht vergleichbare Zweige zu untersuchen).

* Beschneidung: Gute Backtracking -Algorithmen verwenden verschiedene Schnitttechniken, um den Suchraum erheblich zu reduzieren. Das Beschneiden kann die Laufzeit drastisch verbessern, aber es ändert nicht die inhärente exponentielle Natur des Algorithmus im schlimmsten Fall.

* Beispiel: Ein klassisches Beispiel ist das Lösen des N-Queens-Problems. Um N -Queens auf ein NXN -Schachbrett zu platzieren, bezieht sich der Verzweigungsfaktor mit der Anzahl der verfügbaren Spalten in einer Reihe, und die Tiefe bezieht sich auf die Anzahl der Zeilen. Die schlimmste Zeitkomplexität wird durch Überprüfung von Konflikten (angreiferen Königinnen) bei jedem Schritt erheblich verringert, was viele der potenziellen Zweige beschränkt.

* Andere Faktoren: Neben "B" und "D" können andere Faktoren die Laufzeit beeinflussen. Zum Beispiel kann die Zeit, die benötigt wird, um zu bewerten, ob eine Kandidatenlösung vielversprechend ist, auch ein wesentlicher Faktor sein.

* NP-Vervollständigung: Viele Probleme, die mit Backtracking gelöst werden, sind NP-Complete. Dies bedeutet, dass es angenommen wird, dass es keinen Polynom-Zeit-Algorithmus gibt, um sie im Allgemeinen zu lösen, und Backtracking wird häufig zu einem notwendigen (wenn auch manchmal ineffizienten) Ansatz.

Zusammenfassend:

Während Backtracking eine leistungsstarke Problemlösungstechnik sein kann, bedeutet die Komponität der exponentiellen Zeit, dass sie am besten für Probleme geeignet ist, bei denen:

* Die Problemgröße ist relativ klein.

* Effektive Schnittstrategien können angewendet werden, um den Suchraum erheblich zu reduzieren.

* Eine ungefähre Lösung ist akzeptabel, wenn die genaue Lösung zu zeitaufwändig ist, um zu finden.

Wenn Ihr Problem groß ist und das Beschneiden unwirksam ist, müssen Sie möglicherweise alternative Algorithmen oder Annäherungstechniken in Betracht ziehen.