IDA * und Zulässigkeit einer Heuristik?

Question

Ich möchte alte Prüfung auf AI üben und eine herausfordernde Frage sehen und Hilfe von einigen Experten benötigen ...

A ist Anfangszustand und G ist ein Zielzustand. Die Kosten werden an der Kante angezeigt und die heuristischen "H" -Werte werden auf jedem Kreis angezeigt. IDA * Limit ist 7. Wir wollen dieses Diagramm mit IDA * suchen. In welcher Reihenfolge besuchen diese Knoten? (Kind wird in alphabetischer Reihenfolge und in gleicher Bedingung ausgewählt, der Knoten wird zuerst ausgewählt, der zuerst produziert.)

Lösung ist A, B, D, C, D, G.

Meine Frage ist, wie diese berechnet wird, und wie wir diese Heuristik sagen kann ist zulässig und konsistent?

Answer 1

Meine Frage ist, wie diese berechnet wird, und wie wir sagen können Heuristic ist zulässig und konsistent?

ersten Start Lassen Sie uns mit Definitionen dessen, was zulässig und konsistente Heuristik:

1. Eine zulässige Heuristik überschätzt nie die Kosten um das Ziel zu erreichen, dh die Kosten für das Ziel erreichen schätzungsweise nicht ist größer als die Kosten des kürzesten Pfads von diesem Knoten zum Zielknoten im Diagramm.

   Sie können leicht sehen, dass für alle Knoten n im Diagramm die Schätzung h(n) immer kleiner oder gleich dem tatsächlichen kürzesten Pfad ist. Zum Beispiel h (B) = 0 < = 6 (B → F → G).

2. sei c (n, m) bezeichnen die Kosten eines optimalen Pfades in dem Graphen von einem Knoten n zu einem anderen Knoten n'. Eine heuristische Schätzfunktion h(n) ist konsistent, wenn in der Grafik h(n) + c(n, m) <= h(n') für alle Knoten n , n' angezeigt wird. Eine andere Möglichkeit, die Eigenschaft der Konsistenz zu sehen, ist Monotonie. Konsistente heuristische Funktionen werden auch monotone Funktionen genannt, die aufgrund der geschätzten Endkosten einer Teillösung monoton nicht entlang des besten Pfades zum Ziel abnehmen. Daher können wir feststellen, dass Ihre heuristische Funktion nicht konsistent ist.

   h (A) + c (A, B) < = h (B) -> 6 + 2 < = 0.

Lassen Sie mich eine Analogie tun es in einer weniger mathematisch zu erklären, . Sie gehen mit Ihrem Freund einen Lauf. An bestimmten Punkten fragen Sie Ihren Freund, wie lange es dauert, Ihren Lauf zu beenden. Er ist ein sehr optimistischer Typ und er gibt dir immer eine kleinere Zeit, die du machen kannst, selbst wenn du den Rest des Weges an deiner Spitze rennst. Allerdings ist er in seinen Schätzungen nicht sehr konsequent. An einem Punkt A sagte er Ihnen, es wird mindestens eine Stunde mehr, um zu laufen, und nach 30 Minuten laufen Sie fragen ihn wieder. Jetzt sagt er dir, dass es mindestens 5 Minuten mehr von dort ist.Die Schätzung in Punkt A ist weniger informativ als in Punkt B und daher ist Ihr heuristischer Freund inkonsistent.

Im Hinblick auf die Durchführung von IDA *, mir copy-paste des Pseudo-Code des Algorithmus (Ich habe nicht getestet) aus der wikipedia:

node    current node 
g     the cost to reach current node 
f     estimated cost of the cheapest path (root..node..goal) 
h(node)   estimated cost of the cheapest path (node..goal) 
cost(node, succ) step cost function 
is_goal(node)  goal test 
successors(node) node expanding function 

procedure ida_star(root) 
    bound := h(root) 
    loop 
    t := search(root, 0, bound) 
    if t = FOUND then return bound 
    if t = ∞ then return NOT_FOUND 
    bound := t 
    end loop 
end procedure 

function search(node, g, bound) 
    f := g + h(node) 
    if f > bound then return f 
    if is_goal(node) then return FOUND 
    min := ∞ 
    for succ in successors(node) do 
    t := search(succ, g + cost(node, succ), bound) 
    if t = FOUND then return FOUND 
    if t < min then min := t 
    end for 
    return min 
end function 

folgen der Ausführung für Ihr Beispiel einfach ist. Zuerst legen wir die Grenze (oder den Schwellenwert) mit dem Wert der heuristischen Funktion für den Startknoten fest. Wir untersuchen den Graphen mit einer Tiefensuche, die die Zweige ausschließt, deren f-Wert größer als die Grenze ist. Beispiel: f (F) = g (F) + h (F) = 4 + 4> gebunden = 6. Die Knoten werden in der folgenden Reihenfolge untersucht: A, B, D, C, D, G. In einer ersten Iteration des Algorithmus werden die Knoten A, B, D erkundet und wir haben keine Optionen, die kleiner als die Grenze sind.

Die Grenze wird aktualisiert und in der zweiten Iteration werden die Knoten C, D und G untersucht. Sobald wir den Lösungsknoten mit einer Schätzung (7) erreichen, die kleiner als die Grenze (8) ist, haben wir den optimalen kürzesten Pfad.