1. Übungsblatt

[Nikmaster]

Hallo,
ich hab ein paar kleine Probleme mit den Zettel

1+2) Was ist mit Konstante cbfs bzw cdfid gemeind? Ich find in den unterlagen dazu keine passende Konstante und ich hab keine ahnung was diese ausdrücken soll? (der rest der übung ist ja eh in den folien, man muss ja nur die schätzung des benötigten space herleiten können, oder?)
8) stehe ich total an
hier dienen die gegebenen heuristiken als schätzwerte für die kosten für das puzzle?
wobei n der aktuelle zustand des puzzles ist?
dann wäre zB h1 (number of missmatched tiles) admissible, da man ja mit einen zug maximal ein feld bewegen kann - wodurch die mindestkosten die anzahl der falsch liegenden platten sind (damit werden die gesamtkosten doch nie überschätzt) - aber hier ist ja explizit formale beweiße verlangt

hab ich die aufgabenstellungen soweit richtig verstanden?

[_gerald_]

Ohne jetzt genauer nachgeschaut zu haben, vermute ich sie meinen mit den beiden Konstanten jeweils die Schranken fuer die exponentielle Laufzeit. Sprich, du musst jene Konstanten suchen, sodass c*b^d immer eine obere Schranke bzgl. der Laufzeit des Algorithmus ist.

[Mobe]

Hat jemand einen Tip zu 3) ? Der overhead bei dfid ist doch, dass jeder knoten auf ebene L (d-L)-mal betrachtet wird oder? Je höher der Verzweigungsfaktor ist, desto geringer ist der overhead durch mehrfaches Expandieren. Was soll man aus diesen zwei Kurven rauslesen??

[wichtel]

Ich hab mal wieder eine grundsätzliche Unklarheit, nämlich zu den Beispielen 1+2. Geh ich da vor wie bei der Laufzeitabschätzung von Algorithmen?

Momentan ist meine Schätzung b^d/2 (weil im Schnitt nach der Hälfte eine Lösung gefunden wird) - davon bin ich aber nicht ganz überzeugt. Jedenfalls hab ich mal folgendes gemacht:

b^d/2 <= b^d * c
1/2 <= c

Also schätze ich c auf 1/2 (oder 1, weils ja nur eine Schätzung sein soll).

Ist das so richtig?

[_gerald_]

Die generelle Frage ist, ob nicht die Worst-Case-Zeit gefragt ist. Meiner Meinung nach macht ja das d nur Sinn, wenn man davon ausgeht, dass in der Tiefe d eine Loesung ist. Hab das ganze mal mit einer Differenzengleichung geloest und komm auf die generierten Knotenzahl von b^d - 1, was auch klar ist, wenn man

1.) davon ausgeht, dass der branching faktor immer konstant bleibt (d.h. jeder knoten hat b nachfolger)
2.) die "anzahl der generierten knoten" einfach die knotenzahl des baumes ist (ist sie das?)

Mehr hab ich zur Zeit leider auch noch nicht, aber werd mal versuchen, dass ich den branching-faktor variieren lass. Intuitiv ist es klar, dass es hoechstens b^d knoten sein koennen, da ja ein baum mit hoehe d und verzweigungsgrad b genau b^d - 1 knoten hat.

[wichtel]

Meiner Meinung nach macht ja das d nur Sinn, wenn man davon ausgeht, dass in der Tiefe d eine Loesung ist.

d bezeichnet die Tiefe der günstigsten Lösung, nicht die Tiefe des Baumes (der kann nämlich unendlich tief sein)!

die "anzahl der generierten knoten" einfach die knotenzahl des baumes ist (ist sie das?)

Nicht unbedingt - wie gesagt, die Bäume können ja unendlich tief gehen (z.B. Schachspiel). Ich glaub eher dass es sich dabei um die Anzahl der Knoten handelt, die expandiert (also durchlaufen, bzw. deren Eltern durchlaufen) werden.

Ist aber nur eine Mischung aus Vermutung und Intuition meinerseits...

[_gerald_]

Ja, scho klar, dass der Baum unendlich tief sein kann. Jedoch ist der Teilbaum bis zur Tiefe d letztendlich der zu betrachtende Baum, da wir ja davon ausgehen, dass beim Finden einer Loesung die BFS terminiert. Mit der Anzahl der generierten Knoten meine ich daher die Knoten bis zum Finden der Loesung.

