Laufzeit A Stern < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:03 Fr 23.06.2006 | | Autor: | kuminitu |
Hallo,
ich beschäftige mich gerade mit dem Algorithmus A*(A Stern oder A star), weiss aber leider nicht, wie ich eine laufzeit angeben kann, bzw bin auch auf keine guten informationen im internet getroffen,
kann mir jemand bei diesem problem helfen?
MFG
kuminitu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:04 Sa 24.06.2006 | | Autor: | alexfr |
$ [mm] \mbox{Hallo} [/mm] $
$ [mm] \mbox{Der Aufwand von A\* ist sehr abhängig von der verwendeten Heuristik. Im worst case ist der Aufwand exponentiell, } [/mm] $
$ [mm] \mbox{jedoch polynomiell (} [/mm] O(n), [mm] O(n^2), O(n^3) \mbox{) , falls die Heuristik } [/mm] h [mm] \mbox{ folgende Eigenschaft erfüllt:} [/mm] $
$ | h(x) - [mm] h^{\*}(x) [/mm] | [mm] \le O(log(h^{\*}(x))) [/mm] $
$ [mm] h^{\*} \mbox{ ist die optimale Heuristik, also die exakten Kosten von } [/mm] x [mm] \mbox{ zum Ziel.} [/mm] $
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:36 Sa 24.06.2006 | | Autor: | kuminitu |
Hallo,
erstmal danke für die Antwort. habe aber noch zwei fragen:
warum hat der wost-case eine Exponentielle laufzeit? ist der worst-case nicht der fall dijkstra?(der hätte dann doch [mm] n^{2}logn, [/mm] oder?).
eine frage noch zu: [mm]| h(x) - h^{\*}(x) | \le O(log(h^{\*}(x)))[/mm]
kann man das irgendwie begründen oder gar beweisen, irgendwie ist mir das nicht schlüssig.
mfg
kuminitu
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:37 Sa 24.06.2006 | | Autor: | alexfr |
In der Tat lässt sich A* auf den Dijkstra-Algorithmus zurückführen, falls man die Heuristik weglässt, d.h. z.B. $ h(x) = 0 $. Für Probleme ohne Kosten bzw. mit Kosten, die für jeden Knoten identisch sind, entspricht der Dijkstra-Algorithmus einer einfachen Breitensuche, welche im worst case einen exponentiellen Aufwand hat.
Beim Beweis von $ | h(x) - [mm] h^{*}(x) [/mm] | [mm] \le O(log(h^{*}(x))) [/mm] $ bin ich leider etwas überfragt, vielleicht kann Dir hier ja jemand anderes dabei helfen.
|
|
|
|
