Biorąc pod uwagę zestaw stosów NXP, gdzie N jest liczbą stosów, a P jest pojemnością stosów, jak mogę obliczyć minimalną liczbę zamian potrzebnych do przeniesienia z pewnego węzła w lokalizacji A do jakiejkolwiek arbitralnej lokalizacji B? Projektuję grę, a ostatecznym celem jest uporządkowanie wszystkich stosów, aby wszystkie miały ten sam kolor.
# 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']
]
Jeśli chcę wstawić „B” w stacks[1][1]
takim, że stacks[1] = ["-", "B", "Y", "Y"]
. Jak mogę określić minimalną liczbę ruchów wymaganych do tego?
Patrzyłem na wiele podejść, próbowałem algorytmów genetycznych, które generują wszystkie możliwe ruchy ze stanu, oceniają je, a następnie kontynuują najlepsze ścieżki punktacji, próbowałem również uruchomić algorytm Djikstry w celu znalezienia ścieżki problemu . Wydaje się to frustrująco proste, ale nie mogę znaleźć sposobu, aby uruchomić go w innym miejscu niż wykładniczy czas. Czy brakuje mi algorytmu, który ma tu zastosowanie?
Edytować
Napisałem tę funkcję, aby obliczyć minimalną wymaganą liczbę ruchów: stosy: Lista postaci reprezentujących elementy na stosie, stosy [0] [0] to początek stosu [0] stack_ind: Indeks stos, do którego element zostanie dodany do need_piece: element, który powinien zostać dodany do stosu need_index: indeks, w którym element powinien zostać umieszczony
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")
Edycja: Testuj przypadki na stosach:
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
Rzeczywista implementacja kodu nie jest częścią trudną, decyduje o tym, jak zaimplementować algorytm, który rozwiązuje problem, z którym walczę.
Zgodnie @ życzenie YonIif za Utworzyłem istotę tego problemu.
Po uruchomieniu generuje losową tablicę stosów i wybiera losowy element, który należy włożyć do losowego stosu w losowej lokalizacji.
Po uruchomieniu drukuje na konsoli coś w tym formacie.
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']
Aktualizacja statusu
Jestem bardzo zdeterminowany, aby jakoś rozwiązać ten problem .
Należy pamiętać, że istnieją sposoby na zminimalizowanie liczby przypadków, takich jak wspomniane w komentarzach @Hans Olsson. Moje najnowsze podejście do tego problemu polegało na opracowaniu zestawu reguł podobnych do tych wymienionych i zastosowaniu ich w algorytmie generacyjnym.
Zasady takie jak:
Nigdy nie cofaj ruchu. Przejdź od 1-> 0, a następnie 0-> 1 (nie ma sensu)
Nigdy nie ruszaj pionka dwa razy z rzędu. Nigdy nie ruszaj się od 0 -> 1, a następnie 1 -> 3
Biorąc pod uwagę ruch ze stosów [X] na stosy [Y], następnie pewną liczbę ruchów, a następnie ruch ze stosów [Y] na stosy [Z], jeśli stosy [Z] są w tym samym stanie, co w momencie ruchu ze stosów [X] na stosy [Y], ruch można było wyeliminować, przenosząc się ze stosów [X] bezpośrednio na stosy [Z]
Obecnie podchodzę do tego problemu, próbując stworzyć wystarczającą liczbę reguł, aby zminimalizować liczbę „prawidłowych” ruchów, na tyle, aby można było obliczyć odpowiedź za pomocą algorytmu generacyjnego. Jeśli ktoś wymyśli dodatkowe zasady, chciałbym usłyszeć je w komentarzach.
Aktualizacja
Dzięki odpowiedzi @RootTwo dokonałem przełomu, który tutaj opiszę.
Na przełom
Zdefiniuj wysokość bramki jako głębokość, na którą cel musi zostać umieszczony na stosie docelowym.
Ilekroć jakiś element bramki jest umieszczony na indeksie <= stack_height - wysokość bramki, zawsze będzie najkrótsza droga do zwycięstwa za pomocą metody clear_path ().
Let S represent some solid Piece.
TO ZNACZY
Stacks = [ [R, R, G], [G, G, R], [-, -, -] ]
Goal = Stacks[0][2] = R
Goal Height = 2.
Stack Height - Goal Height = 0
Biorąc pod uwagę taki stos stack[0] = R
, gra jest wygrana.
GOAL
[ [ (S | -), (S | -), (S | -) ], [R, S, S], [(S | - ), (S | -), (S | -)] ]
Ponieważ wiadomo, że są zawsze dostępne co najmniej puste przestrzenie stosu-wysokości, najgorszym możliwym przypadkiem byłoby:
[ [ S, S, !Goal ], [R, S, S], [-, -, -]
Ponieważ wiemy, że bramka nie może znajdować się w miejscu docelowym bramki lub gra zostanie wygrana. W takim przypadku minimalna wymagana liczba ruchów to ruchy:
(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
Biorąc pod uwagę taki stos stack[1] = R
, gra jest wygrana.
GOAL
[ [ (S | -), (S | -), S], [ (S | -), R, S], [(S | -), (S | -), (S | -)]
Wiemy, że dostępne są co najmniej 3 puste miejsca, więc najgorszym możliwym przypadkiem byłoby:
[ [ S, !Goal, S], [S, R, S], [ -, -, - ]
W takim przypadku minimalna liczba ruchów to ruchy:
(1, 2), (0, 2), (0, 2), (1, 0)
Dotyczy to wszystkich przypadków.
Zatem problem został zredukowany do problemu znalezienia minimalnej liczby ruchów wymaganych do umieszczenia bramki na wysokości lub powyżej na wysokości bramki.
To dzieli problem na szereg podproblemów:
Kiedy stos docelowy ma dostępny element! = Element bramkowy, określanie, czy istnieje poprawne miejsce dla tego elementu, czy też kawałek powinien pozostać tam, dopóki inny kawałek zostanie wymieniony.
Kiedy stos docelowy ma dostępny element == element bramkowy, określanie, czy można go usunąć i umieścić na wymaganej wysokości bramki, czy też element powinien pozostać, podczas gdy inny zostanie zamieniony.
Gdy powyższe dwa przypadki wymagają zamiany innego elementu, określanie, które elementy należy zamienić w celu zwiększenia, aby umożliwić osiągnięcie celu przez bramkę.
Na stosie docelowym zawsze należy najpierw przeanalizować przypadki.
TO ZNACZY
stacks = [ [-, R, G], [-, R, G], [-, R, G] ]
Goal = stacks[0][1] = G
Najpierw sprawdzenie stosu bramek prowadzi do:
(0, 1), (0, 2), (1, 0), (2, 0) = 4 Moves
Ignorowanie stosu bramek:
(1, 0), (1, 2), (0, 1), (0, 1), (2, 0) = 5 Moves