Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Pyramids of Ra Pathfinding Algorithmus

  • 1
  • 2

Werbeanzeige

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

11

11.11.2016, 14:02

Zitat von »BlueCobold«

Die Nummern muss er willkürlich vergeben haben, denn selbst bei diagonalen Schritten sind Anfang und Ende nicht dasselbe Feld. Ich glaube er wollte einfach nur Nummern haben anhand denen er jetzt die Funktionalität des Algorithmus erklärt haben wollte.

Mit dem Hamilton Kreis hat ja erst TGGC angefangen. Das steht so in der Frage aber nicht. Jedes Feld soll ja nur ein mal besucht werden. Wie beim Springerproblem, nur dass die Spielfigur eben auf die angrenzenden Felder bewegt werden kann. Zumindest so verstehe ich den TE.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

12

11.11.2016, 14:15

Wenn man nicht zum Startpunkt zurückkehren muss, dann ist es ein Hamilton-Pfad-Problem. Das ändert aber nichts an der NP-Vollständigkeit.
David Scherfgens Website | Konzentrationstest Polizei

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

13

11.11.2016, 14:17

Zitat von »Schorsch«

Das steht so in der Frage aber nicht.
Das steht in der Frage nicht, das ist aber Aufgabe des von ihm verlinkten Beispiels. Da geht es nicht nur darum alles einmal zu besuchen, sondern auch zum Ausgangspunkt zurückzugehen.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

14

11.11.2016, 14:23

Zitat von »BlueCobold«

Das steht in der Frage nicht, das ist aber Aufgabe des von ihm verlinkten Beispiels. Da geht es nicht nur darum alles einmal zu besuchen, sondern auch zum Ausgangspunkt zurückzugehen.

Das mag sein. Habe nur seinen eigenen Text gelesen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Maggot

Frischling

  • »Maggot« ist der Autor dieses Themas

Beiträge: 51

Wohnort: Wien

Beruf: Software Entwickler

  • Private Nachricht senden

15

11.11.2016, 14:55

Zitat von »BlueCobold«

Die Nummern muss er willkürlich vergeben haben, denn selbst bei diagonalen Schritten sind Anfang und Ende nicht dasselbe Feld. Ich glaube er wollte einfach nur Nummern haben anhand denen er jetzt die Funktionalität des Algorithmus erklärt haben wollte.


Jup das war mein Gedanke, da ich mich noch nicht wirklich durchblicke... Sorry für die Verwirrung :D

Ich will alles einmal besuchen + zum Ausgangspunkt zurückzugehen.

Es liegen halt schon viele Begriffe im Raum und ich steh etwas auf der Leitung. Deshalb dachte ich das es mit einem Visuellen Beispiel leichter wird.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

16

11.11.2016, 15:08

Der Punkt ist, dass das Problem NP-vollständig ist. Das bedeutet, dass es (nach aktuellem Stand der Forschung) keine wesentlich schnellere Lösung gibt als alle möglichen Pfade durchzuprobieren und zu prüfen, ob sie die Bedingung erfüllen (jedes Feld einmal besuchen, Endfeld = Startfeld). Leider wächst die Anzahl möglicher Pfade sehr schnell mit der Anzahl der Felder.

Also versuch doch mal einen Algorithmus zu schreiben, der nach und nach alle möglichen Pfade durchprobiert. Das sollte nicht so schwer sein. Wie schnell das dann läuft, ist eine andere Sache.
David Scherfgens Website | Konzentrationstest Polizei

Maggot

Frischling

  • »Maggot« ist der Autor dieses Themas

Beiträge: 51

Wohnort: Wien

Beruf: Software Entwickler

  • Private Nachricht senden

17

11.11.2016, 15:21

Zitat von »David Scherfgen«

Der Punkt ist, dass das Problem NP-vollständig ist. Das bedeutet, dass es (nach aktuellem Stand der Forschung) keine wesentlich schnellere Lösung gibt als alle möglichen Pfade durchzuprobieren und zu prüfen, ob sie die Bedingung erfüllen (jedes Feld einmal besuchen, Endfeld = Startfeld). Leider wächst die Anzahl möglicher Pfade sehr schnell mit der Anzahl der Felder.

Also versuch doch mal einen Algorithmus zu schreiben, der nach und nach alle möglichen Pfade durchprobiert. Das sollte nicht so schwer sein. Wie schnell das dann läuft, ist eine andere Sache.


Danke für deine Antwort, ich dachte bis eben das es eine allgemeine möglichkeit gibt es zu lösen.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

18

11.11.2016, 15:21

Alles durchzuprobieren ist doch eine allgemeine Möglichkeit. Zwar nicht elegant, aber viel schneller geht es nunmal nicht (vorausgesetzt, dass P != NP).
David Scherfgens Website | Konzentrationstest Polizei

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

19

11.11.2016, 20:31

Zitat von »Maggot«

Ich dachte bis eben das es eine allgemeine möglichkeit gibt es zu lösen.
Ich bin bereits in meinem ersten Post auf diese allgemeine "Loesbarkeit" eingegenagen. Theoretisch ist es loesbar, praktisch nicht fuer grosse Aufgaben, da man zu lange auf die Ausgabe der Loesung warten muss. Und mehr gibts da eigentlich nicht zu sagen.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Werbeanzeige

  • 1
  • 2

Ähnliche Themen