Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Pacman
Wir sollen ja Heuristiken für die Suche aufstellen.
-
Eine Heuristik h hat ja die Eigenschaf, dass
h(a) = 0 <=> a ist Ziel -
Nun ist das Ziel a als Blattknoten mit m Cherrys auf dem Weg dorthin definiert. (wobei m := max(#Cherrys) _ alle Pfade)
aus 1. und 2. => m muss bekannt sein um h aufzustellen. (gesweige denn h*)
=> Ich kann bei dieser Aufgabe annehmen, dass m immer bekannt ist.
Ich bitte um Korrektur, falls diese Schlussfolgerungen falsch sind.
Nein, nicht direkt. „Das“ Ziel gibt es erstmal nicht, sondern viele davon - jeder Blattknoten ist ein Ziel, nur nicht notwendigerweise ein optimales. Analog: jeder Weg von Arad nach Budapest ist ein Ziel, nicht nur der kürzeste.
dann passe ich meine frage an:
ist bekannt wie viele Cherries auf einem optimalen weg liegen, so dass ich nur noch nach einem dieser optimalen Wege suchen muss?
oder soll man optimistisch einen “optimalen” weg finden.
Ohne diese Information, habe ich allerdings keine Moeglichkeit zu verifizieren, dass der von mir gefundene Weg ein optimaler ist, ohne zusaetzlich alle anderen Wege vorher durchzugehen.
Tut mir leid, ich verstehe deine Frage nicht. Optimalität ist eine Eigenschaft des Algorithmuses; bei A* wissen wir zum Beispiel dass er optimal ist, wenn die Heuristik admissible ist. Deine Cost-Funktion muss halt die Problemstellung hinreichend akurat modellieren, i.e. so dass “Pfad mit den geringsten Kosten”=“Weg mit den meisten Kirschen”. Wenn das der Fall ist muss nur deine Heuristik admissible sein, dann hast du das automatisch.
Analogon deiner Frage wäre: “Ist bekannt wie lange die optimale Strecke von Arad nach Budapest ist, so dass ich nur nach einer dieser optimalen Strecke suchen muss?” - vielleicht wird so deutlich warum die Frage irgendwie… irrelevant zu sein scheint.
danke jezt habe ichs gecheckt
1 „Gefällt mir“