Wenn ich nun davon ausgehe, dass irgendwo in der "Ebene" d eine Loesung ist, dann ist es offensichtlich durch b^d beschraenkt. D.h. die Konstante c_bfs wird imho zum groessten Teil von dem Branching Faktor b abhaengen.

[charlie_brown]

also ich komm auf

n_bfs= (b^d-1) / ( b-1)

und

c_bfs>= 1/(b-1)

[Bernhard123]

eventuell hilfreich für 1+2:
https://vowi.fsinf.at/wiki/Datei:TU_...itung_2010.pdf

[_gerald_]

Komm auf das gleiche wie in der Ausarbeitung mit anderer Rechnung. Hab aber da immer angenommen, dass immer b Kinder bei jedem Knoten sind. Das waer eigentlich im Normalfall nicht so, aber egal wenns in der Ausarbeitung auch so ist...

[Bernhard123]

Denke, dass das so passt wie in der Ausarbeitung.

zu punkt 3) was kann man über die beiden kurven sagen? hab auf der x achse den branchingfaktor b und auf y den angegebenen Term (ist das die Laufzeit?). bedeutet das, dass dfid bei niedrigem b doppelt so lange dauert und sich dann annäherd zu bfs?

ein Tipp zu 4 wär auch super, werd da aus den folien nicht schlauer, find immer nur das es optimal ist mit der tree search

mfg

[_gerald_]

@Bernhard123: Punkt 3 haett ich auch so interpretiert. Die Kurve ist ja (aufgefasst als funktion von b) die Konstante fuer die Schranke von b^d. Sprich dfid wird dann fuer Probleme mit hoeherem Branching Faktor gut sein.

[Terminal]

Ahoi!

Habe bei punkt 1) die Summe mithilfe einer Differenzengleichung vereinfacht:



Daraus folgt dann:

Das kann man dann gut in der Ungleichung verwenden, um zu zeigen:

Für große d gilt dann:


Die Methode aus der Ausarbeitung funktioniert meiner Meinung nach nur für endliche d, da recht freizügig mit den Summen hantiert wird.
Ich habe allerdings etwas Schwierigkeiten beim Aufstellen der Differenzengleichung von punkt 2). Kann mir hier evt. wer weiterhelfen? Ich habe nämlich das Gefühl, dass Aufgaben 1 & 2 nicht ganz unwesentlich für Aufgabe 3 sind. Irre ich da?

/edit: Die Methode aus der Ausarbeitung ist wohl an die Idee der Vereinfachung bei geometrischen Reihen angelehnt. Dennoch wäre es mir lieber auch Aufgabe 2) über eine Differenzengleichung zu lösen.

[_gerald_]

Die Methode mit der Differenzengleichung funktioniert auch nur fuer endliche d, da keine nat. Zahl ist. Habe auch zwei Differenzengleichungen aufgestellt. Zur der von Aufgabe 2: Interpretier das dfid als Summe der Diffglg. von bfs bis zur Tiefe d. So bin ich aufs Ergebnis gekommen.

[Terminal]

Denke, dass das so passt wie in der Ausarbeitung.

zu punkt 3) was kann man über die beiden kurven sagen? hab auf der x achse den branchingfaktor b und auf y den angegebenen Term (ist das die Laufzeit?). bedeutet das, dass dfid bei niedrigem b doppelt so lange dauert und sich dann annäherd zu bfs?

ein Tipp zu 4 wär auch super, werd da aus den folien nicht schlauer, find immer nur das es optimal ist mit der tree search

mfg

zu Punkt 4) Also ich würde sagen, dass man eine Heuristik h finden muss, die zwar admissible (wie in der Angabe vorgegeben) aber nicht consistent ist. Denn es ist die Rede von Graphen und dort können nur solche Heuristiken eine suboptimale Lösung erzeugen, die eben nicht consistent sind (Auf Bäumen reicht schon admissible).

[Terminal]

Die Methode mit der Differenzengleichung funktioniert auch nur fuer endliche d, da keine nat. Zahl ist. Habe auch zwei Differenzengleichungen aufgestellt. Zur der von Aufgabe 2: Interpretier das dfid als Summe der Diffglg. von bfs bis zur Tiefe d. So bin ich aufs Ergebnis gekommen.

Danke, das hilft auf jeden Fall schon mal weiter beim Aufstellen der DfGl, allerdings habe ich dann gewisse Schwierigkeiten beim Lösen der DfGl:



