Dominierende Heuristiken

  • Ich denk vielleicht grad nur falsch und versteh es deswegen nicht, aber irgendwie werd ich aus den Definitionen nicht schlau.
    Eine Heuristik h2 dominiert h1, wenn für alle n gilt: h2(n) >= h1(n).
    Gut, als Beispiel wird dann eine Tabelle mit lauter Suchkosten für die jeweiligen Heuristiken aufgelistet. Aber für jede Suchtiefe sind die Kosten von h2(n) <= h1(n). Wie soll das dann der Definition gerecht werden, dass h2 h1 dominiert? Ich mein, rein logisch gesehen macht es schon Sinn, dass es besser ist, wenn die Kosten für die Heuristik bei jedem n minimal sind, aber warum dann das >=?

  • Meinst du den Ausschnitt:

    Quote

    DFIDS requires 3,473,941 nodes
    A with h1 requires 539 nodes
    A with h2 requires 113 nodes


    Das soll veranschaulichen das mit h2 die suche besser ist da weniger Nodes überprüft werden.


    Die angegebenen Werte sind nicht die Werte die die Heuristik liefert.


    Dadurch das h2 Werte liefert die besser sind (näher am tatsächlichen Wert h*) werden weniger schlechte Routen untersucht.


    Nehmen wir als Beispiel das h1 immer 0 liefert und h2 Manhattan-Distanz.


    Wenn die Aufgabe eine Navigation in einem quadratischem Grid ist wird die suche mit h1 als Heuristic zu einer Breadth-Frist suche in ALLE Richtungen.
    Mit h2 = Manhatten Distanz wird es dagegen eher so aussehen:


  • Im Buch hats halt eine Tabelle gegeben - siehe http://www.informatik.uni-ulm.…ngen/GdKI/WS0203/r4_1.pdf Seite 20, is wohl exakt aus dem Buch übernommen. Da seh ich auch nur, dass die Kosten für h2 geringer sein sollten. Wie kommts jetzt dann dazu, dass h2 h1 dominiert? Die Werte sind ja durchgehend geringer. Oder versteh ich da was falsch?

  • Im Buch hats halt eine Tabelle gegeben - siehe http://www.informatik.uni-ulm.…ngen/GdKI/WS0203/r4_1.pdf Seite 20, is wohl exakt aus dem Buch übernommen. Da seh ich auch nur, dass die Kosten für h2 geringer sein sollten. Wie kommts jetzt dann dazu, dass h2 h1 dominiert? Die Werte sind ja durchgehend geringer. Oder versteh ich da was falsch?


    Das hier h2 h1 dominiert ist einfach gegeben. (Also die entsprechend gewählt). Man kann es sich aus der Tabelle nur denken da dominierende Heuristiken geringere Suchkosten haben also die von ihnen dominierten.


    Ich glaube du verwechselst hier einfach die Suchkosten mit den geschätzten kosten die uns eine Heuristik liefert.


    Die Heuristiken liefern uns geschätzte wegkosten von einer Node zum Ziel. In der Tabelle angeführt sind aber die Suchkosten! (Also die kosten dafür einen gültigen Weg zu finden)


    Wenn wir wissen das die Heuristik admissible ist wissen wir das sie die kosten nie überschätzt. Damit kann man sich leicht die Extremfälle vorstellen.

    • h1(n) = 0 (für alle n)
    • h2(n) = h*(n) - Die tatsächlichen kosten von n zum Ziel.


    Informell kann man es sich dann so vorstellen:

    • Verwenden wir h* untersuchen wir für jeden Knoten immer nur einen Nachfolger. Warum? Wir wissen für alle Nachfolger welcher am weitesten vom Ziel entfernt ist und nehmen daher immer den der am nächsten am Ziel ist.
      Wir untersuchen daher NUR Knoten die zwischen Start und Ziel liegen.
    • Verwenden wir h1 haben wir keine Ahnung wie weit unsere Nachfolger vom Ziel entfernt sind. Jeder Nachfolger hat die selbe Priorität egal ob er Richtung Ziel führt oder nicht. Wir wissen nur wie weit wir bis zum Nachfolger brauchen. Daher untersuchen wir von allen Nachfolgern immer den der am nächsten am Start lag bis wir auf das Ziel stoßen.
      Wir untersuchen daher ALLE Knoten deren Distanz zum Start kleiner ist als die zwischen Start und Ziel
    • Verwenden wir eine Heuristik die dazwischen liegt wissen wir ca. wie weit die Nachfolger vom Ziel entfernt sind, und nehmen daher meistens welche die auch am Weg liegen.


    Je näher die Heuristik also an den Tatsächlichen kosten liegt umso genauer wissen wir welche Nachfolger näher am Ziel sind. Daher untersuchen wir weniger Irrwege -> Die Suchkosten sind kleiner.