theo. Fragen Aufgabe 2 A-star

Moderator: Serious Games

Toa
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 121
Registriert: 16. Feb 2011 23:58

theo. Fragen Aufgabe 2 A-star

Beitrag von Toa » 25. Apr 2012 20:32

Huhu,

ich verstehe nicht wie die Heuristik kosten berechnet werden. Im Text steht es sei Luftlinie, also euklidische Norm. Aber meiner Meinung nach passen dafür die Werte von h nicht. Ich mein wie kann man bei 2 Feldern mehr Abstand auf einmal 4 höhere Kosten haben? Ein Beispiel für einen Heuristikwert wäre nett. Grüße T0a

FloM-KOM
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 279
Registriert: 27. Apr 2010 17:20

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von FloM-KOM » 26. Apr 2012 14:45

Hallo,

in die Folien haben sich bei der Überarbeitung für dieses Jahr auf 2 Feldern Tippfehler für h eingeschlichen. Das wird aktualisiert, Danke für den Hinweis.

Ansonsten ist die Heuristik die Anzahl der Felder die man auf dem kürzesten Weg inklusive der Verwendung von Diagonalen unter dem Ignorieren von Hindernissen von dem bewerteten Feld zum Zielfeld braucht. Da die Distanz über diskrete Felder geht ist es nicht die euklidische Distanz, sondern die diskrete Chebyshev/Diagonale Distanz der Felder (http://en.wikipedia.org/wiki/Chebyshev_distance). Luftlinie bezieht sich hierbei darauf daß die Hindernisse dabei nicht betrachtet werden. Die Folien werden hierfür auch angepasst.

Angi
Neuling
Neuling
Beiträge: 9
Registriert: 3. Okt 2007 18:42

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Angi » 28. Apr 2012 13:27

Was bedeutet genau "Ignorieren der Hindernisse"?

Um z.B. auf dem Übungsblatt von dem Feld rechts von S zu dem ersten weißen Feld direkt oben drüber (oberhalb des schwarzen Feldes) zu gelangen, ist das ein Schritt (so tun, als ob das schwarze Feld überhaupt nicht existieren würde), oder sind es 2 (so tun, als wär das schwarze Feld ein normales weißes Feld)?

Toa
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 121
Registriert: 16. Feb 2011 23:58

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Toa » 28. Apr 2012 14:43

Naja, du zählst die schwarzen Felder natürlich mit. Ansonsten würde die Heuristik ja verfälscht werden. Schau dir das oberste rechte Kästchen in den Folien an
mit h = 3 .. ein Feld diagonal und 2 nach oben. Bzw. schau dir genrell mal die Folien an.

Grüße T0a

Goma
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Goma » 2. Mai 2012 11:00

Hi,
was ich nicht ganz verstehe ist, wie entschieden wird ob das Feld "visited-node" oder nur "open-node" wird, auf der Folie steht alle "Highscore Nodes" werden Visited.
Hierzu nun 3 Fragen:
1) Wie berechnet sich die Highscore Node, bzw. wie genau erkenn ich die? Der kürzeste Weg also "s" kann es nicht sein, da auf der Folie ja auch welche mit höheren kosten plötzlich visited sind?
2.1) Wieso geht er auf Seite 77 der Folie nochmal nach unten Links wo "s"=8 ist und setzt es auf visited?
2.2) und wieso macht er das gleiche dann nicht auch mit den Feldern rechts neben dran, die alle die gleichen Kosten haben?
3) Die Pfeile gehen immer von dem am Ende gelaufenen Feld aus oder kann man das selber entscheiden von welchem der 2-3 angrenzenden man gelaufen kommt?

Direkte Frage noch zur Aufgabe:
Ich habe 3 mögliche wege mit den gleichen kosten, da wir diagonal ja auch nur als 1 und nicht 1,5 zählen, darf ich mir da nun einen als "gelaufenen" Weg nehmen oder gibt es da auch nochmal einen der "richtiger" wäre?

Vielen Dank für die Erklärung.

FloM-KOM
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 279
Registriert: 27. Apr 2010 17:20

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von FloM-KOM » 2. Mai 2012 15:29

Goma hat geschrieben:Hi,
was ich nicht ganz verstehe ist, wie entschieden wird ob das Feld "visited-node" oder nur "open-node" wird, auf der Folie steht alle "Highscore Nodes" werden Visited.
Hierzu nun 3 Fragen:
1) Wie berechnet sich die Highscore Node, bzw. wie genau erkenn ich die? Der kürzeste Weg also "s" kann es nicht sein, da auf der Folie ja auch welche mit höheren kosten plötzlich visited sind?
Der "Highscore" node ist derjenige mit dem geringsten Score s.
Goma hat geschrieben: 2.1) Wieso geht er auf Seite 77 der Folie nochmal nach unten Links wo "s"=8 ist und setzt es auf visited?
Das "v" ist ein Tippfehler.
Goma hat geschrieben: 2.2) und wieso macht er das gleiche dann nicht auch mit den Feldern rechts neben dran, die alle die gleichen Kosten haben?
3) Die Pfeile gehen immer von dem am Ende gelaufenen Feld aus oder kann man das selber entscheiden von welchem der 2-3 angrenzenden man gelaufen kommt?
Die Pfeile geben an von welchem Feld aus der Weg der bis dahin berechnet wurde führt, oder andersrum von welchem Feld aus das betreffende Feld auf die Open-Node-Liste gesetzt wurde.
Goma hat geschrieben: Direkte Frage noch zur Aufgabe:
Ich habe 3 mögliche wege mit den gleichen kosten, da wir diagonal ja auch nur als 1 und nicht 1,5 zählen, darf ich mir da nun einen als "gelaufenen" Weg nehmen oder gibt es da auch nochmal einen der "richtiger" wäre?

