Wegfindung (sehr einfach)
-
Ähm richtig, ich wollte es umgekehrt sagen.
-
Wobei es natürlich genial wäre auch eine Funktion zu haben, die eine möglichst gute obere Schranke für den kürzesten Weg abgibt.
Bye, TGGC
-
Follow the mighty ant.
-
TGGC schrieb:
Wobei es natürlich genial wäre auch eine Funktion zu haben, die eine möglichst gute obere Schranke für den kürzesten Weg abgibt.
Bye, TGGC
Tja, bei n * n Knoten n^2 und jeden Knoten gehen(ist natürlich nicht die beste Abschätzung)
-
Das ist im Allgemeinen keine gültige obere Schranke. Es gibt auch unendlich lange Wege.
Bye. TGGC
-
Ja Theoretisch, aber praktisch wirst du keine Kreise einbauen!
Und Kreise sind nötig um bei endlich vielelen Knoten einen unendlich langen weg zu erzeugen. Außerdem ist dann auch die Summe der "Kosten" der Kanten unendlich, was ja nicht besonder wirlichkeitsnah ist.
-
Und außerdem verbietet A* und Dijkstra Kreise! Also ist es ne obere Schranke!
-
Erstens braucht man eine möglichst günstige obere Schranke, also einen Wert, der den tatsächlichen Weg nicht wahnsinnig (am besten gar nicht) überschätzt, denn die Qualität des gefundenen Weges leidet darunter. Man kann auch leicht einsehen, dass diese Methode meistens überschätzt. Der Weg, den du so bekommst, ist also unbrauchbar.
Zweitens sind Kreiswege keineswegs "verboten", sie werden von den Algorithmen nur nicht erstellt. Wie du aber deine Heuristik so aufbaust, ist u.U. nicht trivial. Nicht zuletzt ist ein Weg auch unendlich lang, wenn es keine Verbindung gibt.
-
Hey Optimizer du hast recht und ich meine Ruhe.
-
Eigentlich habt ihr doch beide recht. Dijkstra & Co. bauen keine Kreiswege (aber nur, wenn's keine 0/negative Kosten gibt) und außerdem braucht man natürlich nen Kreis, um nen unendlich langen Weg zu bauen (Schubfachprinzip).
Das einzige, was mich wundert, warum immer noch über obere Schranken spekuliert wird. A* ist optimal, aber nur wenn die Schranke nie nie nie überschätzt. Umso näher er dran ist, umso schneller ist der Algorithmus. Die obere Schranke bringt imho nicht so viel.
-
MisterX schrieb:
Hey Optimizer du hast recht und ich meine Ruhe.
Ui, habe ich dich angepisst? Ich wollte dich doch nur darauf hinweisen, dass von einem beliebigen Knoten aus "jeden Knoten gehen" (wie von dir vorgeschlagen) den Gesamtweg fast immer überschätzt (nämlich immer dann, wenn man nicht alle Knoten abgehen muss). Und wir haben doch gerade über die Heuristik gesprochen, da du TGGC zitiert hast. Zusammen mit
Jester schrieb:
A* ist optimal, aber nur wenn die Schranke nie nie nie überschätzt.
ergibt sich, dass bei "jeden Knoten gehen" als Heuristik meistens nicht mehr der optimale Weg gefunden wird.
-
@Jester:
Man könnte sich aber einen sehr effizienten Algorithmus ausdenken, der mit einer oberen Schranke für die Weglänge arbeitet. Das wäre noch nichtmal so schwer. Nur erreicht so eine Algorithmus nie große Popularität, weil man keine guten oberen Schranken finden kann.Bye, TGGC
-
Hm, beschreib mal den Algorithmus näher. Ich kann mir im Moment nicht so richtig vorstellen, wie der schön schnell werden soll.
Eine obere Schranke könnte man gewinnen, indem man zunächst mal nen minimalen Spannbaum erstellt. Das geht einfach und schnell und kann auch vorberechnet werden. Dann gibt es von jedem Knoten A zu jedem Knoten B genau einen Weg im minimalen Spannbaum. Der Weg müßte sich leicht finden lassen, seine Länge wäre dann ne obere Schranke.
-
Optimizer schrieb:
MisterX schrieb:
Hey Optimizer du hast recht und ich meine Ruhe.
Ui, habe ich dich angepisst? Ich wollte dich doch nur darauf hinweisen, dass von einem beliebigen Knoten aus "jeden Knoten gehen" (wie von dir vorgeschlagen) den Gesamtweg fast immer überschätzt (nämlich immer dann, wenn man nicht alle Knoten abgehen muss). Und wir haben doch gerade über die Heuristik gesprochen, da du TGGC zitiert hast. Zusammen mit
Jester schrieb:
A* ist optimal, aber nur wenn die Schranke nie nie nie überschätzt.
ergibt sich, dass bei "jeden Knoten gehen" als Heuristik meistens nicht mehr der optimale Weg gefunden wird.
Diese Antwort stammt nicht von mir "der originale MisterX"
