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.
Frage zum zweiten Uebungsblatt
Muss man bei Problem 2.5 das fuer allgemeine Graphen beweisen. Also inklusive (negativ) zyklischen Graphen? Oder darf man annehmen, dass der Suchraum ein Baum oder wenigstens ein DAG ist?
Ich bin mir nicht sicher ob der Name Tree_Search daher kommt…
Man darf grundsätzlich davon ausgehen, dass in Bezug auf die Kapitel (un)informed search alles echte Bäume sind (hence Tree_Search) - insofern, dass der Tree_Search-Algorithmus (für den single-state case) zwangsläufig Bäume (genauer: directed, connected, acyclic, rooted graphs) generiert: Nodes haben Successors, womit wir schonmal directed sind, rooted und connected ergibt sich aus single-state und acyclic ergibt sich dadurch, dass wir nicht (ohne es explizit zu erwähnen) auf widerholung von Knoten überprüfen sondern einfach den fringe über die successor-funktion generieren (daher im Romänien-Beispiel in den Slides irgendwie jedes mal 3 knoten mit der selben Stadt als label…) 
Also der Tree_Search Algorithmus generiert nur Baeume. Aber der Suchraum an sich auf den man die Algorithmen loslaesst koennen schon Zyklen erhalten oder?
Ich glaube was er meint, dass die Graphen Zyklen enthalten können aber der entstehende Baum diesen Graphen „flach klopft“ wodurch Zyklen „abgeschnitten“ werden. Aber prinzipiell ist es auch egal was genau gemeint ist. Am besten ist immer die schwierigsten „Beweise“ (@Dennis ist das Wort nicht etwas unglücklich gewählt? Wäre „Argue“ oder so nicht besser geeignet? Oder erwarten wir hier echt die „offiziellen formalen“ mathematischen Beweise?) zu nehmen, weil der Unterschied echt minimal ist. Das heißt einfach annehmen, dass der Graph Zyklen enthalten kann.
Je nachdem, was du mit Sichraum meinst. Ich drück’s mal so aus - wenn wir für jeden Zustand genau einen Knoten haben, dann kann der Graph zykel enthalten. Ein Zustand kann aber problemlos mehreren Knoten entsprechen.
Nimm das Beispiel aus den Slieds: Wir sind in Rumänien und wollen von Arad nach Bucharest. Arad ist der erste Knoten. Expandieren wir diesen, erhalten wir drei Nachfolger: Sibiu, Timisoara und Zerind; jeder dieser Orte=Zustände entspricht einem neuen Knoten. Expandieren wir jetzt Sibiu, erhalten wir wir neue Knoten; einer davon ist wieder Arad. Das ist ein neuer Knoten, der aber unserem initialen Zustand entspricht. Wenn wir also nicht explizit prüfen, ob ein neu generierter Knoten bereits einem alten Zustand entspricht, erhalten wird also immer einen (zykellosen) Baum, der dann halt unter Umständen unendlich ist - aber Bäume müssen ja nunmal nicht endlich sein 
Beweise müssen nicht streng formal sein; sie müssen aber allgemein gültig und logisch nachvollziehbar sein. Unter „argue“ würd ich mir auch „Durchexerzieren eines halbwegs repräsentativen Beispiels“ vorstellen, das würd ich aber nicht als Beweis durchgehen lassen…
1 „Gefällt mir“
Heisst “Please upload solutions to each exercise individually” so viel wie Einzelabgabe, oder dass man fuer jede Aufgabe eine separate Datei abgeben soll?
Einzelabgabe, ich möchte mal behaupten wie genau die Dateien aussehen, die ihr hochladet ist allen Korrektoren relativ egal. Aber ich persönlich freu mich darüber, wenn alles in einer PDF-Datei ist (bleibt aber Geschmackssache). 
Also heißt nur, dass jeder seine eigene Lösung abgeben soll.
Wann sollen wir denn annehmen die Algorithmen erkennen sich widerholende Zustaende und wann nicht (warum auch immer man das wollen solllte… )?
…korrektur: Was ursprünglich gedacht war war tatsächlich eine Datei pro Aufgabe. Das war aber unter der Annahme, dass man die abgegebenen Dateien auf studOn auch separat kommentieren kann. Turns out, kann man nicht 
Entsprechend… errm, yeah, alles in einer schön formatierten getexten pdf fänd ich auch am schönsten
Ich würde behaupten, ihr solltet davon ausgehen, dass die Algorithmen sich-wiederholende-Zustände allgemein nicht erkennen. In den Slides wurde ja auch immer extra erwähnt, wenn sich was dabei ändert. Davon abgesehen impliziert eben „nicht erkennen“ auch nur „unendlicher Baum“, von dem her wäre die trennung zwischen endlicher Baum / unendlicher Baum sinniger und allgemeiner.
Fällt das denn bei irgendeiner Aufgabe in’s Gewicht? Ich glaube nicht, oder…?
Wenn ich das richtig sehe faellt das nur bei der letzten Frage von Aufgabe 6 ins Gewicht, dort aber massiv
Edit: Auch die Tabelle in Aufgabe 1 geht dann etwas anders…
Mir ist bei Aufgabe 4 noch einiges unklar…
- Bedeutet constant costs dass alle actions die gleichen kosten haben?
- Ich nehme mal an das node in der vierten frage bezieht sich dann auf den node im search tree, bedeutet das, dass zwei unterschiedliche knoten (= nodes) die aber den gleichen state haben unterschiedliche gewichte haben koennen?
Och, solang’s abzählbar bleibt würd ich das nicht „massiv“ nennen…
Nee, dann würd ich halt tatsächlich ne Fallunterscheidung angeben, die eine Textzeile mehr oder weniger bei der Lösung wird euch doch nicht umbringen, oder?
Jupp. (Siehe step cost in den slides)
Ja, andernfalls wäre das „ensures no infinite loops“ glaub ich gar nicht erfüllbar…
Jetzt habt ihr zwei mich aber gewaltig verwirrt.
Wenn ich über den Baum traversiere und mir den aktuellen State merke, dann ist der aktuelle State doch definiert über die Gesamtheit der bisher besuchten Knoten + dem aktuellen Knoten oder etwa nicht?
Das heißt eine Traversierung von A->B->C ist einzigartig, selbst mit Schleifen, denn dann wäre der State ja (z.B.) A->B->C->A->B->C.
Wenn ich darüber noch etwas länger nachdenke, stehen und fallen diese ganzen Algorithmen ja auch gewissermaßen damit, dass jeder State einzigartig ist, ansonsten wüsste keiner der vorgestellten Algorithmen von welchem State in welchem er wechseln soll?
Demnach gibt es pro Baum/Graph jeden state nur genau einmal? Das heißt wie erreiche ich jetzt, dass zwei unterschiedliche Knoten denselben state besitzen bzw. repräsentieren?
Nicht notwendigerweise… was ein state ist hängt von dem konkreten Problem ab. In dem Beispiel in Rumänien sind zum Beispiel die Städte die States. Das was du in der Frage mit „state“ zu meinen scheinst entspricht eher einer Action-sequence…
Wie würdest du denn A,B,C nennen wollen, wenn nicht states? Knoten im Baum können’s ja nicht sein, dennn die wiederholen sich ja wirklich nicht…
Nun gut, was ein State ist, ist demnach wohl Definitionssache. Das hab ich in der Vorlesung wohl übersehen/überhört, dass wir die Städte als States definieren. Afaik könnte ich genau so gut die Action-Sequence als States hernehmen. Wenn man sich das Ganze als State-Maschine vorstellt, muss man die States sogar über die Gesamtheit der bisherigen Aktionen definieren.
Nur als Beispiel ein Baum mit folgendem Aufbau:
A
/ \
B CWenn ich jetzt DFS als Statemachine implementieren will, reicht es mir nicht zu sagen, dass jeder Knoten genau ein State ist, denn dann würde die State-Machine in etwa so aussehen:
StartState: A, Übergang möglich nach B und C
1. Durchlauf: Start bei A mit Regel "Gehe zu B"
2. Durchlauf: State-Regel anwenden und nach B gehen
3. Durchlauf: B hat als Regel wieder zu A zu gehen (weil keine Kindknoten)
Genau ab jetzt gibt es bei der Knoten=State Definition ein Problem, denn wir sind jetzt wieder im State A und State A hat als Regel ja definiert "Gehe zu B".
Das heißt wir würden jetzt zwischen A und B hin und herspringen.
4. Durchlauf: Gehe zu B
5. ...Definiert man die States jedoch über die Action-Sequence, lässt sich das wunderbar als StateMachine implementieren:
1. Durchlauf: Start bei A mit Regel "Gehe zu B" --> CurrState: "A"
2. Durchlauf: State-Regel anwenden und nach B gehen --> CurrState: "A->B"
3. Durchlauf: B hat als Regel wieder zu A zu gehen (weil keine Kindknoten) --> CurrState: "A->B->A"
Ab jetzt unterscheidet sich der State im vergleich zu vorher, weswegen das Anwenden einer anderen Regel deterministisch ist:
4. Durchlauf: State: "A->B->A" hat als Regel zu C zu gehen --> CurrState: "A->B->A->C"
5. ...Einfach Knoten/Nodes oder halt Teile von States.
Edit:
Wenn die Definition über Action-Sequence etwas ungewohnt/unsauber ist, kann man auch anfangen „mit zu zählen wie oft der Knoten besucht wurde“, also:
A0 --> B0 --> A1 --> C0 Jetzt bin ich auch verwirrt, ich habe „ensures no infinite loops“ als auf die states bezogen verstanden, und ob das geht hat damit zu tun ob man endlich viele states hat oder nicht…( wenn man als infinte loop auch etwas betrachtet was
immer nur in eine (falsche) richtung rennt)
Nachdem die knoten die dinger im baum sind kann ich da doch gar keine loops haben.
Oh gott, bitte nicht
Einfach Knoten/Nodes oder halt Teile von States.
[/quote]
Knoten/Nodes KÖNNEN es eben nicht sein
Aber states werden (im sinne dieses Übungsblattes) definiert in den slides auf den Seiten 98ff
Dann hast du das richtig verstanden 
Richtig. Weil Nodes =/= States. Eine „infinite loops“ in den states führt halt zu einem unendlich langen Pfad im Baum.
…macht das irgendwie sinn…?
1 „Gefällt mir“
Also ich bin nun auch völlig verwirrt.
Kurz am Beispiel: Wenn mein Algorithmus von Arad nach Zerind läuft und dann wieder nach Arad und immer so weiter, dann hat er doch immer wieder den selben Zustand und ist in einer “infinite loop” oder?
Wie ich zum Knoten gekommen bin oder der fringe ist dann egal?
Ich versuch mich mal an einer Erklärung, dann seh ich auch gleich, obs so wie ich es jetzt verstanden habe passt (Ich hasse solche „Definitionssachen“ da kann man immer so schnell durheinander kommen):
Du bist immer in den zwei selben States, nämlich einmal im State „Zerid“ und einmal im State „Arad“. Wie du da hingekommen bist, ist für unsere Definition egal, bei einer konkreten Implementierung musst du aber die States dementsprechend erweitern (DFS muss sich einen " Stack an States" merken, usw.). Aber ohne alles und wie in der Vorlesung definiert, ist ein State genau eine Stadt. Ein Knoten repräsentiert genau eine Stadt und damit genau einen State, wobei ein State in mehreren Knoten vorkommen kann.
Das heißt: Ja dann bist du in einer infinite Loop und springst immer zwiachen zwei States hin und her. Jedoch springst du nicht zwischen zwei Knoten hin und her, weil Knoten per Definition keine Loops haben, sondern lediglich „unendlich tief gehen können“. Das heißt bei jedem Hin und Herspringen schaust du dir jedesmal zwei neue Knoten an, die aber denselben State repräsentieren.