Vielen Dank für die Erklärung.
Der endgültige Weg ergibt sich sobald der Zielknoten auf der Open-Node-Liste eingefügt wird, und dann über den Weg auf dem der Algorithmus dort hingekommen ist.

tobi11
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 8. Okt 2009 20:32

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von tobi11 » 3. Mai 2012 16:51

FloM-KOM hat geschrieben:
Goma hat geschrieben: Direkte Frage noch zur Aufgabe:
Ich habe 3 mögliche wege mit den gleichen kosten, da wir diagonal ja auch nur als 1 und nicht 1,5 zählen, darf ich mir da nun einen als "gelaufenen" Weg nehmen oder gibt es da auch nochmal einen der "richtiger" wäre?

Vielen Dank für die Erklärung.
Der endgültige Weg ergibt sich sobald der Zielknoten auf der Open-Node-Liste eingefügt wird, und dann über den Weg auf dem der Algorithmus dort hingekommen ist.
Aber was passiert, wenn mehrere Felder minimale Kosten haben? Sollen wir uns einfach ein Feld aussuchen oder sollen wir dabei in einer bestimmten Weise vorgehen?

Außerdem:
Sollen wir lediglich das Endergebnis abegeben oder für jeden Schritt so ein Bild abgeben?

FloM-KOM
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 279
Registriert: 27. Apr 2010 17:20

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von FloM-KOM » 3. Mai 2012 17:01

Es reicht das Endergebnis abzugeben. Wenn es vom Score her äquivalente Felder gibt kann ein beliebiges ausgewählt werden.

Elementer
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 14. Mär 2009 14:56

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Elementer » 6. Mai 2012 16:18

Mich würde noch interessieren, wenn beispielsweise zwei Felder den gleichen score haben und ich mir dann deren Nachbaren anschaue. Wie setze ich dann korrekt den Vorgängerzeiger? Wird das willkührlich gemacht? Weil ich kann den Zeiger des Nachbarn ja entweder auf das eine oder andere Feld setzen, das sie beide den gleichen Score haben. In den Folien siehts aus als wäre es einfach gegen den Uhrzeigersinn gegangen.

FloM-KOM
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 279
Registriert: 27. Apr 2010 17:20

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von FloM-KOM » 6. Mai 2012 17:31

Beim Abarbeiten nimmt sich der Algorithmus ja immer eines der Felder (also nacheinander und nicht parallel), besucht dieses und schaut dann von dort aus die Nachbarfelder an. Dementsprechend zeigen die Pfeile von diesen Nachbarfeldern aus auf den besuchten Knoten.

Elementer
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 14. Mär 2009 14:56

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Elementer » 6. Mai 2012 23:18

Ja genau, aber das Abarbeiten kann ja von rechts nach links oder umgekehrt gehen und daher wäre auch die Richtung der Vorgängerzeiger anders angeordnet, ist das korrekt? Also es gibt nicht nur EINE Lösung.

Goma
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Goma » 7. Mai 2012 00:36

Ja, das ist ja das was ich auch schon Frage aber keine direkte Antwort drauf bekam, auch das mit den Pfeilen hat mich verwirrt, da die Vorlage ja falsch ist.

Habe mir nun auch einen der Wege rausgenommen und bin diesen gegangen, und die Pfeile habe ich jedes mal so gezeichnet wie ich am schnellsten laufen würde von dem aktuellen Feld dann.
Denke anders gehts nicht und wird wohl auch so richtig sein, wie der "Computer" den schnellsten Weg berechnet wenn es z.B. 3 schnellste Wege gibt, weiss ich nicht, denke aber er nimmt dann auch einfach random bzw. den ersten den er angefasst hat.
Normal kenn ich es auch so das Diagonal höhere kosten hat (weil auch weiter weg), hätte man das in der Übung eingebaut, würde sich das von selber erklären, dann gibts wirklich nur einen.

Elementer
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 14. Mär 2009 14:56

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von Elementer » 7. Mai 2012 13:13

Jo genau, das hab ich mir dann auch so gedacht. Also das man einfach den schnellsten Weg geht und so die Vorgängerzeiger festlegt. Aber das sollten wir Morgen in der Übung nochmal ansprechen.

FloM-KOM
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 279
Registriert: 27. Apr 2010 17:20

Re: theo. Fragen Aufgabe 2 A-star

Beitrag von FloM-KOM » 7. Mai 2012 14:48

Ja, es gibt keine eindeutige Lösung da mehrere Felder den gleichen Score bekommen können. Bei einer Umsetzung würde man die Open-Node-Liste als sortierte Datenstruktur halten, dann ergäbe sich der nächste Knoten aus der Sortierung (als der erste auf der Liste). Die Reihenfolge die daraus folgt ergibt dann auch die Richtungen der Pfeile.

Alle abgegebenen Lösungen die einen richtigen Weg ergeben und in sich schlüssig sind werden als richtig bewertet in der Übung.

Antworten

Zurück zu „Serious Games“