Seite 1 von 1

Konsistente Heuristik

Verfasst: 11. Jul 2007 13:29
von 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)

Verfasst: 11. Jul 2007 20:24
von grieser
siehe Russel/Norvig S. 99...

Verfasst: 12. Jul 2007 15:44
von Dreamdancer
Na ich glaube, DIESES Problem hätten die Studenten auch unter sich lösen können.

Verfasst: 12. Jul 2007 15:50
von grieser
Ich wollte halt auch mal helfen:-)

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

Verfasst: 12. Jul 2007 15:51
von Dreamdancer
NEIN, genau das Gegenteil wollte ich sagen!!! Es gibt so viel umfangreichere Fragen ...

Verfasst: 12. Jul 2007 15:54
von grieser
Und genau da habe ich den Eindruck, daß die Studenten sich gegenseitig helfen, ich habe den Antworten dort nichts hinzuzufügen...

Verfasst: 12. Jul 2007 16:00
von Dreamdancer
Ok, das ist auch eine Aussage, die mich zufriedenstellt :-)

Re: Konsistente Heuristik

Verfasst: 12. Jul 2007 22:02
von klospatz
florian hat geschrieben: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?

Verfasst: 13. Jul 2007 17:37
von 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?

Verfasst: 13. Jul 2007 18:34
von klospatz
Hungriger Hugo hat geschrieben: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.
Hungriger Hugo hat geschrieben: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.
Hungriger Hugo hat geschrieben: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.
Hungriger Hugo hat geschrieben:Zwischen n und n' können allgemein auch mehrere Knoten liegen, oder?

beliebig viele, wenn du mich fragst.

Verfasst: 14. Jul 2007 00:03
von 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? :wink:

Verfasst: 14. Jul 2007 11:06
von Hungriger Hugo
...mit dem direkten Weg hat sich erledigt!

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