Seite 1 von 1

Zulässge Heuristiken / Admissible heuristics

Verfasst: 30. Apr 2019 14:26
von krawehl
[English below]
Hallo,

in der Vorlesung hieß es, dass Heuristiken, die den tatsächlichen Wert sicher unterschätzen "zulässig" sind. Was bedeutet das?
Bzw. wenn das nicht gilt, warum ist das dann ein Problem? Vermutung: Wenn man Knoten überschätzt, führt das dann dazu, dass
man unter Umständen keine Lösung bekommt?

Viele Grüße,
krawehl

[English]
Hello,

in the lecture we had admissible heuristics, which should always underestimate the actual value. Why is this relevant? Would an
overastimating heuristic exclude nodes that could be part of the solution?

Regards,
krawehl

Re: Zulässge Heuristiken / Admissible heuristics

Verfasst: 7. Mai 2019 12:19
von Nicca
Hallo,

ohne dass ich es jetzt noch mal nachgelesen habe, eher mit Wissen aus anderen Fächern: Eine zulässige Lösung ist eine, die das Problem löst, aber nicht unbedingt optimal (Bsp. Navigation von Darmstadt nach Frankfurt: zulässig wäre vielleicht auch eine Fahrt über Wiesbaden, optimal ganz sicher nicht. )
Wenn ich also einen möglichst geringen Wert haben will, bin ich mit meiner Heuristik auf der sicheren Seite, wenn ich immer nur einen niedrigeren als den tatsächlichen Wert erlaube, denn damit verbessere ich auf jeden Fall meine Zielfunktion.

Sorry, ich merke jetzt, dass ich es noch weniger erklären kann als ich dachte... Vielleicht hilft es zumindest zum weiterdenken.

Re: Zulässge Heuristiken / Admissible heuristics

Verfasst: 7. Mai 2019 13:09
von Tobias Joppen
Hallo,

Die Antwort von Nicca kann ich zustimmen.

Man kann sich auch grundlegend die Frage stellen:
Wofür brauche ich überhaupt solche Eigenschaften (wie z.B. Zulässigkeit) für Heuristiken? Das sind ja erst mal nur abstrakte Ideen mit denen man wenig anfangen kann.
Sinnvoll werden solche Eigenschaften erst, wenn man sie verwendet und sich auf ihre Einhaltung verlassen kann.

Um Niccas Beispiel aufzugreifen kennen wir beispielsweise die Strecke über die Autobahn von Darmstadt nach Frankfurt (Sagen wir mal 35 km).
Wenn uns jetzt überlegen, ob über Wiesbaden zu fahren vielleicht kürzer ist, dann können wir uns mit zulässigen Heuristiken etwas rechnerei sparen:
Angenommen wir haben aufwendig berechnet, dass die kürzeste Strecke nach Wiesbaden nur 30 km brauchen würde (ist vielleicht etwas kurz, aber nehmen wir es mal an), dann muss die Strecke von Wiesbaden nach Frankfurt unter 5km lang sein, damit die Strecke Darmstadt-Wiesbaden-Frankfurt kürzer sein kann als die Strecke Darmstadt-Autobahn-Frankfurz. Und genau hier können uns zulässige Heuristiken sehr helfen:
Haben wir eine Heuristik für die Strecke Wiesbaden-Frankfurt von 10km heißt das erst mal nur, dass wir (auf welcher Grundlage auch immer) schätzen , dass die Distanz um die 10km lang ist. Das hilft uns aber noch nicht weiter, denn es ist nur eine Schätzung und die können ja beliebig falsch sein. Die wahre Distanz könnte 2km sein.
Haben wir aber eine zulässige Heurisik, dann gilt das nicht mehr, denn die wahre Strecke von Wiesbaden-Frankfurt kann nicht kürzer sein als der heuristische Wert. Haben wir also eine zulässige Heuristik, die die Distanz Wiesbaden-Frankfurt mit 10km schätzt und die Distanz von Darmstadt-Wiesbaden mit 30 km berechnet, so kann die Strecke von Darmstadt-Wiesbaden-Frankfurt nicht kürzer als 10+30=40 km sein.
Hier könnte ein Algorithmus, der den kürzesten Weg sucht, aufhören weiter nach einem Weg über Wiesbaden zu suchen. Wir wissen, dass es nicht der optimale sein kann.

Liebe Grüße,
Tobias