按降序排列砖塔的最少移动次数

Question

我有一个问题，我有 n 个带有 i 块砖的塔。我需要按降序重新排列它们。我一次只能移动砖块到相邻的塔楼。 例如，对于这个问题：

4 3 0 1 1

答案是 1 步，因为我可以将一块砖从第二个塔移到第三个塔，并得到：4 2 1 1 1。

对于这样的问题：

7 0 0 0 1

答案是移动 3 步即可得到：7 1 0 0 0 或 6 1 1 0 0。

我目前有这个功能：

def compute_min_moves(towers, moves = 0):
    # Si 0 o 1 torre, no se hace nada
    if len(towers) < 2:
        return moves

    for i in range(len(towers)-1, 0 ,-1):
        if towers[i - 1] < towers[i]:
            diff = 0
            while towers[i - 1] < towers[i]:
                diff += 1
                towers[i - 1] += diff
                towers[i] -= diff
                moves += diff   
           
            sub_array = towers[i-1:]
            if not all(earlier >= later for earlier, later in zip(sub_array, sub_array[1:])):
                moves = compute_min_moves(towers, moves)

    return moves

我不知道如何才能得到最佳解决方案。

Answer 1

您最初的解决方案仅在塔之间从右到左移动砖块，因此您提出的最佳解决方案 4 3 0 1 1 永远无法找到（因为它从左到右移动棋子）。

您做了一些调整来缩小问题范围，但仍然只是从左到右移动砖块，而忘记了之前做过的事情。

您提出的算法的另一个问题是，它会不断从塔上移动砖块，直到它与旁边的砖块相等，这不一定是解决问题的最快方法。

这是一种更通用的方法：由于您需要最少的移动次数，因此广度优先搜索是最好的方法。通过探索从起始位置开始的所有可能的移动，然后从 n=1 个位置开始的所有可能的移动，依此类推，您可以保证第一次达到解决方案时，您将以最少的移动次数完成此任务（尽管它不会找到所有此类解决方案 - 它会在找到第一个解决方案后终止）。

使问题进一步复杂化的是，允许双向移动，您需要确保不会在搜索中创建循环。

广度优先搜索的一个好机制是创建一个迄今为止探索过的位置队列，将新的可到达位置添加到队列末尾（如果它们不能彻底解决问题），并在读取时继续这样做队列的开始。

这是该方法的示例实现。

def solved(towers):
    return len(towers) < 2 or all(t1 >= t2 for t1, t2 in zip(towers, towers[1:]))


def solve(towers: list[int]) -> (int, list[int]):
    if solved(towers):
        return 0, towers
    # keep track of visited states, to avoid cycles
    visited = {tuple(towers)}
    # queue of states to visit, preceded by the number of moves to reach them
    queue = [(0, towers)]
    # range of left indices to move between them and the next (right)
    r = range(len(towers) - 1)
    # it's safe to loop while True, since the algorithm is guaranteed to terminate
    # (although it may run for a very long time for large problems)
    while True:
        n, prev_pos = queue.pop(0)
        for i in r:
            # to avoid repeating the same code twice (once for each direction)
            # we iterate over a tuple of (direction and offset)
            for d, o in ((1, 1), (-1, 0)):
                # the tower we're moving from must contain at least one brick
                if prev_pos[i+o] > 0:
                    # copy the previous position and make a single move
                    new_pos = prev_pos.copy()
                    new_pos[i] += d
                    new_pos[i+1] -= d
                    # convert the new position in a (hashable) tuple to check visited
                    if (new_post_tuple := tuple(new_pos)) not in visited:
                        # if the position wasn't visited before, check if it solves the problem
                        if solved(new_pos):
                            return n+1, new_pos
                        # otherwise, avoid visiting it again
                        visited.add(new_post_tuple)
                        # add it to the queue to expand from later
                        queue.append((n+1, new_pos))


print(solve([4, 3, 0, 1, 1]))
print(solve([7, 0, 0, 0, 1]))

输出：

(1, [4, 2, 1, 1, 1])
(3, [6, 1, 1, 0, 0])

我没有看到从您迄今为止的解决方案到始终找到最佳解决方案的直接方法，因此我选择分享我想出的解决方案。请根据上面的反馈更仔细地研究您自己的解决方案，并且不要简单地接受“答案” - 我认为这是应该教您一些东西的作业的一部分，因此如果您提交我的答案将不会有帮助当作你自己的工作。也许只是看看它，然后根据你学到的知识尝试实现你自己的。