Unterschied zwischen...

Moderator: Effiziente Graphenalgorithmen

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Unterschied zwischen...

Beitrag von Dreamdancer »

... zwischen der lower bound beim Goal Directed Search (F.128) und der zulässigen Abschätzung (admissible estimate) auf S. 129 bei der A*-Search.

Also A*-Search ist sicher eine Goal-Directed-Search, auf F. 129 wird aber ausdrücklich darauf hingewiesen, dass die zulässige Abschätzung gemeint ist und KEINE untere Schranke.

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

Re: Unterschied zwischen...

Beitrag von Stille »

Lower Bounds sind ein "admissible estimate". Gemeint ist hier, daß nicht notwendigerweise euklidische Distanzen benutzt werden müssen, sondern jeder beliebige Unterschätzer verwendet werden kann (z.B. auch 0), der natürlich immer einen lower bound für die Kürzesten-Wege-Distanzen darstellt. Folie 129 ist da zugegebenermassen etwas unpräzise.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Unterschied zwischen...

Beitrag von Dreamdancer »

Also ich würde das dann für mein Gedächtnis so abspeichern: "Admissible estimates" sind ja mathematisch gesehen untere Schranken auf die tatsächliche Distanz/tatsächlichen Kosten, damit sind untere Schranken zwar auch admissible estimates, aber untere Schranken zaubert man ja nicht aus dem Hut, das ist ja ein sehr abstrakter Begriff. Deshalb würde ich die beiden Sachen als Synonym verwenden, das eine aus der Mathematik stammend, dass andere aus der Algorithmik und euklidische Distanz nur eine von vielen möglichen Distanzen ist, die diese Forderung erfüllen.
Sage ich da was falsches?

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

Re: Unterschied zwischen...

Beitrag von Stille »

Dreamdancer hat geschrieben:Also ich würde das dann für mein Gedächtnis so abspeichern: "Admissible estimates" sind ja mathematisch gesehen untere Schranken auf die tatsächliche Distanz/tatsächlichen Kosten, damit sind untere Schranken zwar auch admissible estimates, aber untere Schranken zaubert man ja nicht aus dem Hut, das ist ja ein sehr abstrakter Begriff. Deshalb würde ich die beiden Sachen als Synonym verwenden, das eine aus der Mathematik stammend, dass andere aus der Algorithmik und euklidische Distanz nur eine von vielen möglichen Distanzen ist, die diese Forderung erfüllen.
Sage ich da was falsches?
Das kann man hier sicher gleichbedeutend verwenden. Als Algorithmiker würde ich sagen, "admissible estimates" kann irgendetwas sein, was man sich auf jedwede Art und Weise aus dem Hut zaubern kann, vom dem jedoch weiß, daß es eben admissible ist. Lower Bounds sind - sofern sie nicht trivial sondern möglichst gut sein sollen - oftmals nicht ganz einfach zu bekommen. Im Beispiel von euklischen Distanzen erhält man sie recht simpel. Ich würde daher eine lower bound als Beispiel für ein admissible estimate sehen.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“