Wie kann ich bei einem Satz von NXP-Stapeln, wobei N die Anzahl der Stapel und P die Stapelkapazität ist, die minimale Anzahl von Swaps berechnen, die erforderlich sind, um von einem Knoten an Position A zu einem beliebigen Ort B zu gelangen? Ich entwerfe ein Spiel und das Endziel ist es, alle Stapel so zu sortieren, dass sie alle die gleiche Farbe haben.
# Let "-" represent blank spaces, and assume the stacks are
stacks = [
['R', 'R', 'R', 'R'],
['Y', 'Y', 'Y', 'Y'],
['G', 'G', 'G', 'G'],
['-', '-', '-', 'B'],
['-', 'B', 'B', 'B']
]
Wenn ich ein "B" stacks[1][1]
so einfügen möchte, dass stacks[1] = ["-", "B", "Y", "Y"]
. Wie kann ich die Mindestanzahl von Zügen bestimmen, die dazu erforderlich sind?
Ich habe mehrere Ansätze untersucht, ich habe genetische Algorithmen ausprobiert, die alle möglichen Bewegungen aus einem Zustand generieren, sie bewerten und dann die besten Bewertungspfade verfolgen. Ich habe auch versucht, den Djikstra-Algorithmus zur Pfadfindung für das Problem auszuführen . Es scheint frustrierend einfach zu sein, aber ich kann keinen Weg finden, es in etwas anderem als exponentieller Zeit zum Laufen zu bringen. Fehlt mir ein Algorithmus, der hier anwendbar ist?
Bearbeiten
Ich habe diese Funktion geschrieben, um die Mindestanzahl der erforderlichen Züge zu berechnen: Stapel: Liste der Zeichen, die die Teile im Stapel darstellen, Stapel [0] [0] ist die Spitze des Stapels [0] stack_ind: Der Index des Stapel, dem das Teil hinzugefügt werden soll need_piece: Das Teil, das dem Stapel hinzugefügt werden soll braucht_index: Der Index, in dem sich das Teil befinden soll
def calculate_min_moves(stacks, stack_ind, needs_piece, needs_index):
# Minimum moves needed to empty the stack that will receive the piece so that it can hold the piece
num_removals = 0
for s in stacks[stack_ind][:needs_index+1]:
if item != "-":
num_removals += 1
min_to_unlock = 1000
unlock_from = -1
for i, stack in enumerate(stacks):
if i != stack_ind:
for k, piece in enumerate(stack):
if piece == needs_piece:
if k < min_to_unlock:
min_to_unlock = k
unlock_from = i
num_free_spaces = 0
free_space_map = {}
for i, stack in enumerate(stacks):
if i != stack_ind and i != unlock_from:
c = stack.count("-")
num_free_spaces += c
free_space_map[i] = c
if num_removals + min_to_unlock <= num_free_spaces:
print("No shuffling needed, there's enough free space to move all the extra nodes out of the way")
else:
# HERE
print("case 2, things need shuffled")
Bearbeiten: Testfälle auf Stapeln:
stacks = [
['R', 'R', 'R', 'R'],
['Y', 'Y', 'Y', 'Y'],
['G', 'G', 'G', 'G'],
['-', '-', '-', 'B'],
['-', 'B', 'B', 'B']
]
Case 1: stacks[4][1] should be 'G'
Move 'B' from stacks[4][1] to stacks[3][2]
Move 'G' from stacks[2][0] to stacks[4][1]
num_removals = 0 # 'G' is directly accessible as the top of stack 2
min_to_unlock = 1 # stack 4 has 1 piece that needs removed
free_spaces = 3 # stack 3 has free spaces and no pieces need moved to or from it
moves = [[4, 3], [2, 4]]
min_moves = 2
# This is easy to calculate
Case 2: stacks[0][3] should be 'B'
Move 'B' from stacks[3][3] to stack[4][0]
Move 'R' from stacks[0][0] to stacks[3][3]
Move 'R' from stacks[0][1] to stacks[3][2]
Move 'R' from stacks[0][2] to stacks[3][1]
Move 'R' from stacks[0][3] to stacks[3][0]
Move 'B' from stacks[4][0] to stacks[0][3]
num_removals = 0 # 'B' is directly accessible
min_to_unlock = 4 # stack 0 has 4 pieces that need removed
free_spaces = 3 # If stack 3 and 4 were switched this would be 1
moves = [[3, 4], [0, 3], [0, 3], [0, 3], [0, 3], [4, 0]]
min_moves = 6
#This is hard to calculate
Die eigentliche Code-Implementierung ist nicht der Teil, der schwierig ist, sondern bestimmt, wie ein Algorithmus implementiert wird, der das Problem löst, mit dem ich zu kämpfen habe.
Gemäß der Anfrage von @ YonIif habe ich einen Kern für das Problem erstellt.
Wenn es ausgeführt wird, generiert es ein zufälliges Array der Stapel und wählt ein zufälliges Stück aus, das an einer zufälligen Stelle in einen zufälligen Stapel eingefügt werden muss.
Wenn Sie es ausführen, wird etwas von diesem Format auf die Konsole gedruckt.
All Stacks: [['-', '-', 'O', 'Y'], ['-', 'P', 'P', 'O'], ['-', 'P', 'O', 'Y'], ['Y', 'Y', 'O', 'P']]
Stack 0 is currently ['-', '-', 'O', 'Y']
Stack 0 should be ['-', '-', '-', 'P']
Status-Update
Ich bin sehr entschlossen, dieses Problem irgendwie zu lösen .
Beachten Sie, dass es Möglichkeiten gibt, die Anzahl der Fälle zu minimieren, z. B. die in den Kommentaren erwähnten Fälle von @Hans Olsson. Mein jüngster Ansatz für dieses Problem bestand darin, eine Reihe von Regeln zu entwickeln, die den genannten ähnlich sind, und sie in einem Generationsalgorithmus anzuwenden.
Regeln wie:
Mach niemals einen Zug rückgängig. Gehen Sie von 1-> 0 dann 0-> 1 (macht keinen Sinn)
Bewegen Sie niemals ein Stück zweimal hintereinander. Bewegen Sie sich niemals von 0 -> 1, dann von 1 -> 3
Bei einigen Bewegungen von Stapeln [X] zu Stapeln [Y], dann zu einer bestimmten Anzahl von Bewegungen, dann zu einer Bewegung von Stapeln [Y] zu Stapeln [Z], wenn sich die Stapel [Z] im selben Zustand befinden wie zu dem Zeitpunkt, als sie verschoben wurden Von den Stapeln [X] zu den Stapeln [Y] konnte eine Bewegung eliminiert werden, indem von den Stapeln [X] direkt zu den Stapeln [Z] gewechselt wurde.
Derzeit gehe ich dieses Problem mit dem Versuch an, genügend Regeln zu erstellen, um die Anzahl der "gültigen" Züge so gering wie möglich zu halten, damit eine Antwort mithilfe eines Generationsalgorithmus berechnet werden kann. Wenn sich jemand zusätzliche Regeln vorstellen kann, wäre ich daran interessiert, sie in den Kommentaren zu hören.
Aktualisieren
Dank der Antwort von @RootTwo hatte ich einen kleinen Durchbruch, den ich hier skizzieren werde.
Auf den Durchbruch
Definieren Sie die Zielhöhe als die Tiefe, in der das Zielstück im Zielstapel platziert werden muss.
Immer wenn ein Torstück auf Index <= Stack_Höhe - Zielhöhe platziert wird, gibt es über die Methode clear_path () einen kürzesten Weg zum Sieg.
Let S represent some solid Piece.
IE
Stacks = [ [R, R, G], [G, G, R], [-, -, -] ]
Goal = Stacks[0][2] = R
Goal Height = 2.
Stack Height - Goal Height = 0
Bei einem solchen Stapel stack[0] = R
ist das Spiel gewonnen.
GOAL
[ [ (S | -), (S | -), (S | -) ], [R, S, S], [(S | - ), (S | -), (S | -)] ]
Da bekannt ist, dass immer mindestens Stack_Hight-Leerzeichen verfügbar sind, wäre der schlimmste Fall:
[ [ S, S, !Goal ], [R, S, S], [-, -, -]
Da wir wissen, dass das Torstück nicht am Zielort sein kann oder das Spiel gewonnen ist. In diesem Fall wären mindestens die Züge erforderlich:
(0, 2), (0, 2), (0, 2), (1, 0)
Stacks = [ [R, G, G], [-, R, R], [-, -, G] ]
Goal = Stack[0][1] = R
Stack Height - Goal Height = 1
Bei einem solchen Stapel stack[1] = R
ist das Spiel gewonnen.
GOAL
[ [ (S | -), (S | -), S], [ (S | -), R, S], [(S | -), (S | -), (S | -)]
Wir wissen, dass mindestens 3 Leerzeichen verfügbar sind. Der schlimmste Fall wäre also:
[ [ S, !Goal, S], [S, R, S], [ -, -, - ]
In diesem Fall wäre die minimale Anzahl von Zügen die Züge:
(1, 2), (0, 2), (0, 2), (1, 0)
Dies gilt für alle Fälle.
Somit wurde das Problem auf das Problem reduziert, die minimale Anzahl von Zügen zu finden, die erforderlich sind, um das Torstück auf oder über der Zielhöhe zu platzieren.
Dies teilt das Problem in eine Reihe von Unterproblemen auf:
Wenn der Zielstapel sein zugängliches Stück hat! = Zielstück, Bestimmen, ob es einen gültigen Ort für dieses Stück gibt oder ob das Stück dort bleiben soll, während ein anderes Stück getauscht wird.
Wenn der Zielstapel sein zugängliches Stück == Zielstück hat, bestimmen Sie, ob es entfernt und auf der erforderlichen Zielhöhe platziert werden kann oder ob das Stück bleiben soll, während ein anderes getauscht wird.
Wenn in den beiden oben genannten Fällen ein anderes Teil ausgetauscht werden muss, muss festgelegt werden, welche Teile ausgetauscht werden müssen, um die Zielhöhe zu erreichen.
Die Fälle des Zielstapels sollten immer zuerst ausgewertet werden.
IE
stacks = [ [-, R, G], [-, R, G], [-, R, G] ]
Goal = stacks[0][1] = G
Das Überprüfen des Zielstapels führt zuerst zu:
(0, 1), (0, 2), (1, 0), (2, 0) = 4 Moves
Ignorieren des Zielstapels:
(1, 0), (1, 2), (0, 1), (0, 1), (2, 0) = 5 Moves
Antworten:
Ich habe mir zwei Optionen ausgedacht, aber keine von ihnen ist in der Lage, Fall 2 rechtzeitig zu lösen. Die erste Option verwendet A * mit einem Zeichenfolgenabstandsmaß als h (n), die zweite Option ist IDA *. Ich habe viele Saitenähnlichkeitsmaße getestet und bei meinem Ansatz Smith-Waterman verwendet. Ich habe Ihre Notation geändert, um das Problem schneller zu behandeln. Ich habe am Ende jeder Ziffer Zahlen hinzugefügt, um zu überprüfen, ob ein Stück zweimal bewegt wurde.
Hier sind die Fälle, an denen ich getestet habe:
Hier ist der A * -Code:
Hier ist der IDA * Code:
Verwendungszweck:
quelle
In den Kommentaren sagten Sie, es gibt N Stapel mit der Kapazität P und es gibt immer P leere Räume. Wenn dies der Fall ist, scheint dieser Algorithmus in der
else
Klausel in Ihrem Code zu funktionieren (dh wannnum_removals + min_to_unlock > num_free_spaces
):quelle
Obwohl ich nicht die Zeit gefunden habe, dies mathematisch zu beweisen, habe ich mich trotzdem entschlossen, dies zu posten. ich hoffe es hilft. Der Ansatz besteht darin, einen Parameter p zu definieren, der mit guten Zügen abnimmt und genau nach Erreichen des Spiels Null erreicht. Berücksichtigt im Programm nur gute oder neutrale Züge (die p unverändert lassen) und vergisst schlechte Züge (die p erhöhen).
Also, was ist p? Definieren Sie für jede Spalte p als die Anzahl der Blöcke, die noch entfernt werden müssen, bevor alle Farben in dieser Spalte die gewünschte Farbe haben. Nehmen wir also an, wir möchten, dass die roten Blöcke in der Spalte ganz links landen (darauf komme ich später zurück), und nehmen wir an, dass sich unten ein roter Block befindet, dann ein gelber darüber und ein weiterer Block darüber das und dann ein leerer Raum. Dann ist p = 2 für diese Spalte (zwei zu entfernende Blöcke, bevor alle rot sind). Berechnen Sie p für alle Spalten. Für die Spalte, die leer bleiben soll, entspricht p der Anzahl der darin enthaltenen Blöcke (alle sollten gehen). P für den aktuellen Zustand ist die Summe aller ps für alle Spalten.
Wenn p = 0 ist, haben alle Spalten die gleiche Farbe und eine Spalte ist leer, sodass das Spiel beendet ist.
Durch die Auswahl von Bewegungen, die p verringern (oder zumindest nicht erhöhen), bewegen wir uns in die richtige Richtung. Dies ist meiner Meinung nach der entscheidende Unterschied zu Algorithmen mit kürzesten Pfaden: Dijkstra hatte keine Ahnung, ob er sich mit jedem in die richtige Richtung bewegt Scheitelpunkt, den er untersuchte.
Wie bestimmen wir also, wo jede Farbe landen soll? Grundsätzlich durch Bestimmung von p für jede Möglichkeit. Beginnen Sie also zB mit rot / gelb / grün / leer, berechnen Sie p, gehen Sie dann zu rot / gelb / leer / grün, berechnen Sie p usw. Nehmen Sie die Startposition mit dem niedrigsten p ein. Das dauert n! Berechnungen. Für n = 8 ist dies 40320, was machbar ist. Die schlechte Nachricht ist, dass Sie alle Startpositionen mit dem gleichen niedrigsten p untersuchen müssen. Die gute Nachricht ist, dass Sie den Rest vergessen können.
Hier gibt es zwei mathematische Unsicherheiten. Erstens: Ist es möglich, dass es einen kürzeren Weg gibt, der einen schlechten Zug verwendet? Scheint unwahrscheinlich, ich habe kein Gegenbeispiel gefunden, aber ich habe auch keinen Beweis gefunden. Zweitens: Ist es möglich, dass beim Starten mit einer nicht optimalen Startposition (dh nicht dem niedrigsten p) ein kürzerer Weg als bei allen optimalen Startpositionen vorhanden ist? Nochmals: kein Gegenbeispiel, aber auch kein Beweis.
Einige Implementierungsvorschläge. Das Verfolgen von p während der Ausführung für jede Spalte ist nicht schwierig, sollte aber natürlich durchgeführt werden. Ein weiterer Parameter, der für jede Spalte beibehalten werden sollte, ist die Anzahl der offenen Stellen. Wenn 0, können diese Spalten momentan keine Blöcke akzeptieren und können daher aus der Schleife herausgelassen werden. Wenn p = 0 für eine Spalte ist, ist sie nicht für einen Pop geeignet. Prüfen Sie für jeden möglichen Pop, ob es einen guten Zug gibt, dh einen, der das Gesamt-p verringert. Wenn es mehrere gibt, überprüfen Sie alle. Wenn es keine gibt, berücksichtigen Sie alle neutralen Bewegungen.
All dies sollte Ihre Rechenzeit erheblich verkürzen.
quelle