[gelöst]Landaufteilung mit Graphen?
-
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.
