Not logged in. · Lost password · Register

Page:  1  2  next 
Vvalter
Member since Dec 2012
119 posts
Subject: 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...
Jazzpirate
Member since Oct 2016
803 posts
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...) ;)
Vvalter
Member since Dec 2012
119 posts
Also der Tree_Search Algorithmus generiert nur Baeume. Aber der Suchraum an sich auf den man die Algorithmen loslaesst koennen schon Zyklen erhalten oder?
Shadow992
Member since Jan 2014
290 posts
Quote by Vvalter:
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.
This post was edited 3 times, last on 2016-10-31, 19:33 by Shadow992.
Jazzpirate
Member since Oct 2016
803 posts
Also der Tree_Search Algorithmus generiert nur Baeume. Aber der Suchraum an sich auf den man die Algorithmen loslaesst koennen schon Zyklen erhalten oder?
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 ;)
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #4
+1 Shadow992
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?
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...
pawe
Member since Oct 2014
11 posts
Heisst "Please upload solutions to each exercise individually" so viel wie Einzelabgabe, oder dass man fuer jede Aufgabe eine separate Datei abgeben soll?
Shadow992
Member since Jan 2014
290 posts
Quote by pawe:
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). :D

Also heißt nur, dass jeder seine eigene Lösung abgeben soll.
MiriTheRing
Member since Oct 2011
38 posts
Wann sollen wir denn annehmen die Algorithmen erkennen sich widerholende Zustaende und wann nicht (warum auch immer man das wollen solllte... )?
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #8
Aber ich persönlich freu mich darüber, wenn alles in einer PDF-Datei ist (bleibt aber Geschmackssache). :D
...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 ;)

Wann sollen wir denn annehmen die Algorithmen erkennen sich widerholende Zustaende und wann nicht (warum auch immer man das wollen solllte... )?
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...?
MiriTheRing
Member since Oct 2011
38 posts
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...
1. Bedeutet constant costs dass alle actions die gleichen kosten haben?
2. 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?
This post was edited on 2016-11-02, 13:23 by MiriTheRing.
Jazzpirate
Member since Oct 2016
803 posts
Wenn ich das richtig sehe faellt das nur bei der letzten Frage von Aufgabe 6 ins Gewicht, dort aber massiv ;)
Och, solang's abzählbar bleibt würd ich das nicht "massiv" nennen... :D
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? ;)

1. Bedeutet constant costs dass alle actions die gleichen kosten haben?
Jupp. (Siehe step cost in den slides)
2. 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?
Ja, andernfalls wäre das "ensures no infinite loops" glaub ich gar nicht erfüllbar...
Shadow992
Member since Jan 2014
290 posts
Quote by Jazzpirate:
2. 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?
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?
Jazzpirate
Member since Oct 2016
803 posts
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?
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...
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.
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... ;)
This post was edited on 2016-11-02, 14:56 by Jazzpirate.
Shadow992
Member since Jan 2014
290 posts
Quote by Jazzpirate:
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...
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   C

Wenn 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. ...

Quote by Jazzpirate:
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... ;)

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
This post was edited on 2016-11-02, 15:37 by Shadow992.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen