www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast! [ einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - A* negative Kanten
A* negative Kanten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

A* negative Kanten: Frage (überfällig)
Status: (Frage) überfällig Status 
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?
        
Bezug
A* negative Kanten: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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] Teufel
Bezug
                
Bezug
A* negative Kanten: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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)
Bezug
        
Bezug
A* negative Kanten: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:20 Do 26.08.2010
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]