+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Diplom Informatik ( /forumdisplay.php?fid=114 )
+--- Forum: Praktische Informatik (HS) ( /forumdisplay.php?fid=73 )
+--- Thema: WBS-Prüfungsfragen ( /showthread.php?tid=5069 )
WBS-Prüfungsfragen - Christoph - 14.02.2004 19:00
Als Einstieg eine Frage zu A*:
Findet er in diesem Fall wirklich den optimalen Pfad?
Angenommen, der Algorithmus ist so weit, dass zwei
Pfade p_1 und p_2 beide einen Knoten n_1 bzw. n_2 vor dem Ziel n_goal sind.
Seien die Kosten bis den Knoten n_1/n_2 g(p_1) = g(p_2) = 100, also gleich.
Sei h(n_1) = 5, h(n_2) = 8 und für die Kosten gelte
g(n_1,n_goal) = 12 und g(n_2,n_goal) = 10.
Dann wird wie verlangt von beiden Knoten aus unterschätzt, der optimale Pfad ist der über n_2. Allerdings gilt
f(n_1) = g(n_1) + h(n_1) = 105 und
f(n_2) = g(n_2) + h(n_2) = 108.
Also wird der Pfad über n_1 zuerst ausgewählt und das Ziel wird erreicht.
Eine Lösung wäre, dass auch bei gefundendem Ziel noch geprüft wird, ob es einen Pfad in der Grenze gibt mit niedrigerem Wert für f, aber ich kann das bisher nicht aus der Def. des A*-Alg. herauslesen.
Meinungen?
Re: WBS-Prüfungsfragen - Anatoly Karpov - 14.02.2004 23:39
Moin Christoph!
Gerade bei den Beschreibungen im Poole bzgl. Suchalgorithmen wollte ich hier auch fast genau das gleiche posten. Mit der einzigen Ausnahme, dass das beschriebene Problem meiner Meinung nach auch mit dem Lowest-Cost-First Algotithmus auftritt.
Hier deswegen noch einmal das Szenario unter der Annahme, dass es sich um einen Lowest-Cost-First Algorithmus handelt:
Knoten a und b führen beide unmittelbar zum Ziel.
Knoten a (Kosten vom Start: 45; zum Ziel: 8)
Knoten b (Kosten vom Start: 50; zum Ziel: 2)
Die nach den Kosten sortierte Liste (vorher):
[a<45>, b<50>]
Es wird (vgl. Poole S. 131) immer der beste (am weitesten links stehende) Knoten verfolgt, daraus resultiert die folgende sortierte Liste nach dem Durchlauf:
[b<50>,ziel_über_a<53>]
Ein Ziel wurde jetzt zwar gefunden, aber ist es wie in dem Beispiel von Christoph jetzt wirklich schon ein Ziel für den Algorithmus? Ich glaube nicht, denn sonst würde der Lowest-Cost-First ja nicht korrekt sein. Nach Poole findet er nämlich, falls es ein Weg zum Ziel gibt, diesen Weg auch und zwar den optimalen zuerst.
Meiner Meinung nach ist der Algorithmus noch nicht fertig, denn der Weg zum Ziel ist noch nicht gefunden - steht er doch noch nicht ganz links in der Liste. Es würde jetzt also noch ein Durchlauf kommen, der jetzt b<50> unter die Lupe nimmt und einen Weg findet, den der Algorithmus auch als Ziel wertet. Das hört sich zwar nicht so toll an, aber anders geht es halt nicht.
Analog dazu jetzt noch mal zu dem Beispiel eines A* Algorithmus (siehe Christophs Posting vorher):
Die Liste vorher hier wird nach f = (g + h) sortiert:
[n_1<100+5=105>, n_2<100+8=108>]
Die neue Liste:
[n_2<100+8=108>, ziel_über_n_1<100+12=112>]
Auch hier würde ich wie im Beispiel des Lowest-Cost-First Algorithmus nicht von einem Ziel sprechen, denn das Ziel steht nicht ganz links in der Liste. Also gehts weiter:
Die neue Liste:
[ziel_über_n_2<100+10=110>, ziel_über_n_1<100+12=112>]
Und damit ist der Algorithmus imo beendet.
Ich hab mich auch schon ein paar Mal am Kopf gefasst und mich vertan, aber so glaube ich es jetzt verstanden zu haben und sollte das doch nicht stimmen dann klärt mich auf...
Re: WBS-Prüfungsfragen - Slater - 15.02.2004 14:26
nicht so schüchtern, ist doch richtig
muss man auch nicht so kompliziert ausdrücken:
der Weg über n1 scheint 105 (oder mehr) zu kosten,
der Weg über n2 108 (oder mehr)
dann untersucht man natürlich zunächst den Weg über n1
danach bekommt man eine neue Kostenbewerung für den Weg über n1, nun 112,
damit ist der Weg über n2 vielversprechender und wird nun erst mal verfolgt,
(die Information, dass der n1-Weg nun direkt zum Ziel führt und GENAU 112 kostet,
spielt dafür nicht mal eine Rolle)
Re: WBS-Prüfungsfragen - Christoph - 15.02.2004 14:54
also wird genau dann, wenn ich den "vordersten" Knoten der Frontier-Liste auswähle, geprüft, ob das der Zielknoten ist und dann erst gebe ich aus, dass ich eine Lösung habe?
Bzw. im Skript/Buch stand mal was, dass man erst alle Nachbarn in die Frontier-Liste einträgt und danach erst prüft, ob es das Ziel ist. Aber im prinzip sollte das hier nicht weiter stören....
So würde das gehen...
Re: WBS-Prüfungsfragen - Anonymer User - 27.02.2004 10:12
Was genau ist eigentlich dieses "Stanford Research Institute Problem"? Dazu haben wir mit STRIPS einen Lösungsansatz...
Re: WBS-Prüfungsfragen - Anatoly Karpov - 27.02.2004 11:19
Also STRIPS steht für STanford Research Institute Problem Solver. Es geht um Planungsprobleme, und STRIPS stellt sowohl auf der repräsentationellen als auch auf der Planungsebene Ansätze dazu bereit.
Wie das funktioniert (Verfahren & Repräsentation) steht wunderbar im Poole beschrieben, das tipp ich hier jetzt nicht noch rein...
Re: WBS-Prüfungsfragen - Christoph - 27.02.2004 13:57
Meint ihr, dass man das Assumption Based Reasoning als Formalisierung der Integrity Contraints betrachten kann - mit dem einzigen Unterschied, dass bei letzterem auch Fehlerzustände ("unnormale" Zust.) als Assumables gelten?