[gelöst]Landaufteilung mit Graphen?

Heinzelotto

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.

NDEBUG

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!

Ben04

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.

NDEBUG

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.

Ben04

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.

NDEBUG

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.

Ben04

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.

Jester

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 D

Oder soll das ganze wirklich Rotationssymmetrisch sein und nicht nur kongruent?

Ben04

Das ist aber kein 6 mal 6 Feld.

NDEBUG

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)

Jester

Ben04 schrieb:

Das ist aber kein 6 mal 6 Feld.

Naja, die oberste und unterste Zeile kriegst Du sicher raus.