Ein Puzzle mit Suchalgorithmen lösen
Ich bin vor ein paar Tagen auf ein Rätsel gestoßen. Es ist leicht von Hand lösbar. Aber ich habe versucht, einen Algorithmus zu entwickeln, um es zu lösen. Aber ich weiß nicht, wie ich vorgehen soll.
Hier können Sie sehen, dass ich alle Paare von farbigen Punkten verbinden muss. Zum Beispiel muss ich den gelben Punkt mit einem anderen gelben Punkt verbinden, grün mit anderen grünen, blau mit blau und so weiter.
Hier ist ein Beispiel, wie es gelöst werden sollte. wenn die Beschreibung nicht klar war.
So können Sie sehen, dass ich gelben Punkt mit einem anderen gelben Punkt verbunden habe. Und blau mit einem anderen Blau. Aber das verursacht ein Problem. Ich habe den Weg der Aqua-Farbe blockiert, wie Sie sehen können. Ich hoffe, du hast eine Idee.
Also ich möchte es lösen. Brute Force-Ansatz würde funktionieren, aber es wird eine lange Zeit dauern, und ich bin nicht daran interessiert. Ich habe versucht, Breathth First Search, Depth First Search und Dijkstra-Algorithmus zu implementieren. Aber ich denke, dass sie in diesem Fall nicht gut sein werden. Korrigiere mich bitte, wenn ich falsch liege. A * Suche funktioniert vielleicht, aber was ist die Heuristik?
Kann mir jemand eine Intuition geben, wie ich das Problem lösen kann?
1 Antwort
Chromosom:
- 9x9 2d Array von Inten (Genen)
- Ihre 18 einzigartigen farbigen Punkte werden statisch als 512 | 1, 512 | 2, 512 | 4, 512 | 8, 512 | 16, 512 | 32, 512 | 64, 512 | 128, 512 | 256 gesetzt 9 einzigartige Farben; 512 (2 ^ 9) wird die Flagge sein, die sie als statisch / unveränderbare Gene bezeichnet.
- Farbige Verbindungsquadrate haben 2 ^ 0-2 ^ 8 Werte, diese Gene können sich ändern und zusammengesetzt sein, ein Wert von 3 (011b) würde bedeuten, dass 2 Farben (1 und 2) das gleiche Quadrat teilen.
Fitness-Funktion von der Spitze meines Kopfes
- Räume mit 1 einzigartigen Farben sind +8, 2 Farben +6, 3 Farben +4, 4 Farben +2, 5 Farben +0, 6 Farben -2, 7 Farben -4, 8 Farben -6, alle 9 Farben -8
- Verbundene Räume (links, rechts, oben, unten) mit einem passenden farbigen statischen Raum sind +9
- Leerzeichen, die mit einem übereinstimmenden Farbraum in 1 Richtung +4, 2 Richtungen +3, 3 Richtungen +2, 4 Richtungen +1 verbunden sind
Mutation
- Logisches XOR ein zufälliges Farbbit (1 & lt; Floor (Random () * 9)) mit einem zufälligen nicht-statischen Gen
Cross-Over / Zucht Von der Spitze meines Kopfes
- Kopieren Sie Ihre 2 Kandidaten-Chromosomen
- Löschen Sie Gene innerhalb der Kopien, die 5 oder mehr überlappende Farben enthalten
- Logische ODER die beiden Chromosomen zusammen, um Ihr Ergebnis zu erhalten