• Bei b) tu ich mir schwer ein counterexample zu finden obwohl ich glaube, dass das nicht so schwer sein kann. Hat da jemand einen Vorschlag bzw. Hilfestellung für mich?


    (Im Generellen sind die Heuristik-Beispiele/Beweise nicht meine Lieblinge bei den Aufgaben..)

    TI, SE-Student - Software/Hardware Engineer

  • Ich hab als Beispiel das 8-Puzzle genommen und als Heuristiken die Manhattan Distanz und die Anzahl der falsch Platzierten Felder.


    Du musst ein Beispiel finden, bei dem die Manhattan Distanz nach einem Zug sinkt, aber die Anzahl der falsch platzierten Felder gleich bleibt, dann ist die Ungleichung für die Konsistenz nicht mehr erfüllt.

  • Zeichne dir einen kleinen Graphen mit 3 Knoten auf zB A -> B -> G, wobei G der Goal Knoten ist und bewerte die "eigentlichen" Kosten für diese Wege.
    Dann schau dir 2 Heuristiken an, für die jeweils die Konsistenzbedingungen gelten (zB "Luftlinie", die ist auch immer kleiner/gleich den eigentlichen Kosten) wobei du h1 so wählst, dass sich die Bedingungen nur "sehr knapp" ausgehen, also die heuristischen Werte sind nahe den eigentlichen Werten sind, und für h2 nimmst du ganz kleine Werte, für die die Konsistenzbedingungen auf jeden Fall ausgehen!


    Dadurch dass für h1 die Bedingungen nur "knapp" gelten, ist h(n) = 2*h1(n) nicht mehr konsistent, und wenn du h2 richtig wählst ist auch h(n) = 2* h1(n) - h2(n) nicht mehr konsistent!