如何找到将项目移动到堆栈中某个位置的最小移动次数？

Question

给定一组 NXP 堆栈，其中 N 是堆栈数，P 是堆栈容量，如何计算从位置 A 的某个节点移动到某个任意位置 B 所需的最小交换次数？我正在设计一个游戏，最终目标是对所有堆栈进行排序，使它们都具有相同的颜色。

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

如果我想在stacks[1][1]这样的stacks[1] = ["-", "B", "Y", "Y"]. 我如何确定这样做所需的最小移动次数？

我一直在研究多种方法，我尝试过从一个状态生成所有可能的移动的遗传算法，对它们进行评分，然后继续沿着最佳评分路径，我还尝试运行 Djikstra 的算法来寻找问题的路径. 这看起来简单得令人沮丧，但我想不出办法让它在指数时间内运行。是否有我遗漏的适用于此的算法？

编辑

我编写了这个函数来计算所需的最小移动次数： stacks: List of Characters List of Characters 代表堆栈中的碎片，stacks[0][0] 是 stack[0] 的顶部 stack_ind：将被添加到堆栈的碎片needs_piece：应该被添加到堆栈的碎片needs_index：碎片应该位于的索引

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

编辑：堆栈上的测试用例：

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

实际的代码实现并不是困难的部分，它决定了如何实现一种算法来解决我正在努力解决的问题。

根据@YonIif 的要求，我为这个问题创建了一个要点。

当它运行时，它会生成一个随机的堆栈数组，并选择一个需要插入到随机位置的随机堆栈中的随机片段。

运行它会将这种格式的内容打印到控制台。

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

状态更新

我非常有决心以某种方式解决这个问题。

请记住，有一些方法可以最大限度地减少案例数量，例如@Hans Olsson 在评论中提到的案例。我最近解决这个问题的方法是开发一组类似于上述规则的规则，并将它们用于分代算法。

规则例如：

永远不要逆转一个动作。从 1->0 然后 0->1 （没有意义）

永远不要连续移动一块。从不从 0 -> 1 然后 1 -> 3 移动

给定从 stacks[X] 到 stacks[Y] 的一些移动，然后是一定数量的移动，然后从 stacks[Y] 移动到 stacks[Z]，如果 stacks[Z] 的状态与移动时的状态相同从 stacks[X] 到 stacks[Y] 发生了，可以通过从 stacks[X] 直接移动到 stacks[Z] 来消除移动

目前，我正在尝试创建足够的规则来解决这个问题，它最大限度地减少“有效”移动的数量，足以使答案可以使用分代算法来计算。如果有人能想到其他规则，我很想在评论中听到它们。

更新

感谢@RootTwo 的回答，我有了一些突破，我将在这里概述。

走向突破

将目标高度定义为目标块必须放置在目标堆栈中的深度。

每当某个球门被放置在 index <= stack_height - 球门高度时，通过 clear_path() 方法总会有一条通往胜利的最短路径。

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

给定一些筹码使得stack[0] = R，游戏获胜。

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

由于已知它们总是至少有 stack_height 可用的空白空间，因此最坏的情况是：

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

因为我们知道目标块不能在目标目的地或游戏获胜。在这种情况下，所需的最少移动次数为：

(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

给定一些筹码使得stack[1] = R，游戏获胜。

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

我们知道至少有 3 个空格可用，因此最坏的情况是：

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

在这种情况下，最小移动次数为：

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

这将适用于所有情况。

因此，问题已简化为找到将球门块放置在球门高度处或上方所需的最小移动次数的问题。

这将问题分解为一系列子问题：

1. 当目标堆栈具有其可访问的块 != 目标块时，确定该块是否存在有效位置，或者在交换另一个块时该块是否应该留在那里。

2. 当目标堆栈具有其可访问的块 == 目标块时，确定是否可以将其移除并放置在所需的目标高度，或者在交换另一个块时是否应保留该块。

3. 当上述两种情况需要换块时，确定换哪个块才能增加，使目标块达到目标高度。

目标堆栈应始终首先评估其案例。

IE

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

Goal = stacks[0][1] = G

首先检查目标堆栈会导致：

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

忽略目标堆栈：

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

Answer 1

在评论中你说有N个容量为P的堆栈，并且总是有P个空闲空间。如果是这种情况，似乎该算法将在else代码中的子句中起作用（即 when num_removals + min_to_unlock > num_free_spaces）：

1. 找到最接近堆栈顶部的所需部分。
2. 将所有棋子从所需棋子上方移动，使得有一个堆栈（不是目标堆栈）顶部有空白空间。如果需要，从目标堆栈或另一个堆栈中移动棋子。如果唯一的开放空间是目标堆栈的顶部，请将棋子移到那里以打开另一个堆栈的顶部。这总是可能的，因为有 P 个开放空间，最多有 P-1 个棋子可以从所需棋子上方移动。
3. 将所需的棋子移至堆栈顶部的空白位置。
4. 从目标堆栈中移动棋子，直到目标打开。
5. 将所需的棋子移动到目的地。