Konsistente Heuristik
Moderator: Einführung in die Künstliche Intelligenz
Konsistente Heuristik
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)
ich habe eine Frage zum Thema Heuristiken:
Und zwar verstehe ich nicht was es bedeutet, dass eine Heuristik konsistent ist.
(Folie 22, Informed Search)
-
- Mausschubser
- Beiträge: 67
- Registriert: 17. Jul 2005 23:17
- Wohnort: Frankfurt am Main
-
- Mausschubser
- Beiträge: 67
- Registriert: 17. Jul 2005 23:17
- Wohnort: Frankfurt am Main
-
- Mausschubser
- Beiträge: 67
- Registriert: 17. Jul 2005 23:17
- Wohnort: Frankfurt am Main
- klospatz
- Sonntagsinformatiker
- Beiträge: 230
- Registriert: 16. Dez 2003 14:01
- Wohnort: Darmstadt
- Kontaktdaten:
Re: Konsistente Heuristik
um die eigentliche frage nochmal aufzugreifen:florian hat geschrieben:Und zwar verstehe ich nicht was es bedeutet, dass eine Heuristik konsistent ist.
(Folie 22, Informed Search)
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?
-
- Neuling
- Beiträge: 8
- Registriert: 2. Jul 2007 13:17
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?
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
- Sonntagsinformatiker
- Beiträge: 230
- Registriert: 16. Dez 2003 14:01
- Wohnort: Darmstadt
- Kontaktdaten:
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: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.
c ist in der aufgabenstellung vorgegeben. entweder die anzahl der uebersprungen steine oder 1.Hungriger Hugo hat geschrieben:Wie kann ich jetzt, das verbleibende c(n,a,n') berechnen?
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:Ausserdem würde mich interessieren, wie man zeigt, dass für jedes n der direkte Weg der optimale Weg ist.
Hungriger Hugo hat geschrieben:Zwischen n und n' können allgemein auch mehrere Knoten liegen, oder?
beliebig viele, wenn du mich fragst.
- Rodent Bait
- Mausschubser
- Beiträge: 91
- Registriert: 26. Apr 2005 14:50
- Wohnort: Darmstadt
- Kontaktdaten:
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").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")...
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 DuZwischen n und n' können allgemein auch mehrere Knoten liegen, oder?
h(n) <= c(n,a,n') + c(n,a',n'') h(n'') usw.
Wie definierst Du den direkten Weg?Ausserdem würde mich interessieren, wie man zeigt, dass für jedes n der direkte Weg der optimale Weg ist.

-
- Neuling
- Beiträge: 8
- Registriert: 2. Jul 2007 13:17