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?
1 Antwort
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