Comment trouver le nombre minimum de coups pour déplacer un objet dans une position dans une pile?

Étant donné un ensemble de piles NXP avec N étant le nombre de piles et P étant la capacité des piles, comment puis-je calculer le nombre minimum de swaps nécessaires pour passer d'un nœud de l'emplacement A à un emplacement arbitraire B? Je conçois un jeu, et l'objectif final est de trier toutes les piles afin qu'elles soient toutes de la même couleur.

# 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']
         ]

Si je veux insérer un "B" à stacks[1][1]tel point stacks[1] = ["-", "B", "Y", "Y"]. Comment puis-je déterminer le nombre minimum de déplacements requis pour ce faire?

J'ai examiné plusieurs approches, j'ai essayé des algorithmes génétiques qui génèrent tous les mouvements possibles à partir d'un état, les notent, puis continuent sur les meilleurs chemins de notation, j'ai également tenté d'exécuter l'algorithme de Djikstra pour trouver le chemin du problème . Cela semble d'une simplicité frustrante, mais je ne peux pas trouver un moyen de le faire fonctionner dans autre chose que du temps exponentiel. Y a-t-il un algorithme qui me manque qui s'applique ici?

Éditer

J'ai écrit cette fonction pour calculer le nombre minimum de coups requis: piles: liste de la liste des personnages représentant les pièces de la pile, piles [0] [0] est le haut de la pile [0] stack_ind: l'index du pile que la pièce sera ajoutée à needs_piece: la pièce qui doit être ajoutée à la pile needs_index: l'index où la pièce doit être située

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")

Modifier: cas de test sur des piles:

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

L'implémentation réelle du code n'est pas la partie qui est difficile, c'est de déterminer comment implémenter un algorithme qui résout le problème avec lequel je me bats.

Conformément à la demande de @ YonIif, j'ai créé un résumé du problème.

Lorsqu'il s'exécute, il génère un tableau aléatoire des piles et choisit une pièce aléatoire qui doit être insérée dans une pile aléatoire à un emplacement aléatoire.

L'exécuter imprime quelque chose de ce format sur la console.

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']

Mise à jour du statut

Je suis très déterminé à résoudre ce problème d'une manière ou d'une autre .

Gardez à l'esprit qu'il existe des moyens de minimiser le nombre de cas, tels que ceux @Hans Olsson mentionnés dans les commentaires. Mon approche la plus récente de ce problème a été de développer un ensemble de règles similaires à celles mentionnées et de les utiliser dans un algorithme générationnel.

Des règles telles que:

N'inversez jamais un mouvement. Passez de 1-> 0 puis 0-> 1 (n'a aucun sens)

Ne déplacez jamais un morceau deux fois de suite. Ne jamais passer de 0 -> 1 puis 1 -> 3

Étant donné un certain mouvement des piles [X] vers les piles [Y], puis un certain nombre de mouvements, puis un mouvement des piles [Y] vers les piles [Z], si les piles [Z] sont dans le même état que lors du déplacement des piles [X] aux piles [Y] s'est produit, un mouvement aurait pu être éliminé en passant directement des piles [X] aux piles [Z]

Actuellement, j'aborde ce problème avec une tentative de créer suffisamment de règles, qu'il minimise le nombre de mouvements "valides", suffisamment pour qu'une réponse puisse être calculée à l'aide d'un algorithme générationnel. Si quelqu'un peut penser à des règles supplémentaires, je serais intéressé de les entendre dans les commentaires.

Mise à jour

Grâce à la réponse de @RootTwo, j'ai fait une petite percée, que je vais décrire ici.

Vers la percée

Définissez la hauteur du but comme la profondeur de la pièce de but doit être placée dans la pile de destination.

Chaque fois qu'un morceau de but est placé à index <= stack_height - hauteur du but, il y aura toujours un chemin le plus court vers la victoire via la méthode clear_path ().

Let S represent some solid Piece.

C'EST À DIRE

