Konsistente Heuristik

[florian]

Hallo,

ich habe eine Frage zum Thema Heuristiken:

Und zwar verstehe ich nicht was es bedeutet, dass eine Heuristik konsistent ist.
(Folie 22, Informed Search)

[grieser]

siehe Russel/Norvig S. 99...

[Dreamdancer]

Na ich glaube, DIESES Problem hätten die Studenten auch unter sich lösen können.

[grieser]

Ich wollte halt auch mal helfen:-)

Aber wenn Sie meinen werde ich in Zukunft meinen Mund halten...

[Dreamdancer]

NEIN, genau das Gegenteil wollte ich sagen!!! Es gibt so viel umfangreichere Fragen ...

[grieser]

Und genau da habe ich den Eindruck, daß die Studenten sich gegenseitig helfen, ich habe den Antworten dort nichts hinzuzufügen...

[Dreamdancer]

Ok, das ist auch eine Aussage, die mich zufriedenstellt

[klospatz]

Und zwar verstehe ich nicht was es bedeutet, dass eine Heuristik konsistent ist.
(Folie 22, Informed Search)

um die eigentliche frage nochmal aufzugreifen:

den graph auf selbiger folie finde ich recht selbsterklaerend. eine heuristik, also eine kostenabschaetzung, ist konsistent, wenn wenn die kostenabschaetzung von einem beliebigen knoten n zu einem beliebigen knoten g kleiner oder gleich der abschaetzung von einem beliebigen "zwischenknoten" n' (nach anwendung einer aktion a vom knoten n) zum knoten g ist.
h(n) <= c(n, a, n') + h(n')

klaert das deine frage?

[Hungriger Hugo]

Soweit so gut, wenn man sich Städte vorstellt funktioniert dies auch einwandfrei. Heißt ja im Prinzip nichts anderes, als dass wenn man den direkten Weg zu einer Zielstadt geht dieser immer kürzer geschätzt werden muss, als ein Weg über eine andere Stadt zu dieser Zielstadt.

Aber wenn man jetzt das Beispiel aus der Übung nimmt (Aufgabe 1.2), wo man Steine korrekt platzieren soll, wurde z.B. als Heuristik vorgeschlagen, die korrekt platzierten Steine zu zählen.

Es könnte also sein, dass h(n) = 4 und h(n') = 5. Wie kann ich jetzt, das verbleibende c(n,a,n') berechnen? Man hat doch unterschiedliche Einheiten (einmal korrekt platzierte Steine und einmal "Zugkosten")...

Ausserdem würde mich interessieren, wie man zeigt, dass für jedes n der direkte Weg der optimale Weg ist.

Zwischen n und n' können allgemein auch mehrere Knoten liegen, oder?

[klospatz]

Aber wenn man jetzt das Beispiel aus der Übung nimmt (Aufgabe 1.2), wo man Steine korrekt platzieren soll, wurde z.B. als Heuristik vorgeschlagen, die korrekt platzierten Steine zu zählen.

du meinst sicher die anzahl der inkorrekt platzierten steine. (die anzahl der korrektplatzierten ist sicher nicht admissable). in dem fall verhaelt es sich doch analog zum staedtebeispiel. setze dazu oBdA stadt = stein.

Wie kann ich jetzt, das verbleibende c(n,a,n') berechnen?

c ist in der aufgabenstellung vorgegeben. entweder die anzahl der uebersprungen steine oder 1.

Ausserdem würde mich interessieren, wie man zeigt, dass für jedes n der direkte Weg der optimale Weg ist.

der fall duerfte ja nur bei konsistenten heuristiken richtig sein. und dann sollte eine prosa begruendung bezueglich konsitenz beweis genug sein.

Zwischen n und n' können allgemein auch mehrere Knoten liegen, oder?

beliebig viele, wenn du mich fragst.

[Rodent Bait]

Es könnte also sein, dass h(n) = 4 und h(n') = 5. Wie kann ich jetzt, das verbleibende c(n,a,n') berechnen? Man hat doch unterschiedliche Einheiten (einmal korrekt platzierte Steine und einmal "Zugkosten")...

Das Ziel der Heuristik ist, eine Schätzung über die Kosten zum Ziel zu finden. Die Heuristik sagt nun aus, dass die Kosten durch die Anzahl der noch nicht korrekt platzierten Steine abgeschätzt werden kann. Da wird tatsächlich eine Einheit in die andere konvertiert, machbar ist das aber. Ist halt eine Heuristik ( so wie "Volumen in Liter ist ungefähr gleich Gewicht in Kilo").

Zwischen n und n' können allgemein auch mehrere Knoten liegen, oder?

c(n,a,n') ist zunächst nur für definiert, falls n' ein direkter Nachfolger von n ist. Aber durch wiederholtes Einsetzen erhältst Du
h(n) <= c(n,a,n') + c(n,a',n'') h(n'') usw.

Ausserdem würde mich interessieren, wie man zeigt, dass für jedes n der direkte Weg der optimale Weg ist.

Wie definierst Du den direkten Weg?

[Hungriger Hugo]

...mit dem direkten Weg hat sich erledigt!

Nun habe ich es auch verstanden. Vielen Dank euch zwei!