Frage von theanker, 241

Java - rekursiv - Haus vom Nikolaus?

Hallo Leute, Ich hab eine ziemlich einfache Frage, uns war soll ich in java rekursiv die Anzahl von Möglichkeiten bestimmen das Haus vom Nikolaus zu zeichnen. Jedoch kann ich beim besten willen mir nicht vorstellen wie ich das machen soll. Also ich weiß nicht wie ich vorgehen muss. Wär das ein kürzeste Wege Problem hätte ich den Dijkstra implementiert aber so hab ich absolut keine Ahnung was ich machen soll. Kann mir da einer Helfen ? Wie würdet ihr vorgehen oder welchen Algorithmus würdet ihr zu Hilfe herbei ziehen?

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von Roach5, 184

Du suchst nach einem Eulerweg und hier speziell nach der Anzahl an Möglichkeiten, Eulerwege abzugehen.

Anfangs- und Endpunkte müssen die beiden unteren Knoten sein (da diese die zwei Knoten mit ungeradem Grad gibt, dies gilt im Allgemeinen immer, wenn es zwei gibt, und es gibt entweder zwei oder garkeine). Wir nennen diese Knoten A und B, den Knoten über A 1, den über B 2 und den "Dachknoten" 3. Algorithmisch finden wir den Eulerweg folgendermaßen:

1. G' := G
2. Finde einen AB-Weg Weg W //Anderer Algorithmus
3. While(E(G') ist nicht leer)
     1) Wähle v,v' in V(W)
     2) Finde einen vv'-Weg W' in G'
     3) Verschmelze W mit W'
     4) E(G') -> E(G')\E(W)
4. Gib W aus.

Das ganze fängt also mit einem AB-Weg an und vergisst alle Kanten, die bereits benutzt wurden. Aus den übrigen Kanten werden jetzt wieder Wege gesucht und diese drangeheftet usw. Dass wir immer unsere "Teilwege" W' in bereits besuchten Knoten von unserer temporären Version von W anfangen und enden lassen, garantiert, dass wir keine Verhäddelungen bekommen, und immer in der richtigen Richtung auskommen. Jetzt einfach alle verschiedenen Möglichkeiten ausprobieren und du kommst auf das Ergebnis.

LG

Antwort
von gummiwipfel, 163

Was mir spontan (unabhängig von Java, da weiß ich nicht welche eingebauten Datenstrukturen du verwenden könntest) einfällt wäre eine ganz naive Möglichkeit: Bastel dir einen ungerichteten Graphen und lass bei jedem Aufruf deiner Suchfunktion in jede Richtung, ausgehend vom zuletzt erreichten Knoten, weitersuchen (also für alle Möglichkeiten die Funktion wieder aufrufen).
Diese Suchfunktion musst du dann für jeden Knoten einmal aufrufen, also sie von jedem Knoten aus starten lassen.
Immer dann, wenn jede Kante besucht wurde, hast du wieder eine Möglichkeit gefunden.

Was du dafür feststellen musst ist welche der Richtungen aus einem Knoten noch nicht gewählt wurden (also solltest du wohl jede Kante markieren, die du bereits besucht hast).

Im Prinzip baust du einfach nur einen Suchbaum auf um alle Möglichkeiten einmal testen zu können. Solltest du damit schon einmal etwas zu tun gehabt haben: bei Computerschach wird meist ein ähnlicher Suchbaum aufgebaut, dort aber auf Grund der vielen Möglichkeiten nur bis zu einer gewissen Tiefe. Beim Haus vom Nikolaus solltest du aber in angemessener Zeit durch alle Möglichkeiten durchkommen.

Keine passende Antwort gefunden?

Fragen Sie die Community