Das führt aber doch dann zu einer homogenen Lösung von da doch konstant ist
und wenn ich dann Variation der Konstanten mache und in die inhomogene Gleichung einsetze erhalte ich



was mich nicht wirklich weiter bringt. Ich übersehe hier wohl etwas.

[_gerald_]

Ich meinte eher



Damit brauchst fuer dfid keine Diffglg und das ganze vereinfacht sich zu einer Summenumformung. Nach ein paar Index-Shifts und Vereinfachungen solltest du am Ziel sein.

[Terminal]

Danke, das ist natürlich wesentlich einfacher! Wenn ich dir mehr als ein Thanks geben könnte, würd ichs tun!

[Bernhard123]

Hey hätte noch ein paar Fragen, wär super wenn ihr mir feedback dazu geben könntet:

6) meine optimistisch-geschätzten Kosten sind jeweils kleiner gleich meinen tatsächlichen Kosten, bedeutet auch die max() ist kleiner gleich den tatsächlichen Kosten?
7) selbiges mit consitent? max(h1(n),h2(n)) <= c(n;a;n+1)+ max(h1(n+1),h2(n+1)) ?

9) die aufgabenstellung ist mir etwas unklar. Ich hab die Reihenfolge der expandierten Knoten notiert und die bisdahin erreichten Kosten der einzelnen Zielknoten.
*) BFS wär dann zB: das Alphabet mit Zielknoten Z am Ende mit den Kosten 89.
*) UCS wär bei Z mit Kosten 85 (brechen die Suchen ab wenn alle Zielknoten gefunden wurden, oder wird der komplette Baum durchlaufen?)
*) DFS wär W mit 85 der letzte Zielknoten.

Müssen wir dazu noch was notierten? Meinen die da so OPEN CLOSE LIST? "In addition, calculate for each search
strategy the set of nodes that is actually kept in memory when the goal node is found."

danke für jegliches Feedback!

Grüße

[BenBach]

Hi,

Könnte mir jemand Tipps für 6 und 7 geben?

Und wie funktioniert das mit den Ankreuz Übungen. Ist meine erste. Hab ich das richtig verstanden.
Man macht das Übungsblatt handschriftlich, kreuzt die gemachten Aufgaben an und nimmt die handschriftliche Lösung zum Termin mit ohne etwas hochzuladen?

Danke für jegliche Hilfe

[Bernhard123]

Hi,
Man macht das Übungsblatt handschriftlich, kreuzt die gemachten Aufgaben an und nimmt die handschriftliche Lösung zum Termin mit ohne etwas hochzuladen?

bingo

[arf]

Hi,

9) Erweitern wir die Knoten nach Kosten??
Also ist die Reihenfolge so: erst Kosten dann alphabetische Reihenfolge oder Kosten wird nur für UCS berücksichtigt?

[ag01]

Hi,

9) Erweitern wir die Knoten nach Kosten??
Also ist die Reihenfolge so: erst Kosten dann alphabetische Reihenfolge oder Kosten wird nur für UCS berücksichtigt?

Kosten werden nur für UCS benötigt ... sonst hat das Ganze IMO wenig Sinn.

[Terminal]

@Bernhard123: Die Beweise bei 6) und 7) hab ich im wesentlichen auch so (sind sehr kurz). Ich glaube hier kommt es hauptsächlich auf die richtige Argumentation an. 5) Lässt sich wider dem ersten Anschein auch recht leicht über vollständige Induktion über die Entfernung vom Zielknoten lösen.

@BenBach: Man sollte vielleicht noch erwähnen: Die ausgearbeiteten Lösungen sind den Übungsleitern meist relativ egal. Es geht mehr darum, dass du ein von dir angekreuztes Beispiel evt. an der Tafel vorführen musst und dabei sind ausgearbeitete Lösungen oft ganz nützlich.

[Benny]

bei 1) warum ist euch nd = b*nd-1 + 1 herausgekommen? bei b = 2 und d = 1 kommt ja nur 3 heraus, aber es konnen ja 3,4,5 und 6 Knoten erzeugt werden? Reicht die Schatzung fur den ersten Knoten jeder Tiefe? bei grossen d ist das nicht zu unklar?

P.S. : ist die Wurzel auf d=0 oder d=1?

[Bernhard123]

brechen die heuristiken bei punkt 9 ab, wenn ein goal node erreicht wurde?

[Mobe]

brechen die heuristiken bei punkt 9 ab, wenn ein goal node erreicht wurde?

