A* negative Kanten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:09 Mo 26.07.2010 | | Autor: | Gilga |
Ich arbeite gerade an einer A* Heuristik für einen speziellen Graphen mit negativen Kanten.
Obwohl sehr oft erwähnt wird das der Alg. nicht für neg. Kantengewichte angewendet werden kann erscheint es mir aber möglich mit Komplexität [mm] O(n^2) [/mm] falls die Heuristik konsistent ist. (z.B. Heuristik = korrekte Entfernung zum Ziel)
Kann mir da jemand einen Literaturhinweis geben?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:58 Mo 26.07.2010 | | Autor: | Teufel |
Hi!
Ich weiß nicht genau, wie der A*-Algorithmus funktioniert, aber z.B. ist es beim Dijkstra so, dass es keine negativen Kanten geben darf, weil man den Weg ja dann beliebig billig machen kann (hat man eine negative Kante gefunden, kann man diese so lange hin und her abklappern, bis man den Preis beliebig klein gemacht hat). Ist das bei deinem Algorithmus vielleicht auch so?
![[anon]](/images/smileys/anon.png "[anon]") Teufel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:29 Di 27.07.2010 | | Autor: | Gilga |
Dies trifft nur auf negative Zyklen zu.
Man kann Dijkstra so implementieren dass er auch Graphen mit neg. Kanten ohne neg. Zyklen in exp. Zeit löst indem man verbesserte Knoten wieder in die priority queue einfügt.
(siehe A Note on {Dijkstra's} Shortest Path Algorithm, Johnson, 1973)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 26.08.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
