Shortest Path: Preprocessing

Moderator: Effiziente Graphenalgorithmen

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Shortest Path: Preprocessing

Beitrag von David »

Hallo!

Kann mir vielleicht mal jemand in eigenen Worten beschreiben, was beim Preprocessing genau passiert. Ich verstehe die Aussagen auf Folie 135 nicht so richtig.

Vielen Dank!

David

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Shortest Path: Preprocessing

Beitrag von Stille »

Keiner sonst? Also, die Idee ist, auf einem reduzierten Graphen schneller kürzeste Wege zu finden. Dazu merkt man sich für jede Kante diejenigen Knoten, zu denen ein kürzester Weg, der diese Kante benutzt, führt. Nun reicht es aus, der Suche einen Graphen zugrunde zu legen, der nur noch aus Kanten a besteht, für die gilt, daß sich der Zielknoten in deren Container C(a) befindet.

Analog dazu könnte man Kanten "taggen", z.B. mit geometrischer Information versehen. Angenommen man zerlegt den Graphen z.B. in Quadranten, so weiß man, daß man, um von einem Knoten mitten im links unteren Quadranten zu einem Knoten mitten im links oberen Quadranten zu gelangen, Kanten aus den beiden rechten Quadranten nicht betrachten muß.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Re: Shortest Path: Preprocessing

Beitrag von David »

Danke für die Antwort. Habs jetzt verstanden.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“