Schätze schon.

[NoxMortem]

bei 1) warum ist euch nd = b*nd-1 + 1 herausgekommen? bei b = 2 und d = 1 kommt ja nur 3 heraus, aber es konnen ja 3,4,5 und 6 Knoten erzeugt werden? Reicht die Schatzung fur den ersten Knoten jeder Tiefe? bei grossen d ist das nicht zu unklar?

P.S. : ist die Wurzel auf d=0 oder d=1?

Die Wurzel ist auf d=0. Es werden aber nie mehr knoten in den Speicher geladen als betrachtet werden. Wenn also der Zielknoten auf Ebene d ganz rechts außen liegt und wir den worst case annehmen dass jeder knoten den maximalen branching faktor b hat dann müssten wir 1(=wurzel)+b^1+b^2+b^3+...+b^d Knoten speichern.

[Antimessiah]

eventuell hilfreich für 1+2:
https://vowi.fsinf.at/wiki/Datei:TU_Wien-Grundzüge_der_Artificial_Intelligence_VO_(Egly)_-_Beweisausarbeitung_2010.pdf

Wie kommt man bei dfid bitte von

c * (1 - x) = 1 + x + x² + x³ + ...

auf

c * (1 - x) = 1 / (1 - x)?

[Bernhard123]

@Anitmessiah: diese Folge ist das selbe.
http://www.wolframalpha.com/input/?i=1%2F(1-x)

Andere Frage:

Wird der A* bei Bsp. 10 einfach an den vorgegebenen Graphen angewendet? Denn in der Angabe steht "creating an A* search tree", wie bildet man den, wenn man mehrere Nachfolger hat?

[Turbosailor]

hat jemand einen tipp wie ich bei 4 auf eine heuristik komme die admissible ist aber nicht consistent ist? ich steh da iwie voll auf dem schlauch..

[wichtel]

hat jemand einen tipp wie ich bei 4 auf eine heuristik komme die admissible ist aber nicht consistent ist? ich steh da iwie voll auf dem schlauch..

Schau mal unter: http://ijcai.org/papers09/Papers/IJCAI09-111.pdf
Seite 2 (635) - daran kannst du dich orientieren ;-)

Gefunden übrigens mit Google "admissible but inconsistent heuristic".

[ri_ba]

Hm, da wird ein Graph hingeklatscht, bei dem die Werte für h(n) so angegeben ist, dass h admissible, aber nicht consistent ist. Aber was genau der Graph oder das h machen, weiß keiner. Ist das Beispiel genug? Und hat jemand Erfolg dabei gehabt, andere Graphen dieses Martelli zu finden? Ich finde überall nur diesen G5-Graphen oder italienische Restaurants Sollte ja auch einen mit 4 statt 5 Nodes geben, wäre entspannter.

Und, wenn ich es nicht überlesen habe, hat sich noch niemand dazu geäußert, wie man die Aufgabe 8 formal beweisen kann. Hat da jemand einen Ansatz?

[wichtel]

Ich finde überall nur diesen G5-Graphen oder italienische Restaurants

Also ich hab's geschafft den Graphen auf Startknoten + 2 Knoten + Endknoten zu kürzen.
Falls du Inspiration brauchst: Setz dich doch in ein italienisches Restaurant :-)

[Bernhard123]

bräucht pls noch nenn tipp zu bsp10, siehe post #30!

[Benny]

Also bei Punkt 10 hab ich das so gemacht mit dem Tree :
hab anfangs nur den Anfangsknoten als Wurzel gestellt, da ja im Pseudocode steht, dass nur der Start State und der Goal State in den Tree kommen.
Dann immer wenn ein successor durch den loop ist, steht dort, dass man den current_node als parent des successors setten muss.
Das hab ich dann einfach so gemacht, dass ich in diesem step den successor an den current_node im Tree angehangt habe. So ensteht bei mir der Tree wenn man am goal ist.
Hoffe das ist korrekt und das hilft dir :P

[Black Sheep]

Zu 8 hab ich hier mal was gefunden, Aufgabe 1.3:

http://www.ke.tu-darmstadt.de/lehre/...ung1-muloe.pdf

[Bernhard123]

edit:gerald is right!

[_gerald_]

Bei mir bekommt er A -> C -> E -> F, das macht insgesamte Kosten von 11.

Edit: Vorher probiert er aber andere Wege, also bei mir schaut sich der Algorithmus jeden Knoten einmal an.

