Dijkstra-Algorithmus Vs Uniform Cost Search (Zeitkomplexität)

Question

Meine Frage ist wie folgt: Dijkstra-Algorithmus ist nach verschiedenen Quellen nichts anderes als eine Variante der Uniform Cost Search. Wir wissen, dass der Dijkstra-Algorithmus den kürzesten Pfad zwischen einer Quelle und allen Zielen (Single-Source) findet. Wir können Dijkstra jedoch immer modifizieren, um den kürzesten Pfad zwischen einem START- und einem GOAL-Zustand zu finden (wenn das Ziel aus der Prioritätswarteschlange abgerufen wird, halten wir einfach an); Aber im schlimmsten Fall wird immer noch der kürzeste Pfad von START zu allen anderen Knoten gefunden (angenommen, das Ziel ist der am weitesten entfernte Knoten im Graphen).

Wenn wir den Dijkstra-Algorithmus mit einem Min-priority-Heap implementieren, ist die Laufzeit O (V log V + E), wobei E die Anzahl der Kanten und V die Anzahl der Ecken ist.

Da Uniform Cost Search dasselbe ist wie Dijkstra (etwas andere Implementierung), dann sollte die Laufzeit von UCS Dijkstra ähnlich sein, nicht wahr? Gemäß meiner AI-Klasse ist die Suche nach einheitlicher Kosten jedoch im schlechtesten Fall exponentiell und es dauert O (b ^{1 + [C */& epsi;]}), wobei C * die Kosten der optimalen Lösung sind. (b ist der Verzweigungsfaktor)

Wie können beide Algorithmen bei unterschiedlichen Laufzeiten gleich sein? Ist die Laufzeit gleich, aber die Art, wie wir sie betrachten, ist anders?

würde ich Ihre Hilfe :) schätzen :) Danke

Answer 1

Ist die Laufzeit gleich, aber die Art, wie wir es betrachten ist anders?

Ja. Die einheitliche Kostensuche kann für unendlich große Graphen verwendet werden, auf denen Dijkstras ursprünglicher Algorithmus niemals enden würde. In solchen Situationen ist es nicht sinnvoll, die Komplexität in Bezug auf und E zu definieren, da beide unendlich sein können und die resultierende große O-Zahl bedeutungslos ist.