[gelöst]Landaufteilung mit Graphen?
-
Ich habe folgendes Problem: ich möchte auf einem Schachbrett der Größe 6x6 zwei Figuren platzieren. Anschließend möchte ich alle Wege der Länge 9 finden, die die beiden Felder auf denen die Figuren stehen, beinhalten. Dabei ist nur die Bewegung in den Himmelsrichtungen und stets auch nur ein Feld pro Zug erlaubt. Das könnten z.B. alle Wege sein die in dem Feld von Figur A beginnen und Figur B enden sein. Müssen sie aber nicht. Die Wege dürfen überall beginnen und überall enden. Einzige Bedingung ist, daß sie durch die beiden Felder der Figuren führen und genau die Länge 9 haben. Hier eine grafische Darstellung:
1 2 3 4 5 6 +---+---+---+---+---+---+ A | | | | | | | +---+---+---+---+---+---+ B | | S | | | | | +---+---+---+---+---+---+ C | | | | | | | +---+---+---+---+---+---+ D | | | | | | | +---+---+---+---+---+---+ E | | | Z | | | | +---+---+---+---+---+---+ F | | | | | | | +---+---+---+---+---+---+ z.B. ein erlaubter Weg: [2B] -> 3B -> 4B -> 5B -> 5C -> 5D -> 5E -> 4E -> [3E] ein anderer erlaubter Weg: 1A -> 1B -> [2B] -> 2C -> 2D -> 2E -> 2F -> 3F -> [3E]Bisher benutze ich ein Backtracking-Algorithmus, der ziemlich dumm in jedem Feld beginnt und alle Wege von diesem Feld aus der Länge 9 findet, die die beiden Felder beinhalten. Also sehr unelegant und dumm. Außerdem kommt er auch mit der weiteren Anforderung nicht klar.
Weitere Anforderung: die Wege dürfen auch verzweigt sein. So sind nun auch alle Wege erlaubt die kürzer als 9 Einheiten sind. So sind z.B. nun auch alle Wege erlaubt die die Länge 8 haben. Dann muß allerdings das fehlende 9te Glied mit dem bisherigen Weg verbunden sein. Weiter sind auch alle Wege der Länge 7 erlaubt, bei denen die 2 restlichen Einheiten irgendwie mit dem Weg verbunden sind. Wieder ein Beispiel:
nun auch erlaubte Wege: [2B] -> 3B -> 4B -> 5B -> 6B | -> 4C -> 4D -> 4E -> [3E]Auch hier müssen die Wege nicht auf dem Start und Zielfeld beginnen bzw. enden, sondern müssen sie nur beinhalten.
Hier versagt das Backtracking und ich muß die Wege ziemlich naiv bewerten, da an die Wege noch andere Bedingungen gestellt werden und somit aussichtsreiche Kandidaten aussortieren.
Nun frage ich mich ob es eine bessere (und schnellere) Alternative zum "dummen" Backtracking gibt. Ich habe dabei an Graphen gedacht und bin mir aber nicht sicher, ob das so das Wahre ist. Daher frage ich hier, wie setze ich das Problem am besten um? Mit Graphen, ...? Welche Algorithmen benutze ich am besten? Gibt es vielleicht eine ganz andere Lösungsmöglichkeit?
Für jegliche Hinweise und Gedanken bin ich sehr dankbar.
EDIT: Falls es wichtig sein sollte ... Das ganze soll in Ansi-C realisiert werden.
-
Der erste Ansatz, der mir so spontan einfällt ist, dass du einfach bei Figur A anfängst, und dann alle Wege suchst, die zu Figur B führen und die maximal 9 züge lang sind. Wenn ein solcher Weg die Länge 9 hat, dann tust du ihn in deine valid-wege-liste. Falls er aber nur z.b. die Länge 7 hat, dann fehlen noch zwei kanten, also nimmst du einfach von diesem Teilweg ausgehend alle Möglichkeiten, noch zwei Kanten an Felder A und B anzuhängen und legst die so entstehenden Wege in deine Liste.
Dieser Ansatz sollte auf jeden Fall schneller sein als der andere und es gibt auch keine doppelten wege (im gegensatz zum ersten Ansatz, da man dort ja einen Weg zweimal findet, wenn man irgendwann vom anderen Ende aus anfängt).
edit: das ist bis jetzt noch recht grob, lässt sich bestimmt noch irgendwie optimieren
edit2: ich sehe gerade, dass ich beim überfliegen deines Posts die "weitere Anforerung" übersehen habe
Dies macht es aber noch einfacher, da du bei einem |weg| < 9 einfach die verbleibenden kanten irgendwo anhängen kannst Und was en Thread-Titel angeht: dafür brauchst du keinen Graphen als Datenstruktur, d.h. du brauchst nicht ein großes Feld im Speicher zu allokieren. Es reicht, wenn du eine Liste von Arrays hast, in die die fertigen Pfade reinkommen, und ein Array, das du zum finden der Pfade benutzt. Aber um die Implementierung kann man sich später auch noch genug Gedanken machen
-
Danke für die Antwort. Das klingt auf jeden Fall systematischer, als wie ich es bisher getan habe. Den ersten Schritt von dir habe ich auch schon umgesetzt. So findet dieser Code alle Wege zwischen Start und Ziel mit Länge<=Maxlänge: http://pastie.org/396608
Als nächstes werde ich mal schauen wie ich erlaubte Wege speichere. Ich denke dabei an ein struct. Sowas hier in der Art:
struct valid_way_s { int length; int way[WAY_MAXLEN]; };Die Länge brauch ich ja im nächsten Schritt um festzustellen, wie viele Stücke ich noch irgendwo an den Weg anfügen muß. Und in valid_way_s.way.[] dachte ich mir packe ich den Weg rein mit folgender logik. Nummeriere das Board durch von 0 (oben links) bis 35 (unten rechts). Der Weg wäre dann eine Reihe von einfachen Zahlen, die das jeweilige Feld bezeichnen. In einem 2Dimensionalen Array sind das dann auch sogar die Offsets von dem jeweiligen Feld zum Beginn des Boards im Speicher.
Allerdings weiß ich noch nicht, wie ich am besten das "Füge die restlichen Stücke irgendwo an" systematisch umsetzen soll. Haste da ne Idee? Mein Gedankengang ist im Moment das auch wieder rekursiv zu machen. Aber es gibt sehr viele Möglichkeiten z.b. 2 Elemente irgendwo an einen Weg der Länge 7 anzufügen.
EDIT: so könnte z.b. das hier ein erlaubter weg sein
erlaubter weg möglichkeiten für 1tes Stück möglichkeit für 2tes Stück (1tes festgelegt) ------------- ---------------------------- ...+---+---+---+... ...+---+---+---+... ...+---+---+---+... ...| | | |... ...| | X | |... ...| | X | X |... ...+---+---+---+... ...+---+---+---+... ...+---+---+---+---+... ...| | 1 | |... ...| X | 1 | X |... ...| X | 1 | 2 | X |... ...+---+---+---+... ...+---+---+---+... ...+---+---+---+---+... ...| | 1 | |... ...| X | 1 | X |... ...| X | 1 | X |... ...+---+---+---+... ...+---+---+---+... ...+---+---+---+... ...| | 1 | |... ...| X | 1 | X |... ...| X | 1 | X |... ...+---+---+---+... ...+---+---+---+... ...+---+---+---+... ...| | 1 | |... ...| X | 1 | X |... ...| X | 1 | X |... ...+---+---+---+... ...+---+---+---+... ...+---+---+---+... ...| | | |... ...| | X | |... ...| | X | |... ...+---+---+---+... ...+---+---+---+... ...+---+---+---+...
-
NDEBUG schrieb:
Allerdings weiß ich noch nicht, wie ich am besten das "Füge die restlichen Stücke irgendwo an" systematisch umsetzen soll. Haste da ne Idee? Mein Gedankengang ist im Moment das auch wieder rekursiv zu machen. Aber es gibt sehr viele Möglichkeiten z.b. 2 Elemente irgendwo an einen Weg der Länge 7 anzufügen.
Das würde ich auch rekursiv machen. Als erstes eine zusätzliche Kante an den pfad anfügen (versuchen, sie an jedes bisherige element des pfades anzufügen (in den 4 himmelsrichtungen), falls dort schon etwas belegt ist, dann diesen neuen pfad nicht nehmen). Auf die so entstehenden Pfade wendest du gleiche Methode nochmal an, so oft, bis du die gewünschte Länge erreicht hast. Problematisch wird es nur, wenn sich Kreise im Pfad bilden, d.h. wenn die "Pfaderweiterungsfunktion" wieder am ursprünglichen Pfad in einem punkt A "anstößt", denn dann hast du diesen Pfad doppelt, da du auch von A aus, wo der Pfad einen Kreis gebildet hat, den gleichen Graphen (jetzt ists ja kein Pfad mehr
) hättest erzeugen können. Je nachdem, ob du Kreise erlauben willst, kannst du auch prüfen, ob im nächsten zug ein Kreis entstehen würde und dann diese Pfadfortsetzung nicht in deine Liste der gültigen Pfade einfügen, damit würdest du dir das Problem der doppelten Pfade sparen.Und dass es sehr viele Pfade sind, das ist nun mal so bei dieser Aufgabenstellung
nochmal edit, da ich nicht weiß, ob das jetzt so klar rausgekommen ist:
Der Trick ist, einen Algorithmus zu schrieben, der zu einem beliebigen Pfad alle Pfade zurückgibt, die entstehen, wenn man _eine_ zusätzliche Kante hinzufügt. Diesen Algorithmus kann man dann _nochmal_ auf die entstehenden Pfade (deren Länge ja nun um 1 größer ist) anwenden, und man erhält alle Pfade, die eine um 2 größere Länge als der Ausgangspfad haben. Dies iterativ zu implementieren (für beliebige Längen) erscheint mir um eineiges schwerer und ein effizienter Lösungsansatz dazu fällt mir auf die schnelle auch nicht ein.
-
Ich habe auch hier das Problem mit Rekursion gelöst. Und bin jetzt endlich fertig. Hier also das vollständige Programm: http://pastie.org/396767 Der einzige Schönheitsfehler ist, daß es die Lösung 2mal findet. Aber ich hab heut keine Lust mehr nach dem Fehler zu suchen.
Es löst übrigens dieses Problem: 4 Leute sollen sich ein Land teilen. Jeder soll auf seinem Stück Land ein Haus und ein Brunnen haben. Außerdem sollen die Länder jeweils kongruent sein, also die gleiche Form haben. Die Brunnen und Häuser sind folgendermaßen verteilt:
Brun = Brunnen +------+------+------+------+------+------+ | Leer | Leer | Haus | Haus | Leer | Leer | +------+------+------+------+------+------+ | Leer | Leer | Leer | Leer | Brun | Leer | +------+------+------+------+------+------+ | Leer | Leer | Haus | Leer | Brun | Leer | +------+------+------+------+------+------+ | Leer | Leer | Leer | Leer | Leer | Leer | +------+------+------+------+------+------+ | Leer | Leer | Leer | Leer | Leer | Leer | +------+------+------+------+------+------+ | Leer | Brun | Leer | Leer | Brun | Haus | +------+------+------+------+------+------+Danke!
-
Was meinst du mit "gleicher Form"? Wenn du meinst mit Rotation oder Translation ineinander überführbar, dann könnte es eventuell schneller gehen das Land aufzuteilen als Grundstück für Grundstück zu berechnen und zu kucken ob es passt.
Gibt es einen Fall in dem die 4 Felder in der Mitte nicht 4 verschiedenen Leuten gehören? Wenn nicht dann gibt es glaube ich weniger als 128 verschiedenen Möglichkeiten das Land aufzuteilen.
-
Ben04 schrieb:
Was meinst du mit "gleicher Form"? Wenn du meinst mit Rotation oder Translation ineinander überführbar, dann könnte es eventuell schneller gehen das Land aufzuteilen als Grundstück für Grundstück zu berechnen und zu kucken ob es passt.
Ja, so ist das gemeint gewesen, also durch Rotation. Jeder soll die gleiche Anzahl Stücke Land haben und sie sollen jeweils deckunsgleich sein. Das warn Rätsel aus sonem Nintendo DS Spiel, das ein Kollege mit bei der Arbeit hatte. Da muß man ständig sone Rätsel lösen. Und es hat ein wenig gedauert, daß per Hand zu lösen, da die Form die das Problem löst ein bißchen doof ist.
Gibt es einen Fall in dem die 4 Felder in der Mitte nicht 4 verschiedenen Leuten gehören? Wenn nicht dann gibt es glaube ich weniger als 128 verschiedenen Möglichkeiten das Land aufzuteilen.
Die Felder in der Mitte gehören den 4 verschiedenen Besitzern, da wenn man ein Mittelstück nimmt und 90/180/270 Grad dreht es natürlich jeweils einem anderen gehören muß um deckungsgleiche Stücken Land zu erhalten. 128 könnte sogar hinkommen. Ich hatte mir als Debugausgabe im Programm das mal anzeigen lassen. Das war ungefähr so in dem Dreh.
-
Wäre es dann nicht schneller alle etwa 128 Möglichkeiten irgendwo abzuspeichern und die dann durchzutesten als jedes Mal haufenweise Pfade mit Seitenschwänze zu generieren? Ob eine gegebene Landverteilung mit einer Brunnen/Hausverteilung zusammenpasst, kann man ja sehr einfach und schnell überprüfen.
-
Ben04 schrieb:
Wäre es dann nicht schneller alle etwa 128 Möglichkeiten irgendwo abzuspeichern und die dann durchzutesten als jedes Mal haufenweise Pfade mit Seitenschwänze zu generieren?
Wenn die Funktion sehr oft hintereinander ausgeführt werden soll, hast du Recht, dann wäre es besser die Wege zu hinterlegen, wie Aufstellungen bei nem Schachcomputer. Sie soll aber jediglich die Lösung für das Problem finden und damit wollte ich mich nicht belasten da noch ein Lookup für "Stellungen" einzubauen.
Aber vielleicht ist deine Idee noch besser als meine Anfang, du müsstest das weiter ausführen, was du genau meinst.
Im Moment macht das Programm folgendes:
- finde alle Pfade die maximal 9 Einheiten lang sind
- ist der Pfad 9 Einheiten lang dann teste ihn gegen die Ausschlußkriterien (überlappt mit sich selbst, wenn er gedreht wird; nicht jeder hat ein Haus und ein Brunnen auf seinen Feldern)
- ist der Pfad kürzer als 9 Einheiten, dann füge die restlichen Einheiten irgendwo an und teste gegen das Ausschlußkriterium
Die 9 kommt natürlich daher, daß das Spielfeld (36 Felder) gerecht auf 4 Leute aufgeteilt werden soll.
Die Lösung bei obiger Konfiguration ist eindeutig und verzweigt.
-
Ich teile das Feld in 4 Quadranten (also das Brett einmal vertikal und horizontal in der Mitte durchschneiden). Jeder Quadrant besteht aus 9 Felder wovon jeweils das Feld in der Mitte bekannt ist. In jedem Quadrant kann es bis zu 3 verschiedene Besitzer geben. Kennt man einen Quadrant so kann man Rotationen und Umbenennungen die anderen 3 bestimmen. Für einen Quadrant gibt es also 3^8 = 6561 Möglichkeiten die man sehr einfach auflisten kann. Man iteriert nun drüber und wählt eine aus welche die Brunnen/Hausbedingung erfüllt und wo die Grundstücke zusammenhängend sind. Es reicht zu testen ob ein Grundstück zusammenhängend ist. Dies geht mit einem kleinen rekursiven Floodfillalgo sehr einfach.
Das ist meiner Meinung nach einfacher zu implementieren (und schneller) als das was du jetzt hast.
-
Ben04 schrieb:
Gibt es einen Fall in dem die 4 Felder in der Mitte nicht 4 verschiedenen Leuten gehören?
Ja.
A A A C C C A A B D C C A B B D D C B B B D D DOder soll das ganze wirklich Rotationssymmetrisch sein und nicht nur kongruent?
-
Das ist aber kein 6 mal 6 Feld.
-
Es soll roationssymmetrisch sein. Dein Vorschlag mit dem permutieren innerhalb eines Quadranten ist wirklich sehr eingänglich. Ich hab das gerad mal zusammengecodet und der Source ist mit deiner Methode halb so lang und leichter verständlich, als die Wegfinde-Routine. Danke für die Idee. Da hab ich von Anfang an zu kompliziert gedacht
Hier der Code falls du sehen willst, was ich aus deiner Idee gemacht habe http://pastie.org/397252 (schlecht kommentiert usw. ... auf die schnelle entstanden)
-
Ben04 schrieb:
Das ist aber kein 6 mal 6 Feld.
Naja, die oberste und unterste Zeile kriegst Du sicher raus.