[Bernhard123]

Ja ich habs mir eigentlich eh auch so gedacht wie du sagst, nur das Break from while loop hat mich stutzig gemacht. Springt er da komplett aus der while oder beendet er nur diesen durchgang?

[_gerald_]

also wenn das break ausgefuehrt wird (also wenn er eine loesung hat), dann springt er aus der while schleife.

[Sapientas]

Hab ihr bei 9. die gleichen Ergebnisse?
s = Speicherplatz bei Auffinden eines Endknotens
c = Kosten zum Erreichen des Knotens
e = Welcher Endknoten
a) s = 10, c = 11, e = J
b) s = 12, c = 8, e = T
c) s = 4, c = 20, e = Q
d) s = 3, c = 11, e = J
e) s = 3, c = 11, e = J

PS: Für 10. krieg ich ebenfalls ACEF raus, wobei die Knoten in folgender Reihenfolge untersucht werden: ABDCEF

[Aster62]

Baut 4) eigentlich nur auf die Verwendung einer Closed List auf? Oder gibt es auch Beispiele wo ohne Verwendung einer Closed List die optimale Lösung nicht gefunden wird?
Kann hier übrigens den deutschen Wiki Artikel sehr empfehlen...

Ist Beispiel 6 wirklich in 2 Zeilen zu lösen indem man direkt schliesst, dass h1 oder h2 > h* sein müsste, sofern das max nicht admissible ist und sich diese Aussage aber mit der Angabe widerspricht? Kommt mir irgendwie zu einfach vor... (h* sind die realen Kosten)

[ri_ba]

Wie meinst du das? Das Beispiel im verlinkten PDF baut ja darauf auf, dass die Knoten in der "closed"-Liste dann doch wieder benutzt werden müssen, und man so auf den worst case von 2^n kommt, da sobald der rechteste Knoten in der closed-Liste ist, alles nochmal von vorn beginnt. Das heißt der nächste Knoten auf dem optimalen Pfad wird durch die inkonsistente Heuristik zuletzt betrachtet, usw. Soweit ich mich nicht irre, kann man von rechts auch zwei Knoten wegnehmen, aber an dem dort gegebenen Graphen kann man das wirklich schön erklären.

Und im PDF, was eigentlich zu Beispiel 8 verlinkt wurde, ist die letzte Aufgabe gleich unserer Nummer 6. Das PDF (und ich) würden zwar andersherum argumentieren, aber dieser kurze Ansatz scheint doch zu reichen.

[Bernhard123]

Kann jemand die Ergebnisse von Sapientas in Post #42 bestätigen?
Ich hätte da zB.
a) BFS: Es werden die Knoten der Reihe nach von A-J durchlaufen. J goal node. Kosten würde ich sagen wären dann 36, also alle bis man letztendlich bei einem goalnode angelangt ist.

[Aster62]

Wie meinst du das? Das Beispiel im verlinkten PDF baut ja darauf auf, dass die Knoten in der "closed"-Liste dann doch wieder benutzt werden müssen, und man so auf den worst case von 2^n kommt, da sobald der rechteste Knoten in der closed-Liste ist, alles nochmal von vorn beginnt. Das heißt der nächste Knoten auf dem optimalen Pfad wird durch die inkonsistente Heuristik zuletzt betrachtet, usw. Soweit ich mich nicht irre, kann man von rechts auch zwei Knoten wegnehmen, aber an dem dort gegebenen Graphen kann man das wirklich schön erklären.

Und im PDF, was eigentlich zu Beispiel 8 verlinkt wurde, ist die letzte Aufgabe gleich unserer Nummer 6. Das PDF (und ich) würden zwar andersherum argumentieren, aber dieser kurze Ansatz scheint doch zu reichen.

Ich habe hier nicht das PDF aus dem Forum sondern den englischen und deutschen Wiki Eintrag aus der Angabe verwendet. Im deutschen A* Artikel gibt es ein Beispiel für eine zulässige, nicht konsistente Heuristik. Bei diesem wird der optimale Weg blockiert, indem die Knoten die nötig wären bereits in der closed List sind.

Bei deinem Beispiel (pdf) wird doch trotzdem noch die optimale Lösung gefunden, auch wenn der richtige Weg erst zum Schluss betrachtet wird und somit der Worst-Case eintritt.

[Aster62]

