Algorithmus Graph

[triopsfreak]

Also, ich habe ein 2-Dimensionales Array und will einen Weg berechnen, mit dem ich von einem beliebigen Punkt, irgendwo mitten im Array, mit einer gegeben Anzahl Schritte so viele Punkte wie möglich einzusammeln und dann wieder am Start anzukommen. Die Elemente im Array haben dazu eine Methode, getPoints(), die liefert die Anzahl der Punkte. Ich habe mir schon den A* Algorithmus angeschaut, der ist aber nicht so ganz das, was ich brauche, oder doch?

 

[Private Void]

Ein einschlägig bekannter Algorithmus fällt mir momentan dazu nicht ein, das klingt für mich aber auf jeden Fall schonmal nach Rekursion und Tiefensuche.

 

[Illuvatar]

Wenn ich dich richtig verstehe, solltest du vielleicht mal nach "Travelling Salesman Problem" suchen.
In dem Fall könnte das allerdings (falls dein Array nicht relativ klein ist) beliebig kompliziert werden...

 

[Ark]

Jupp, stinkt gewaltig nach NPC. Vielleicht findest du hier ein Problem, das schon auf deines zu passen scheint: Karps 21 NP-vollständige Probleme ? Wikipedia Für mich sieht es jedenfalls nach einer Mischung aus Rucksack und Handlungsreisendem aus. (Oder mit anderen Worten: ganz, ganz schlecht. )

Sollte dem so tatsächlich sein, wirst du nicht darum herum kommen, Abstriche bei deinen Anforderungen zu machen. Oder du beziehst Hummeln in dein Programm mit ein: Problem des Handlungsreisenden ? Wikipedia

Ark

 

[triopsfreak]

Danke für die Vorschläge, ich werd mir das Zeugs mal anschauen

 

[oopexpert]

Wenn ich witzig sein wollte, würde ich sagen: Ich habe zwar keine Lösung, aber ich interessiere mich für das Problem.

Naja, eigentlich interessiert mich der Anwendungsfall. Magst Du mir sagen, in welchem Zusammenhang dieses Problem behandelt wird?

 

[triopsfreak]

Für ein Onlinegame, in dem es unter anderem darum geht, mit möglichst wenig schritten auf einer karte (das Array) so viele "gute" Felder zu besuchen.

 

[bygones]

Sicher dass ihr mit dem TSP richtig liegt ?

Seine Ausgangssituation ist doch:

Gegeben x Schritte, welcher Pfad von Start nach Start gibt mir die meisten Punkte.

TSP behandelt die kurzmoeglichste Strecke um alle Punkte besucht zu haben.

Er will weder, alle Punkte absuchen, noch die kurzmoeglichste Strecke.

und wenn er sich mit moeglichen lokaler optimierung zufrieden gibt sollte das nicht ein NP komplexes Problem werden

 

[Ark]

und wenn er sich mit moeglichen lokaler optimierung zufrieden gibt sollte das nicht ein NP komplexes Problem werden

Man kann immer die Komplexität runterschrauben, wenn man seine Anforderungen reduziert. Das habe ich aber schon geschrieben. Außerdem hat der TO noch nicht verkündet, dass er sich mit einem lokalen Optimum begnügen würde.

Natürlich haben wir nicht nachgewiesen, dass das Problem in NP fällt, aber es läuft eben (nach unserer Erfahrung) wahrscheinlich darauf hinaus. Für mich sieht es auch mehr nach Rucksack als nach TSP aus. (Dabei entspricht das Rucksackvolumen der Anzahl der Schritte.) Das macht die Sache aber auch nicht besser. TSP ist es insofern, als dass eine unnötig lange Strecke eben Schritte verschwendet, die anders vielleicht hätten besser genutzt werden können.

Ark

 

[bygones]

Man kann immer die Komplexität runterschrauben, wenn man seine Anforderungen reduziert. Das habe ich aber schon geschrieben. Außerdem hat der TO noch nicht verkündet, dass er sich mit einem lokalen Optimum begnügen würde.

hoffen wir mal ;-)

da kannst du dann einfach dem Weg folgen, der dir aktuell immer die hoechste Summe liefert.

 

[Landei]

Wahrscheinlich reicht schon eine Art greedy-Algorithmus: Vom Standpunkt zum nächstgelegenen Punkt gehen und wieder zurück. Schauen was der nächstgelegene Punkt zu dieser Schleife ist, Schleife um diesen Punkt erweitern wenn diese dadurch nicht zu lang wird. Wieder den nächstgelegenen Punkt zur Schleife bestimmen u.s.w.