Stacks = [ [R, R, G], [G, G, R], [-, -, -] ]
Goal = Stacks[0][2] = R
Goal Height = 2.
Stack Height - Goal Height = 0

Étant donné une telle pile stack[0] = R, le jeu est gagné.

                       GOAL
[ [ (S | -), (S | -), (S | -) ], [R, S, S], [(S | - ), (S | -), (S | -)] ]

Puisqu'il est connu qu'il y a toujours au moins des espaces vides stack_height disponibles, le pire des cas serait:

 [ [ S, S, !Goal ], [R, S, S], [-, -, -]

Puisque nous savons que la pièce de but ne peut pas être dans la destination du but ou que le jeu est gagné. Dans ce cas, le nombre minimum de mouvements requis serait le nombre de mouvements:

(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

Étant donné une telle pile stack[1] = R, le jeu est gagné.

              GOAL
[ [ (S | -), (S | -), S], [ (S | -), R, S], [(S | -), (S | -), (S | -)]

Nous savons qu'il y a au moins 3 espaces vides disponibles, donc le pire des cas serait:

[ [ S, !Goal, S], [S, R, S], [ -, -, - ]

Dans ce cas, le nombre minimum de coups serait le nombre de coups:

(1, 2), (0, 2), (0, 2), (1, 0)

Cela vaut pour tous les cas.

Ainsi, le problème a été réduit à un problème de trouver le nombre minimum de mouvements requis pour placer la pièce de but à ou au-dessus à la hauteur du but.

Cela divise le problème en une série de sous-problèmes:

1. Lorsque la pile de destination a sa pièce accessible! = Pièce de but, déterminer s'il y a un emplacement valide pour cette pièce, ou si la pièce doit y rester pendant qu'un autre morceau est échangé.

2. Lorsque la pile de destination a sa pièce accessible == pièce de but, déterminer si elle peut être retirée et placée à la hauteur de but requise, ou si la pièce doit rester pendant qu'une autre est échangée.

3. Lorsque les deux cas ci-dessus nécessitent l'échange d'une autre pièce, déterminer les pièces à échanger afin d'augmenter afin de permettre à la pièce de but d'atteindre la hauteur du but.

La pile de destination doit toujours avoir ses cas évalués en premier.

C'EST À DIRE

stacks = [ [-, R, G], [-, R, G], [-, R, G] ]

Goal = stacks[0][1] = G

La vérification de la pile de buts conduit d'abord à:

(0, 1), (0, 2), (1, 0), (2, 0) = 4 Moves

Ignorer la pile de buts:

(1, 0), (1, 2), (0, 1), (0, 1), (2, 0) = 5 Moves

J'ai proposé deux options, mais aucune d'entre elles n'est en mesure de résoudre le cas 2 en temps opportun. La première option utilise A * avec une mesure de distance de chaîne comme h (n), la deuxième option est IDA *. J'ai testé de nombreuses mesures de similitude de chaîne, j'ai utilisé smith-waterman dans mon approche. J'ai changé votre notation pour traiter le problème plus rapidement. J'ai ajouté des chiffres à la fin de chaque chiffre pour vérifier si une pièce a été déplacée deux fois.

Voici les cas sur lesquels j'ai testé:

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']
]

Voici le code 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')

Voici le code 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

Usage:

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)

Dans les commentaires que vous avez dit, il y a N piles de capacité P, et il y a toujours P espaces vides. Si tel est le cas, il semble que cet algorithme fonctionnera dans la elseclause de votre code (c'est-à-dire quand num_removals + min_to_unlock > num_free_spaces):

1. Trouvez la pièce désirée la plus proche du haut d'une pile.
2. Déplacez toutes les pièces du dessus de la pièce souhaitée de telle sorte qu'il y ait une pile (pas la pile de destination) qui a un espace vide au-dessus. Si nécessaire, déplacez les pièces de la pile de destination ou d'une autre pile. Si le seul espace ouvert est le haut de la pile de destination, déplacez-y un morceau pour ouvrir le haut d'une autre pile. Ceci est toujours possible, car il y a P espaces ouverts et au plus P-1 pièces pour se déplacer au-dessus de la pièce souhaitée.
3. Déplacez la pièce souhaitée à l'endroit vide au-dessus d'une pile.
4. Déplacez les pièces de la pile de destination jusqu'à ce que la destination soit ouverte.
5. Déplacez la pièce souhaitée vers la destination.

Bien que je n'aie pas trouvé le temps de le prouver mathématiquement, j'ai quand même décidé de poster ceci; J'espère que cela aide. L'approche consiste à définir un paramètre p qui diminue avec de bons coups et atteint zéro exactement lorsque le jeu est terminé. Dans le programme, ne considère que les bons coups ou les coups neutres (qui ne modifient pas p) et oublient les mauvais coups (qui augmentent p).

Alors qu'est-ce que p? Pour chaque colonne, définissez p comme le nombre de blocs qui doivent encore être supprimés avant que toutes les couleurs de cette colonne soient la couleur souhaitée. Supposons donc que nous voulons que les blocs rouges se retrouvent dans la colonne la plus à gauche (j'y reviendrai plus tard), et supposons qu'il y ait un bloc rouge en bas, puis un jaune en plus de cela, un bloc de plus en haut de cela, puis un espace vide. Puis p = 2 pour cette colonne (deux blocs à retirer avant que tous ne soient rouges). Calculez p pour toutes les colonnes. Pour la colonne qui doit finir vide, p est égal au nombre de blocs qui s'y trouvent (tous doivent aller). P pour l'état actuel est la somme de tous les p pour toutes les colonnes.

Lorsque p = 0, toutes les colonnes ont la même couleur et une colonne est vide, donc le jeu est terminé.

En choisissant des mouvements qui diminuent p (ou du moins n'augmentent pas p), nous allons dans la bonne direction, c'est à mon avis la différence cruciale avec les algorithmes de chemin le plus court: Dijkstra ne savait pas s'il se déplaçait dans la bonne direction à chaque sommet qu'il enquêtait.

Alors, comment pouvons-nous déterminer où chaque couleur doit se retrouver? Fondamentalement, en déterminant p pour chaque possibilité. Par exemple, commencez par rouge / jaune / vert / vide, calculez p, puis passez à rouge / jaune / vide / vert, calculez p, etc. Prenez la position de départ avec le p le plus bas. Cela prend n! calculs. Pour n = 8, c'est 40320, ce qui est faisable. La mauvaise nouvelle est que vous devrez examiner toutes les positions de départ avec le p le plus bas égal. La bonne nouvelle est que vous pouvez oublier le reste.

Il y a ici deux incertitudes mathématiques. Un: est-il possible qu'il existe un chemin plus court qui utilise un mauvais mouvement? Cela semble peu probable, je n'ai pas trouvé de contre-exemple, mais je n'ai pas non plus trouvé de preuve. Deuxièmement: est-il possible qu'en commençant avec une position de départ non optimale (c'est-à-dire pas le p le plus bas), il y ait un chemin plus court qu'avec toutes les positions de départ optimales. Encore une fois: pas de contre-exemple mais pas de preuve non plus.

Quelques suggestions d'implémentation. Garder une trace de p pendant l'exécution pour chaque colonne n'est pas difficile mais doit bien sûr être fait. Un autre paramètre à conserver pour chaque colonne est le nombre de spots ouverts. Si 0, alors ces colonnes ne peuvent momentanément accepter aucun bloc, elles peuvent donc être exclues de la boucle. Lorsque p = 0 pour une colonne, elle n'est pas éligible pour un pop. Pour chaque pop possible, examinez s'il y a un bon mouvement, c'est-à-dire celui qui diminue le p global. S'il y en a plusieurs, examinez-les tous. S'il n'y en a pas, considérez tous les mouvements neutres.

Tout cela devrait considérablement réduire votre temps de calcul.