Jak znaleźć minimalną liczbę ruchów, aby przenieść przedmiot na pozycję na stosie?

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:

1. 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.

2. 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.

3. 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

Wymyśliłem dwie opcje, ale żadna z nich nie jest w stanie rozwiązać przypadku 2 w odpowiednim czasie. Pierwszą opcją jest użycie A * z miarą odległości łańcucha jako h (n), drugą opcją jest IDA *. Przetestowałem wiele miar podobieństwa strun, w swoim podejściu zastosowałem smith-waterman. Zmieniłem twój zapis, aby szybciej rozwiązać problem. Dodałem liczby na końcu każdej cyfry, aby sprawdzić, czy element został przesunięty dwukrotnie.

Oto przypadki, w których testowałem:

start = [
 ['R1', 'R2', 'R3', 'R4'], 
 ['Y1', 'Y2', 'Y3', 'Y4'], 
 ['G1', 'G2', 'G3', 'G4'], 
 ['B1'], 
 ['B2', 'B3', 'B4']
]

case_easy = [
 ['R', 'R', 'R', 'R'], 
 ['Y', 'Y', 'Y', 'Y'], 
 ['G', 'G', 'G'], 
 ['B', 'B'], 
 ['B', 'B', 'G']
]


case_medium = [
 ['R', 'R', 'R', 'R'], 
 ['Y', 'Y', 'Y', 'B'], 
 ['G', 'G', 'G'], 
 ['B'],
 ['B', 'B', 'G', 'Y']
]

case_medium2 = [
 ['R', 'R', 'R' ], 
 ['Y', 'Y', 'Y', 'B'], 
 ['G', 'G' ], 
 ['B', 'R', 'G'],
 ['B', 'B', 'G', 'Y']
]

case_hard = [
 ['B'], 
 ['Y', 'Y', 'Y', 'Y'], 
 ['G', 'G', 'G', 'G'], 
 ['R','R','R', 'R'], 
 ['B','B', 'B']
]

Oto kod A *:

from copy import deepcopy
from heapq import *
import time, sys
import textdistance
import os

def a_star(b, goal, h):
    print("A*")
    start_time = time.time()
    heap = [(-1, b)]
    bib = {}
    bib[b.stringify()] = b

    while len(heap) > 0:
        node = heappop(heap)[1]
        if node == goal:
            print("Number of explored states: {}".format(len(bib)))
            elapsed_time = time.time() - start_time
            print("Execution time {}".format(elapsed_time))
            return rebuild_path(node)

        valid_moves = node.get_valid_moves()
        children = node.get_children(valid_moves)
        for m in children:
          key = m.stringify()
          if key not in bib.keys():
            h_n = h(key, goal.stringify())
            heappush(heap, (m.g + h_n, m)) 
            bib[key] = m

    elapsed_time = time.time() - start_time
    print("Execution time {}".format(elapsed_time))
    print('No Solution')

Oto kod IDA *:

#shows the moves done to solve the puzzle
def rebuild_path(state):
    path = []
    while state.parent != None:
        path.insert(0, state)
        state = state.parent
    path.insert(0, state)
    print("Number of steps to solve: {}".format(len(path) - 1))
    print('Solution')

def ida_star(root, goal, h):
    print("IDA*")
    start_time = time.time()
    bound = h(root.stringify(), goal.stringify())
    path = [root]
    solved = False
    while not solved:
        t = search(path, 0, bound, goal, h)
        if type(t) == Board:
            solved = True
            elapsed_time = time.time() - start_time
            print("Execution time {}".format(elapsed_time))
            rebuild_path(t)
            return t
        bound = t

def search(path, g, bound, goal, h):

    node = path[-1]
    time.sleep(0.005)
    f = g + h(node.stringify(), goal.stringify())

    if f > bound: return f
    if node == goal:
        return node

    min_cost = float('inf')
    heap = []
    valid_moves = node.get_valid_moves()
    children = node.get_children(valid_moves)
    for m in children:
      if m not in path:
        heappush(heap, (m.g + h(m.stringify(), goal.stringify()), m)) 

    while len(heap) > 0:
        path.append(heappop(heap)[1])
        t = search(path, g + 1, bound, goal, h)
        if type(t) == Board: return t
        elif t < min_cost: min_cost = t
        path.pop()
    return min_cost

class Board:
  def __init__(self, board, parent=None, g=0, last_moved_piece=''):
    self.board = board
    self.capacity = len(board[0])
    self.g = g
    self.parent = parent
    self.piece = last_moved_piece

  def __lt__(self, b):
    return self.g < b.g

  def __call__(self):
    return self.stringify()

  def __eq__(self, b):
    if self is None or b is None: return False
    return self.stringify() == b.stringify()

  def __repr__(self):
    return '\n'.join([' '.join([j[0] for j in i]) for i in self.board])+'\n\n'

  def stringify(self):
    b=''
    for i in self.board:
      a = ''.join([j[0] for j in i])
      b += a + '-' * (self.capacity-len(a))

    return b

  def get_valid_moves(self):
    pos = []
    for i in range(len(self.board)):
      if len(self.board[i]) < self.capacity:
        pos.append(i)
    return pos

  def get_children(self, moves):
    children = []
    for i in range(len(self.board)):
      for j in moves:
        if i != j and self.board[i][-1] != self.piece:
          a = deepcopy(self.board)
          piece = a[i].pop()
          a[j].append(piece)
          children.append(Board(a, self, self.g+1, piece))
    return children

