Wegfindung bei Gebiet aus Zellen => alle Zellen durchlaufen

[amArsch2]

Hi,

mein problem ist folgendes.

ich habe eine Liste mit Zelle
Diese Zellen wissen welche Nachbarzellen an ihnen Grenzen (falls vorhanden)
=> dadurch hab ich eine art Gebiet
dabei ist ideses Gebiet nicht Rechteckig sonder beliebig. Es kann sogar ein loch darin sein

Was ich will?
Ich will von einer gegebenen Startzelle zu einer gewünschten Zielzelle laufen, dabei aber alle Zellen mindestens 1x durchlaufen
Wünschenswert wäre natürlich exakt einmal... aber das ist wohl nicht möglich da wie gesagt das Gebiet sehr unterschiedlich sein kann.
=> Also es soll kurz gesagt der schnellst mögliche weg gefunden werden, aber alle zellen durchlaufen.

Hat jemand eine Idee wie ich das am besten realisieren kann?
Oder hat jemand sogar eine open source lösung dazu, die ich entsprechend meiner wünsche anpassen kann?

Ich selber bin bisher auf keine geeignete Lösung gekommen, die in endlich viel zeil eine Lösung liefert.
Irgend etwas Rekursives mit Backtracking hätte ich mir gedacht, aber ich bevorzuge iteraitive lösungen

Danke
AmArsch

 

[napstermania]

Hallo,

du solltest das Problem auf jeden Fall iterativ lösen, da du bei sehr großen Gebieten schnell die Rekrusionstiefe überschreiten kannst. (Gute Beispiele sind "FloodFill" algorithmen mit rekursiven Lösungen)

Zu deinem Problem gibts es bestimmt keine exakte Lösung aber das TSP (Travelling Salesman Problem) geht schon gut in die Richtiung, welche du benötigst.

Hier mal Beispiel zu einem algo: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php

Ein anderes Beispiel sind algorithmen zum finden der kürzesten Wege http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo7.php

Ich vermute allerdings das du beide techniken benötigst um deine Aufgabenstellung zu meistern, da du einmal alle Zellen anfahren musst (TSP) und zum anderen den kürzesten Weg finden musst.

Ich hoffe ich kontne dir etwas weiterhelfen.

Mfg

 

[amArsch2]

Ja danke,

das hilft mir weiter. ich brauch oft nur einen stoß in die richtige richtung... jetzt weiß ich wie ich weiter vorghenen kann

Vielen Dank