Unterschied zwischen...

[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.

[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.

[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?

[Stille]

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.