Not logged in. · Lost password · Register

Page:  previous  1  2 
MiriTheRing
Member since Oct 2011
38 posts
In reply to post ID 148525
Ja, andernfalls wäre das "ensures no infinite loops" glaub ich gar nicht erfüllbar...
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.
Jazzpirate
Member since Oct 2016
803 posts
In reply to post ID 148528
+1 Shadow992
Wenn ich jetzt DFS als Statemachine implementieren will
Oh gott, bitte nicht :D

   
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.
Knoten/Nodes KÖNNEN es eben nicht sein ;)

Aber states werden (im sinne dieses Übungsblattes) definiert in den slides auf den Seiten 98ff ;)

etzt bin ich auch verwirrt, ich habe "ensures no infinite loops" als auf die states bezogen verstanden
Dann hast du das richtig verstanden :)

Nachdem die knoten die dinger im baum sind kann ich da doch gar keine loops haben.
Richtig. Weil Nodes =/= States. Eine "infinite loops" in den states führt halt zu einem unendlich langen Pfad im Baum.

...macht das irgendwie sinn...?
Vvalter
Member since Dec 2012
119 posts
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?
Shadow992
Member since Jan 2014
290 posts
Quote by Vvalter:
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.
Jazzpirate
Member since Oct 2016
803 posts
In reply to post #18
+1 Shadow992
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?

What Shadow992 said. Aber es kommt natürlich drauf an wie du die ganze Situation modellierst. Auf allen Slides zum Thema haben wir allerdings Städte als States modelliert; insofern scheint mir alles andere unsinnig.

Wie ich zum Knoten gekommen bin oder der fringe ist dann egal?
Dafür, dass du in ner Endlosschleife gefangen bist ist wie du hingekommen bist zunächst egal, ja (der fringe ist natürlich insofern nicht egal, als dass der regelmäßig die selben states beinhaltet, sonst wär's ja keine Schleife...)

Guckt euch vielleicht nochmal die slides 154ff an; da macht er DFS für das Rumänien-Beispiel. Offensichtlich bleibt DFS da in einer "Endlosschleife" hängen, aber als search tree ist das eben nur ein unendlicher Pfad, der dadurch entsteht, dass Arad und Sibiu einfach abwechselnd neu expandiert werden.
This post was edited on 2016-11-02, 19:49 by Jazzpirate.
BreakFast
Avatar
Member since Oct 2012
350 posts
+1 Jazzpirate
Quote by Jazzpirate on 2016-11-02, 19:47:
Guckt euch vielleicht nochmal die slides 154ff an; da macht er DFS für das Rumänien-Beispiel. Offensichtlich bleibt DFS da in einer "Endlosschleife" hängen, aber als search tree ist das eben nur ein unendlicher Pfad, der dadurch entsteht, dass Arad und Sibiu einfach abwechselnd neu expandiert werden.

(Es sei angemerkt, dass 154ff im Sinne der PDF-Viewer-Anzeige, nicht der Zahlen auf den Folien, gemeint ist.)
*Ralf
Avatar
Member since Oct 2011
765 posts
Quote by BreakFast:
(Es sei angemerkt, dass 154ff im Sinne der PDF-Viewer-Anzeige, nicht der Zahlen auf den Folien, gemeint ist.)
[Image: https://s15.postimg.org/imqovhjrv/okular.png] Bin verwirrt...  :scared:
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:  previous  1  2 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen