¿Cómo encontrar el número mínimo de movimientos para mover un elemento a una posición en una pila?

Dado un conjunto de pilas NXP, siendo N la cantidad de pilas y P la capacidad de las pilas, ¿cómo puedo calcular la cantidad mínima de intercambios necesarios para pasar de un nodo en la ubicación A a una ubicación arbitraria B? Estoy diseñando un juego, y el objetivo final es ordenar todas las pilas para que sean del mismo color.

# 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 quiero insertar una "B" en stacks[1][1]tal que stacks[1] = ["-", "B", "Y", "Y"]. ¿Cómo puedo determinar la cantidad mínima de movimientos necesarios para hacerlo?

He estado buscando múltiples enfoques, probé algoritmos genéticos que generan todos los movimientos posibles desde un estado, los puntúan y luego continúan por los mejores caminos de puntuación, también he intentado ejecutar el algoritmo de Djikstra para encontrar el camino en el problema . Parece frustrantemente simple, sin embargo, no puedo encontrar una manera de hacerlo funcionar en otra cosa que no sea el tiempo exponencial. ¿Me falta algún algoritmo que sea aplicable aquí?

Editar

He escrito esta función para calcular el número mínimo de movimientos necesarios: pilas: Lista de personajes que representan las piezas en la pila, las pilas [0] [0] es la parte superior de la pila [0] stack_ind: El índice de la apilar que la pieza se agregará a needs_piece: la pieza que se debe agregar a la pila needs_index: el índice donde se debe ubicar la pieza

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

Editar: Casos de prueba en pilas:

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

La implementación del código real no es la parte difícil, es determinar cómo implementar un algoritmo que resuelva el problema con el que estoy luchando.

Según la solicitud de @ YonIif, he creado una idea general del problema.

Cuando se ejecuta, genera una matriz aleatoria de las pilas y elige una pieza aleatoria que debe insertarse en una pila aleatoria en una ubicación aleatoria.

Ejecutarlo imprime algo de este formato en la consola.

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

Actualización de estado

Estoy muy decidido a resolver este problema de alguna manera .

Tenga en cuenta que hay formas de minimizar el número de casos, como los que @Hans Olsson menciona en los comentarios. Mi enfoque más reciente para este problema ha sido desarrollar un conjunto de reglas similares a las mencionadas y emplearlas en un algoritmo generacional.

Reglas como:

Nunca reviertas un movimiento. Ir de 1-> 0 luego 0-> 1 (No tiene sentido)

Nunca muevas una pieza dos veces seguidas. Nunca moverse de 0 -> 1 luego 1 -> 3

Dado algún movimiento de las pilas [X] a las pilas [Y], luego cierto número de movimientos, luego un movimiento de las pilas [Y] a las pilas [Z], si las pilas [Z] están en el mismo estado que cuando se movió de las pilas [X] a las pilas [Y] ocurrió, un movimiento podría haberse eliminado moviéndose directamente de las pilas [X] a las pilas [Z]

Actualmente, me estoy acercando a este problema con un intento de crear suficientes reglas, para minimizar el número de movimientos "válidos", lo suficiente como para que se pueda calcular una respuesta utilizando un algoritmo generacional. Si alguien puede pensar en reglas adicionales, me interesaría escucharlas en los comentarios.

Actualizar

Gracias a la respuesta de @RootTwo, he tenido un pequeño avance, que esbozaré aquí.

Sobre el avance

Defina la altura de la portería como la profundidad en que la pieza de portería debe colocarse en la pila de destino.

Cada vez que una pieza de gol se coloca en index <= stack_height - altura de gol, siempre habrá un camino más corto hacia la victoria a través del método clear_path ().

Let S represent some solid Piece.

ES DECIR

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

Dada una pila tal que stack[0] = Rel juego se gana.

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

Como se sabe que siempre hay al menos espacios en blanco stack_height disponibles, el peor de los casos sería:

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

Como sabemos que la pieza de gol no puede estar en el destino de gol o el juego está ganado. En cuyo caso, el número mínimo de movimientos necesarios serían los movimientos:

(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

Dada una pila tal que stack[1] = Rel juego se gana.

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

Sabemos que hay al menos 3 espacios en blanco disponibles, por lo que el peor de los casos sería:

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

En este caso, el número mínimo de movimientos serían los movimientos:

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

Esto será válido para todos los casos.

Por lo tanto, el problema se ha reducido a un problema de encontrar el número mínimo de movimientos necesarios para colocar la pieza de portería a la altura de la portería o por encima.

Esto divide el problema en una serie de subproblemas:

1. Cuando la pila de destino tiene su pieza accesible! = Pieza objetivo, determina si hay una ubicación válida para esa pieza, o si la pieza debe permanecer allí mientras se intercambia otra pieza.

2. Cuando la pila de destino tiene su pieza accesible == pieza de portería, determina si se puede quitar y colocar a la altura de portería requerida, o si la pieza debe permanecer mientras se intercambia otra.

3. Cuando los dos casos anteriores requieren que se intercambie otra pieza, determinar qué piezas intercambiar para aumentar y hacer posible que la pieza de meta alcance la altura de la meta.

La pila de destino siempre debe evaluar primero sus casos.

ES DECIR

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

Goal = stacks[0][1] = G

Comprobar la pila de objetivos primero conduce a:

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

Ignorando la pila de objetivos:

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

Se me ocurrieron dos opciones, pero ninguna de ellas puede resolver el caso 2 de manera oportuna. La primera opción es usar A * con una medida de distancia de cadena como su h (n), la segunda opción es IDA *. Probé muchas medidas de similitud de cuerdas, usé smith-waterman en mi enfoque. He cambiado tu notación para tratar el problema más rápido. He agregado números al final de cada dígito para verificar si una pieza se movió dos veces.

Estos son los casos que he probado en:

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

Aquí está el código 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')

Aquí está el código 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

Uso:

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)