Kann jemand die Ergebnisse von Sapientas in Post #42 bestätigen?
Ich hätte da zB.
a) BFS: Es werden die Knoten der Reihe nach von A-J durchlaufen. J goal node. Kosten würde ich sagen wären dann 36, also alle bis man letztendlich bei einem goalnode angelangt ist.

Die Kosten sollten doch mMn die von Start bis Goal sein, bei a) also A->C->J (=11).

Bei Speicher und Goal habe ich die gleichen Ergebnisse wie in #42

Sorry for Doppelpost, bin unterwegs

[NoxMortem]

Edit: Entfernt um weitere Verrwirrung zu verhindern

[Aster62]

Nein. Es wird immer zuerst der Knoten mit den niedrigsten Kosten expanded. Das einzige was dabei beachtet wird, ist dass bei BFS bspw erst alle Knoten auf der Ebene darunter expanded werden etc. Sprich die Reihenfolge in der Queue ist sehr wohl nach Gewichten sortiert.

BFS wird daher A(0),D(=2),E(=3),F(=4),B(=7),C(=8) expanded. Wenn ein Knoten expandiert wird kommen seine Kinder in die Queue. Und die Reihenfolge in der ein Element in die Queue kommt ist essentiell. Sprich die Gewichte geben an in welcher Reihenfolge die "Nachbarn" eines Knotens geholt werden. Wird aber D zuerst expandiert, wird auf der Ebene darunter auch K zuerst expandiert. Meiner Meinung nach wäre das aber Implementierungsabhängig (man könnte auch jede ebene als sortierte Liste verwalten) doch meist list man von Queues und dann wird K(=7) (da D zuerst expandiert wird) auch vor G(=1) drankommen.

BFS schreibt ja nur vor, "expandiere zuerst alle nachbarn DANN expandiere die Nachbarn der expandierten Knoten". Je nachdem in welcher Reihenfolge du die Nachbarn jetzt holst, verwaltest,sortierst macht das schon einen Unterschied.

EDIT:Gibts dazu einen Pseudocode in den Folien an den man sich halten kann?

Ist das nicht eine Erweiterung des BFS, die Uniform-Cost Search (b)?

[NoxMortem]

Korrektur: laut deutschem Wiki hast du Recht!

Die uniforme Kostensuche (Uniform Cost Search) ist eine Erweiterung der Breitensuche für Graphen mit gewichteten Kanten. Der Algorithmus besucht Knoten in Reihenfolge aufsteigender Pfadkosten vom Wurzelknoten (und wird deshalb üblicherweise mit einer Priority Queue implementiert, in der alle noch nicht besuchten Nachbarn bereits besuchter Knoten mit der Pfadlänge als Schlüssel verwaltet werden). Die Optimalität ist nur für nicht-negative Kantengewichte garantiert.

Gut dann ist wohl klar wie BFS und UCS an der Tafel vorzuzeigen sind

[Black Sheep]

Wie habt ihr 8 nun gelöst oder kann man so argumentieren wie in meinem pdf?

[NoxMortem]

