python - 执行 15 题的终止条件应该是什么？

Question

我正在尝试实现一个解决方案来输出 15-puzzle 的移动序列Python 中的问题。这是 MOOC 可选作业的一部分。问题陈述在 this link 处给出。 .

我有一个执行有效转换的程序版本(如下所示)。

我首先确定空单元格(用 0 表示)的邻居并将它们放入列表中。然后，我从列表中随机选择一个邻居来与空单元格进行交换。所有交换都累积在不同的列表中，以记录解决难题的移动顺序。然后在程序结束时输出。

但是，随机选择数字与空单元格进行交换的过程将永远持续下去。为了避免“无限”(非常长的运行)循环，我现在将交换次数限制为 30。

from random import randint
def find_idx_of_empty_cell(p):
    for i in range(len(p)):
        if p[i] == 0:
            return i

def pick_random_neighbour_idx(neighbours_idx_list):
    rand_i = randint(0, len(neighbours_idx_list)-1)
    return neighbours_idx_list[rand_i]

def perform__neighbour_transposition(p, tar_idx, src_idx):
    temp = p[tar_idx]
    p[tar_idx] = p[src_idx]
    p[src_idx] = temp

def solve_15_puzzle(p):
    standard_perm = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
    neighbours_idx_list = []
    moves_sequence = []
    empty_cell_idx = find_idx_of_empty_cell(p)
    previous_empty_cell_idx = empty_cell_idx

    while (not(p == standard_perm) and len(moves_sequence) < 30):
        if not (empty_cell_idx in [0,4,8,12]):
            neighbours_idx_list.append(empty_cell_idx - 1)
        if not (empty_cell_idx in [3,7,11,15]):
            neighbours_idx_list.append(empty_cell_idx + 1)
        if not (empty_cell_idx in [0,1,2,3]):
            neighbours_idx_list.append(empty_cell_idx - 4)
        if not (empty_cell_idx in [12,13,14,15]):
            neighbours_idx_list.append(empty_cell_idx + 4)

        if previous_empty_cell_idx in neighbours_idx_list:
            neighbours_idx_list.remove(previous_empty_cell_idx)

        chosen_neighbour_idx = pick_random_neighbour_idx(neighbours_idx_list)
        moves_sequence.append(p[chosen_neighbour_idx])
        perform__neighbour_transposition(p, empty_cell_idx, chosen_neighbour_idx)
        previous_empty_cell_idx = empty_cell_idx
        empty_cell_idx = chosen_neighbour_idx
        neighbours_idx_list = []

    if (p == standard_perm):
        print("Solution: ", moves_sequence)

对于以下方法调用，预期输出为 [15, 14, 10, 13, 9, 10, 14, 15]。

solve_15_puzzle([1, 2, 3, 4, 5, 6, 7, 8, 13, 9, 11, 12, 10, 14, 15, 0])

Answer 1

15 block 瓷砖的问题乍一看似乎更难。

计算最佳(最短)解是一个难题，并且已经证明，当 N 增加时寻找最优解是 NP-hard。

找到(非最佳)解决方案要容易得多。例如，可以使用一个非常简单的算法:

• 将当前位置的“距离”定义为 manhattandistances 的总和从你想要的位置开始的每一 block 瓷砖
• 从给定的位置开始，做一些随机的移动
• 如果移动后的距离有所改善或保持不变，则保留更改，否则撤消它们并返回起点。

这种算法可以描述为一种多步随机爬山方法，能够解决 15 难题(只要确保允许足够的随机移动以能够逃脱局部最小值)。

Python 可能不是解决此问题的最佳语言，但如果您使用 PyPy 实现，您可以在合理的时间内获得解决方案。

我的实现为在几秒钟内混合了 1000 次随机移动的谜题找到了解决方案，例如:

