Wegfinugs Alogorythmus gesucht
-
guten morgen!
ich suche nach tipps, links, hilfestellungen, code, ect für ein pathfinding's problem:
ich habe ein labyrinth, das geschlossen ist -> es gibt kein weg für rein und raus "man" steht irgendwo mitten im dem labyrinth und nun suche ich nach einem algorythmus der berechnen soll welchen weg man nehmen mus um jedes "Feld" min 1x zu betreten. dabei soll der Algorythmus den schnellsten weg suchen
XXXXXXXXX
X X s X
X X X X <-- hier kann man noch nicht viel falsch machen, um mit Wenigst
X X x X Beweggung jedes feld einmal betreten zu haben
X X
XXXXXXXXXich hoffe ihr habt mich komplett verstanden
und danke im vorauf für jede hilfreiche antwortgruss reima
-
du könntest eine art rekursiven A* algorithmus machen, bei jeder abzweigung machst du einen neuen weg. wenn du durch bist, nimmst du am ende den, der die kleinste zahl hat wenn er wieder beim startpunkt angekommen ist
-
Hm, das klingt aber recht aufwendig.
Ich stell mir das Ding grad mal als Graphen vor. Jeder Verzeweigungspunkt ist ein Knoten. Die Kanten dazwischen haben sind die Wege zwischen den Punkten. Sie werden nach Weglänge gewichtet. Wenn man es jetzt schafft dadrin (zunächst) geschickt ein paar Kanten wegzulassen(immer den kürzesten Weg), sodaß alle Knoten geraden Knotengrad haben, dann findet man leicht einen Rundweg, ohne was doppelt zu gehen. Möglicherweise ist jetzt aber was in mehrere Teile zerfallen. Jetzt könnte man versuchen die weggelassenen Kanten auf minimale Art&Weise wieder dazuzunehmen. Da es immer die kürzesten sind ist es vielleicht nicht so schlimm, daß man sie zweimal gehen muß. Aber einen Beweis, daß es optimal wird hab ich grad auch nicht in der Tasche.