Ich habe so argumentiert. (gemäß einem Dokument der TU Darmstadt)
Bei beiden heuristiken kannst du dich maximal um 1 verschlechtern (also pro Schritt) daher gilt:
h(n)<=h(n')+1
woraus du umformen kannst
h(n)-h(n')<=1 und damit auf jedenfall <=c denn wenn c=0 wäre, dann hätten wir das Ziel erreicht

[Aster62]

Nein die Uniform Cost Search expandiert immer den Knoten für den gilt: "Aktuelle Kosten+Weg zu Knoten)" minimal ist. Das kann sehr wohl auch in die Tiefe gehen. BFS geht aber IMMER zuerst alle Knoten einer Ebene durch

So hab ich es verstanden

Hast du eine Quelle für die Verwendung von Gewichtungen beim Standard BFS? Finde in meinen aktuellen Quellen nur dass es die Möglichkeit gibt Gewichtungen einzuführen

[NoxMortem]

Edit: Entfernt um weitere Verrwirrung zu verhindern

[Aster62]

Nein darum frage ich ja ob jemand im Skriptum/Buch einen Pseudocode gesehen hat an den man sich halten kann? Ich würde aber auch sagen, dass man das sehr wohl mit/ohne Gewichtung machen kann an der Tafel und in beiden Fällen die Punkte bekommt. Denn wenn du BFS verstanden hast und vorzeigen kannst geht das sowohl mit als auch ohne. Daher würde ich mir DARUM keine Sorgen machen.

Wenn der Baum nämlich bspw die Nachbarn bereits sortiert speichern würde (was ja nicht so unabwägig ist) dann hättest du bei der Suche keinen mehraufwand denn dein node.nextNeighbour() würde dir ja genau dieses Element bringen.

Stimmt schon, es geht hier nur um das Verständnis, mich hätte es halt trotzdem interessiert, Wissen tut selten weh

Wie habt ihr denn Bsp 5) gezeigt? Meiner Meinung nach ist das genau wie 6 & 7 ein Beispiel, dass man mit freiem Auge und der Definition von admissible & consistent schon erkennt, deshalb Verwirren mich die 2 Punkte pro Beispiel noch ziemlich

[NoxMortem]

Hab den Falschen post oben editiert -.-

Korrektur: laut deutschem Wiki hast du Recht!

Die uniforme Kostensuche (Uniform Cost Search) ist eine Erweiterung der Breitensuche für Graphen mit gewichteten Kanten. Der Algorithmus besucht Knoten in Reihenfolge aufsteigender Pfadkosten vom Wurzelknoten (und wird deshalb üblicherweise mit einer Priority Queue implementiert, in der alle noch nicht besuchten Nachbarn bereits besuchter Knoten mit der Pfadlänge als Schlüssel verwaltet werden). Die Optimalität ist nur für nicht-negative Kantengewichte garantiert.


Gut dann ist wohl klar wie BFS und UCS an der Tafel vorzuzeigen sind

[krischblack]

c) s = 4, c = 20, e = Q

wie kommst du bei c.) auf die Kosten von der Depth-First Search, Speicher und Endpunkt sind mir klar, auch der Algorithmus soweit, nur mit den Kosten verstehe ich das noch nicht ganz

[Bernhard123]

Schon langsam bin ich etwas verwirrt
ich hab zb. die BFS und die anderen methoden bei punkt 9 so angewendet, wie sie im Foliensatz eki_03.pdf angeführt sind.
bei der bfs werden doch keine kosten berücksichtigt im gegesatz zu der UCS?

[Aster62]

Schon langsam bin ich etwas verwirrt
ich hab zb. die BFS und die anderen methoden bei punkt 9 so angewendet, wie sie im Foliensatz eki_03.pdf angeführt sind.
bei der bfs werden doch keine kosten berücksichtigt im gegesatz zu der UCS?

Steht doch mittlerweile auch so im Forum.
Was genau verwirrt dich noch?

[Bernhard123]

die ganzen quotes von nox
also geht er bei der bfs jetzt alle Knoten von A-J der Reihe nach durch, und als Kosten nimmt man den kürzesten Pfad zu J oder die Kosten um ein goal node zu finden?

[Aster62]

die ganzen quotes von nox
also geht er bei der bfs jetzt alle Knoten von A-J der Reihe nach durch, und als Kosten nimmt man den kürzesten Pfad zu J oder die Kosten um ein goal node zu finden?

Schwer zu sagen, da in der Angabe nicht definiert ist welche der 2 Varianten sie wollen. Um es genau zu nehmen, sind die Kosten gar nicht gefragt...

[ri_ba]

Aster62:
Du hast natürlich recht. Ich bin dann auf die Laufzeit gesprungen, anstatt die Lösung. Ich nehme mal meine Müdigkeit als Ausrede

Beispiel 5 ist hier:
http://en.wikipedia.org/wiki/Consistent_heuristic

bzw hier in anderer Notation:
http://reason.cs.uiuc.edu/eyal/class...w6/hw6_sol.pdf

Im zweiten Dokument findet sich auch ein Ansatz für die 4.

[Bernhard123]

PS: Für 10. krieg ich ebenfalls ACEF raus, wobei die Knoten in folgender Reihenfolge untersucht werden: ABDCEF

Ist die Reihenfolge der Untersuchung nicht ABDCDEF? D kommt von der closed wieder auf die open zurück und dann hat es den lowest f value?
Denn eine mögliche Lösung zum überprüfen wäre auch ACDEF oder? Der richtige Pfad schlussendlich ist eh ACEF, nur wegen der Vorhergehensweise des Algos wärs

[Aster62]

Ist die Reihenfolge der Untersuchung nicht ABDCDEF? D kommt von der closed wieder auf die open zurück und dann hat es den lowest f value?
Denn eine mögliche Lösung zum überprüfen wäre auch ACDEF oder? Der richtige Pfad schlussendlich ist eh ACEF, nur wegen der Vorhergehensweise des Algos wärs

