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

3条回答

网友

1楼 · 编辑于 2024-10-17 06:32:07

虽然我还没有时间从数学上证明这一点，但我还是决定发布这篇文章；希望能有帮助。该方法是定义一个参数p，该参数随着良好的移动而减小，并在游戏结束时精确地达到零。在程序中，只考虑好的移动或中性移动（保持p不变），而忽略坏的移动（增加p）

那么什么是p？对于每列，将p定义为在该列中的所有颜色成为所需颜色之前仍需删除的块数。因此，假设我们希望红色块在最左边的列中结束（我稍后会回来讨论），假设底部有一个红色块，顶部有一个黄色块，顶部还有一个块，然后是一个空白。然后，该列的p=2（在全部为红色之前删除两个块）。计算所有列的p。对于最后应该为空的列，p等于其中的块数（所有块都应该为空）。当前状态的P是所有列的所有P的总和

当p=0时，所有列的颜色相同，一列为空，因此游戏结束

通过选择减少p（或至少不增加p）的移动，我们正在朝正确的方向移动，在我看来，这是最短路径算法的关键区别：Dijkstra不知道他在调查的每个顶点是否都朝着正确的方向移动

那么，我们如何确定每种颜色应该在哪里结束呢？基本上通过确定每种可能性的p。例如，从红/黄/绿/空开始，计算p，然后转到红/黄/空/绿，计算p，等等。取p最低的起始位置。这需要n！计算。对于n=8，这是40320，这是可行的。坏消息是，你必须检查所有最低p值相等的起始位置。好消息是你可以忘记剩下的

这里有两个数学上的不确定性。第一：有没有可能有一条较短的路径使用了错误的移动？似乎不太可能，我还没有找到反例，但我也没有找到证据。第二：当从非最佳起始位置（即非最低p）开始时，是否有可能比所有最佳起始位置的路径更短。再说一遍：没有反例，但也没有证据

一些实施建议。在每个列的执行过程中跟踪p并不困难，但当然应该这样做。应为每列保留的另一个参数是开放点的数量。如果为0，则此列可能暂时不接受任何块，因此可以不在循环中。当某列的p=0时，该列不符合pop的条件。对于每一个可能的pop，检查是否有一个好的移动，即降低总体p。如果有多个，请检查所有。如果没有，考虑所有中性的动作。

所有这些都将大大减少您的计算时间

网友

2楼 · 编辑于 2024-10-17 06:32:07

我提出了两个选择，但没有一个能够及时解决案例2。第一个选项是使用带有字符串距离度量的*作为h（n），第二个选项是IDA*。我测试了许多字符串相似性度量，在我的方法中使用了smith waterman。我已更改了您的符号，以便更快地处理这个问题。我在每个数字的末尾添加了数字，以检查一个工件是否移动了两次

以下是我测试过的案例：

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

以下是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')

以下是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

用法：

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)

网友

3楼 · 编辑于 2024-10-17 06:32:07

在您的评论中，有N个堆栈的容量为p，并且总是有p个空格。如果是这种情况，那么这个算法似乎可以在代码中的else子句中工作（即num_removals + min_to_unlock > num_free_spaces）：

找到最靠近堆叠顶部的所需工件
从所需工件上方移动所有工件，使一个堆栈（不是目标堆栈）顶部有一个空空间。如果需要，从目标堆栈或其他堆栈中移动工件。如果唯一的开放空间是目标堆栈的顶部，则将一个工件移动到该位置以打开另一个堆栈的顶部。这始终是可能的，因为有P个开放空间，最多P-1个工件从所需工件上方移动
将所需工件移动到堆栈顶部的空白位置
从目标堆栈移动工件，直到目标打开
将所需工件移动到目标位置

编辑

状态更新

更新

相关问题更多 >

编程相关推荐

热门问题

热门文章