Backtracking

[relyyy]

Hallo, da ich heute meine mündliche Abiturprüfung habe, nochmal eine schnelle Frage.


Aufgabe ist folgende:
Man soll von A wieder zu A kommen und dabei jeden Buchstaben genau einmal benutzen.
Bild:

Ich weiß nicht, wie ich auf den Code dazu komme.

Wie Backtracking in der Theorie funktioniert weiß ich, kann es aber auf diese Aufgabe nicht anwenden.
Wäre super wenn mir jemand helfen könnte.

Mit freundlichen Grüßen,
relyyy

 

[Salohcin]

Abend relyyy!

Hoffe das hilft dir:

Das ist ganz einfach, du kannst zum Beispiel einen Stapel (Stack) benutzen. Du markierst und packst zuerst A auf den Stapel und suchst immer wieder einen unmarkierten Nachfolgerknoten von dem obersten Element auf dem Stapel. Hat dieser allerdings keine Nachfolger kannst du diesen vom Stapel runterschmeissen.

Bsp.:

Spoiler: klappauf

A
A --> F
A --> F --> E
A --> F --> E --> D
A --> F --> E --> D --> C //C hat keine Nachfolger mehr
A --> F --> E --> D
A --> F --> E --> D --> B //B hat keine Nachfolger mehr
A --> F --> E --> D //D hat keine Nachfolger mehr
A --> F --> E //E hat keine Nachfolger mehr
A --> F //F hat keine Nachfolger mehr
A //A hat keine Nachfolger mehr

ABBRUCH WEIL STAPEL LEER

Gruß
Salohcin