(1, 5, 43, [9, [4, 10, 14, 11, 15, 3, 8, 1, 13, None, 9, 7, 12, 2, 5, 6]])
(4, 17, 41, [9, [4, 10, 14, 11, 15, 3, 8, 1, 12, None, 6, 2, 5, 13, 9, 7]])
(7, 19, 39, [11, [4, 10, 14, 11, 15, 3, 1, 2, 12, 6, 8, None, 5, 13, 9, 7]])
(9, 54, 36, [5, [4, 14, 3, 11, 15, None, 10, 2, 12, 6, 1, 8, 5, 13, 9, 7]])
(11, 60, 34, [10, [4, 14, 3, 11, 15, 10, 1, 2, 12, 6, None, 8, 5, 13, 9, 7]])
(12, 93, 33, [14, [4, 14, 11, 2, 15, 10, 3, 8, 12, 6, 1, 7, 5, 13, None, 9]])
(38, 123, 31, [11, [4, 14, 11, 2, 6, 10, 3, 8, 15, 12, 1, None, 5, 13, 9, 7]])
(40, 126, 30, [13, [15, 6, 4, 2, 12, 10, 11, 3, 5, 14, 1, 8, 13, None, 9, 7]])
(44, 172, 28, [10, [15, 4, 2, 3, 12, 6, 11, 8, 5, 10, None, 14, 13, 9, 1, 7]])
(48, 199, 23, [11, [15, 6, 4, 3, 5, 12, 2, 8, 13, 10, 11, None, 9, 1, 7, 14]])
(61, 232, 22, [0, [None, 15, 4, 3, 5, 6, 2, 8, 1, 12, 10, 14, 13, 9, 11, 7]])
(80, 276, 20, [10, [5, 15, 4, 3, 1, 6, 2, 8, 13, 10, None, 7, 9, 12, 14, 11]])
(105, 291, 19, [4, [9, 1, 2, 4, None, 6, 8, 7, 5, 15, 3, 11, 13, 12, 14, 10]])
(112, 313, 17, [9, [1, 6, 2, 4, 9, 8, 3, 7, 5, None, 14, 11, 13, 15, 12, 10]])
(113, 328, 16, [15, [1, 6, 2, 4, 9, 8, 3, 7, 5, 15, 11, 10, 13, 12, 14, None]])
(136, 359, 15, [4, [1, 6, 2, 4, None, 8, 3, 7, 9, 5, 11, 10, 13, 15, 12, 14]])
(141, 374, 12, [15, [1, 2, 3, 4, 8, 6, 7, 10, 9, 5, 12, 11, 13, 15, 14, None]])
(1311, 385, 11, [14, [1, 2, 3, 4, 8, 5, 7, 10, 9, 6, 11, 12, 13, 15, None, 14]])
(1329, 400, 10, [13, [1, 2, 3, 4, 6, 8, 7, 10, 9, 5, 11, 12, 13, None, 15, 14]])
(1602, 431, 9, [4, [1, 2, 3, 4, None, 6, 8, 7, 9, 5, 11, 10, 13, 15, 14, 12]])
(1707, 446, 8, [5, [1, 2, 3, 4, 6, None, 7, 8, 9, 5, 15, 12, 13, 10, 14, 11]])
(1711, 475, 7, [12, [1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 15, 12, None, 13, 14, 11]])
(1747, 502, 6, [8, [1, 2, 3, 4, 6, 5, 7, 8, None, 9, 10, 12, 13, 14, 15, 11]])
(1824, 519, 5, [14, [1, 2, 3, 4, 9, 6, 7, 8, 5, 10, 15, 12, 13, 14, None, 11]])
(1871, 540, 4, [10, [1, 2, 3, 4, 9, 6, 7, 8, 5, 10, None, 12, 13, 14, 15, 11]])
(28203, 555, 3, [9, [1, 2, 3, 4, 5, 6, 7, 8, 9, None, 10, 12, 13, 14, 11, 15]])
(28399, 560, 2, [10, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, None, 12, 13, 14, 11, 15]])
(28425, 581, 1, [11, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, None, 13, 14, 15, 12]])
(28483, 582, 0, [15, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, None]])

最后一行表示经过 24,483 次实验后，它在 582 次移动后找到了目标位置。请注意，582 肯定远非最佳，因为众所周知，经典版本的 15 拼图中没有任何位置需要超过 80 步。

移动次数后的数字是“曼哈顿距离”，例如倒数第四行是位置:

其中与解决方案的曼哈顿距离之和为 3。