Kommt drauf an wie die Closed List implementiert ist. Normalerweise kommt doch von der Closed List nichts auf die Open List zurück, zumindest nicht laut der zu verwendenden Implementierung (Pseudocode), oder?
Ziemlich schwammig irgendwie das ganze :-/

[Bernhard123]

die tafel unleserlich vollschreiben plus ein bisschen nuscheln und das klappt scho irgendwie

[ri_ba]

Ich glaube wenn, dann würden Nodes nur re-opened werden, wenn man sich "verrannt" hat, also man nicht im Ziel ist, aber auch keine Nodes mehr in OPEN sind. So wie ich dich verstanden habe, tust dus nur wieder öffnen, weil es den geringsten Funktionswert hat?

Nachtrag: Das Verrennen würde dann aber nur bei inkonsistenten Heuristiken funktionieren, so wie ich das verstanden habe.

[Bernhard123]

andererseits würd er ja von Node C dann mit den Kosten 4 zu D kommen und wir waren ja schon mal mit Kosten 3 bei D, also würds eigentlich wenig sinn machen nochmals bei D vorbeizuschauen.

[NoxMortem]

Hab mal die überflüssing posts von mir "gelöscht". Vielleicht ist es jetzt für Neuankömmlinge leichter nachvollziehbar.

[ReinhardBla]

Wie habt ihr das Beispiel 6 genau gelöst? Ich hab einfach ein Gegenbeispiel betrachtet, also wenn h nicht admissible ist, dann gibt es einen Knoten bei dem h die Kosten von n zum Ziel überschätzt. Damit das eintritt muss entweder h1 oder h2 die Kosten überschätzen. Nachdem das aber gegen die Annahme aus der Angabe ist, kann das nicht eintreten. Kann man das irgendwie formaler beweisen?

[IdealChain]

eventuell hilfreich für 1+2:
https://vowi.fsinf.at/wiki/Datei:TU_...itung_2010.pdf

Auch hilfreich für Bsp. 5 (vorletzte Seite)!

[damian]

eventuell hilfreich für 1+2:
https://vowi.fsinf.at/wiki/Datei:TU_...itung_2010.pdf

wie kommt man hier beim breitensuche-beweis (seite 4) auf die beiden zeilen I und II, die dann subtrahiert werden? woher kommt die zeweite zeile?

[ReinhardBla]

Ja einfach mir x multiplizieren, prinzipiell wird hier der gleiche Trick angewendet wie bei der Herleitung der Formel für die Partialsummen bei der Geometrischen Reihe, siehe: http://de.wikipedia.org/wiki/Geometr..._Partialsummen

[damian]

Das ist mir schon klar aber wieso darf ich das? Und wieso subtrahiere ich es dann?

Und was heisst auf Seite 5 "wissen wir bereits was das Ergebnis ist"? - woher?

[ReinhardBla]

Was ist dann genau die Schwierigkeit, wenn dir das eh klar ist? Das ist eine einfache Äquivalenumformung, also bei einer Gleichung darfst du linke und rechts etwas hinzumultiplizieren (stark vereinfacht jetzt gesagt). Genauso darfst du links und rechts etwas dazu addieren oder subtrahieren, solange die Gleichung korrekt bleibt. Also linke Seite gleich rechte Seite.

Woher wir das wissen? Ja aus Beispiel 2) Breitensuche, wissen wir, dass unter einem sehr großen d (für das interessieren wir uns eben) das selbe ist wie

[Akilleus]

Was ist mit "overhead" in der 2. Frage gemeint?

[braaains]

Was ist mit "overhead" in der 2. Frage gemeint?

der zusätzliche aufwand, der durch DFID verursacht wird, da der baum mit jeder iteration wieder aufgebaut wird.

[damian]

edit: hat sich erübrigt

[damian]

eventuell hilfreich für 1+2:
https://vowi.fsinf.at/wiki/Datei:TU_...itung_2010.pdf

wie kommt man auf seite 6 auf die letzte Zeile?

[damian]

Kann jemand meine Lösung bestätigen für 10)?

[Sunny]

könnte vielleicht jemand von euch das 1. übungsblatt uploaden? lerne gerade für die alte GAI prüfung, diese beispiele + lösungswege wären dabei sehr hilfreich. danke.