En los comentarios que dijo que hay N pilas con capacidad P, y siempre hay P espacios vacíos. Si ese es el caso, parece que este algoritmo funcionará en la elsecláusula de su código (es decir, cuandonum_removals + min_to_unlock > num_free_spaces ):

1. Encuentra la pieza deseada que esté más cerca de la parte superior de una pila.
2. Mueva todas las piezas desde arriba de la pieza deseada de tal manera que haya una pila (no la pila de destino) que tenga un espacio vacío en la parte superior. Si es necesario, mueva las piezas de la pila de destino u otra pila. Si el único espacio abierto es la parte superior de la pila de destino, mueva una pieza allí para abrir la parte superior de otra pila. Esto siempre es posible, porque hay espacios abiertos P y, como máximo, piezas P-1 para moverse desde arriba de la pieza deseada.
3. Mueva la pieza deseada al lugar vacío en la parte superior de una pila.
4. Mueva las piezas de la pila de destino hasta que el destino esté abierto.
5. Mueva la pieza deseada al destino.

Aunque no he encontrado el tiempo para probar esto matemáticamente, decidí publicar esto de todos modos; Espero eso ayude. El enfoque consiste en definir un parámetro p que disminuya con buenos movimientos y llegue a cero exactamente cuando el juego haya terminado. En el programa solo se consideran buenos movimientos o movimientos neutrales (que dejan p sin cambios) y se olvidan de los malos movimientos (que aumentan p).

Entonces, ¿qué es p? Para cada columna, defina p como el número de bloques que aún deben eliminarse antes de que todos los colores de esa columna sean del color deseado. Supongamos que queremos que los bloques rojos terminen en la columna más a la izquierda (volveré sobre eso más adelante), y supongamos que hay un bloque rojo en la parte inferior, luego un amarillo encima de eso, un bloque más encima eso, y luego un espacio vacío. Entonces p = 2 para esta columna (dos bloques para eliminar antes de que todos sean rojos). Calcule p para todas las columnas. Para la columna que debería terminar vacía, p es igual al número de bloques que contiene (todos deben ir). P para el estado actual es la suma de todas las p para todas las columnas.

Cuando p = 0, todas las columnas tienen el mismo color y una columna está vacía, por lo que el juego ha terminado.

Al elegir movimientos que disminuyen p (o al menos no aumentan p) nos estamos moviendo en la dirección correcta, esta es en mi opinión la diferencia crucial con los algoritmos de ruta más corta: Dijkstra no tenía idea de si se estaba moviendo en la dirección correcta con cada vértice que estaba investigando.

Entonces, ¿cómo determinamos dónde debe terminar cada color? Básicamente determinando p para cada posibilidad. Entonces, por ejemplo, comience con rojo / amarillo / verde / vacío, calcule p, luego vaya a rojo / amarillo / vacío / verde, calcule p, etc. Tome la posición inicial con la p más baja. Esto toma n! cálculos Para n = 8 esto es 40320, que es factible. La mala noticia es que tendrá que examinar todas las posiciones iniciales con la p más baja. La buena noticia es que puedes olvidarte del resto.

Aquí hay dos incertidumbres matemáticas. Uno: ¿es posible que haya un camino más corto que use un mal movimiento? Parece poco probable, no he encontrado un contraejemplo, pero tampoco he encontrado una prueba. Dos: es posible que al comenzar con una posición inicial no óptima (es decir, no la p más baja) haya una ruta más corta que con todas las posiciones iniciales óptimas. De nuevo: sin contraejemplo, pero tampoco prueba.

Algunas sugerencias de implementación. Hacer un seguimiento de p durante la ejecución de cada columna no es difícil, pero, por supuesto, debe hacerse. Otro parámetro que debe mantenerse para cada columna es el número de espacios abiertos. Si es 0, entonces estas columnas pueden no aceptar momentáneamente ningún bloque, por lo que pueden quedar fuera del ciclo. Cuando p = 0 para una columna, no es elegible para un pop. Para cada pop posible, examine si hay un buen movimiento, es decir, uno que disminuya la p general. Si hay múltiples, examine todos. Si no hay ninguno, considere todos los movimientos neutrales.

Todo esto debería reducir en gran medida el tiempo de cálculo.