Stosowanie:

initial = Board(start)
final1 = Board(case_easy)
final2 = Board(case_medium)
final2a = Board(case_medium2)
final3 = Board(case_hard)

x = textdistance.gotoh.distance

a_star(initial, final1, x)
a_star(initial, final2, x)
a_star(initial, final2a, x)

ida_star(initial, final1, x)
ida_star(initial, final2, x)
ida_star(initial, final2a, x)

W komentarzach powiedziałeś, że jest N stosów o pojemności P i zawsze jest P pustych miejsc. W takim przypadku wydaje się, że ten algorytm będzie działał w elseklauzuli w kodzie (tj. Kiedy num_removals + min_to_unlock > num_free_spaces):

1. Znajdź żądany kawałek, który znajduje się najbliżej wierzchu stosu.
2. Przenieś wszystkie elementy powyżej pożądanego elementu w taki sposób, aby znajdował się jeden stos (nie stos docelowy) z pustą przestrzenią na górze. W razie potrzeby przenieś pionki ze stosu docelowego lub innego stosu. Jeśli jedyną otwartą przestrzenią jest góra stosu docelowego, przenieś tam kawałek, aby otworzyć górę innego stosu. Jest to zawsze możliwe, ponieważ istnieje P otwartych przestrzeni i co najwyżej P-1 pionków, które można przesunąć z góry powyżej pożądanego kawałka.
3. Przenieś żądany element w puste miejsce na szczycie stosu.
4. Przenieś elementy ze stosu docelowego, aż miejsce docelowe będzie otwarte.
5. Przenieś żądany element do miejsca docelowego.

Chociaż nie znalazłem czasu, aby to udowodnić matematycznie, i tak postanowiłem to opublikować; mam nadzieję, że to pomoże. Podejście polega na zdefiniowaniu parametru p, który zmniejsza się przy dobrych ruchach i osiąga zero dokładnie po zakończeniu gry. W programie uwzględnia tylko dobre ruchy lub ruchy neutralne (które pozostawiają p bez zmian) i zapominają o złych ruchach (które zwiększają p).

Co to jest p? Dla każdej kolumny zdefiniuj p jako liczbę bloków, które należy jeszcze usunąć, zanim wszystkie kolory w tej kolumnie będą miały żądany kolor. Przypuśćmy, że chcemy, aby czerwone bloki znalazły się w lewej kolumnie (wrócę do tego później) i załóżmy, że jest jeden czerwony blok na dole, a następnie żółty na nim, jeszcze jeden blok na górze to, a potem pusta przestrzeń. Następnie p = 2 dla tej kolumny (dwa bloki do usunięcia, zanim wszystkie będą czerwone). Oblicz p dla wszystkich kolumn. Dla kolumny, która powinna skończyć się pusta, p jest równe liczbie znajdujących się w niej bloków (wszystkie powinny pójść). P dla bieżącego stanu jest sumą wszystkich p dla wszystkich kolumn.

Gdy p = 0, wszystkie kolumny mają ten sam kolor, a jedna kolumna jest pusta, więc gra się zakończyła.

Wybierając ruchy, które zmniejszają p (a przynajmniej nie zwiększają p), idziemy we właściwym kierunku, to moim zdaniem zasadnicza różnica w przypadku algorytmów najkrótszej ścieżki: Dijkstra nie miał pojęcia, czy porusza się we właściwym kierunku z każdym wierzchołek, który badał.

Jak więc ustalić, gdzie powinien kończyć się każdy kolor? Zasadniczo przez określenie p dla każdej możliwości. Tak więc np. Zacznij od czerwonego / żółtego / zielonego / pustego, oblicz p, następnie przejdź do czerwonego / żółtego / pustego / zielonego, oblicz p, itd. Zajmij pozycję początkową z najniższym p. To zajmuje n! obliczenia. Dla n = 8 jest to 40320, co jest wykonalne. Zła wiadomość jest taka, że ​​będziesz musiał zbadać wszystkie pozycje początkowe z równym najniższym p. Dobra wiadomość jest taka, że ​​możesz zapomnieć o reszcie.

Istnieją tutaj dwie niepewności matematyczne. Po pierwsze: czy jest możliwe, że istnieje krótsza ścieżka wykorzystująca zły ruch? Wydaje się mało prawdopodobne, nie znalazłem kontrprzykładu, ale nie znalazłem też dowodu. Po drugie: czy możliwe jest, że rozpoczynając od nieoptymalnej pozycji początkowej (tj. Nie najniższego p) ścieżka byłaby krótsza niż przy wszystkich optymalnych pozycjach początkowych. Ponownie: bez kontrprzykładu, ale też bez dowodu.

Kilka sugestii dotyczących implementacji. Śledzenie p podczas wykonywania dla każdej kolumny nie jest trudne, ale oczywiście należy to zrobić. Kolejnym parametrem, który należy zachować dla każdej kolumny, jest liczba wolnych miejsc. Jeśli 0, to kolumny te nie mogą chwilowo zaakceptować żadnych bloków, więc można je pominąć w pętli. Gdy p = 0 dla kolumny, nie kwalifikuje się do pop. Dla każdego możliwego trzasku sprawdź, czy jest dobry ruch, tj. Taki, który zmniejsza ogólne p. Jeśli jest ich wiele, sprawdź wszystkie. Jeśli nie ma, rozważ wszystkie ruchy neutralne.

Wszystko to powinno znacznie skrócić czas obliczeń.