2011到2012的迷宫

迷宫难题

从左边入口处的“2011”进去，在迷宫里转悠，最后变为“2012”从右边出来。你可以在迷宫里随便转圈，可以重复之前走过的路，但不能直接退回上一次刚刚走过的路。每经过一条路时都需要按照路上的标示立即进行计算。

思考解题方案

这是一个广度搜索问题。由于同一条路不能连续走两回，因此已搜索过的状态节点包括三个信息：

• 当前位置：2011处的位置编号为0， 中间处的位置编号为1， 2012处的编号为2。
• 当前的数值。
• 上一步走过的路径。 注意 这个信息容易忽略，若忽略则不能得到正确解答。

从初始状态(0, 2011, “*”)开始，搜索状态(2, 2012, “3”)或(2, 2012, “5”)。其中”*”表示起点。每个状态节点都有几个相邻的状态，例如对于初始状态来说，如果走”+7”路径就到达状态(1,2018,”7”)。由于2011是一个奇数，我们不选择”/2”这条路径。

所谓广度搜索就是将所有与当前状态相邻的状态都放进一个队列中，然后从队列取出下一个状态，并重复上述步骤，直到找到目标状态。为了在搜索到目标状态时，能输出从起点状态开始所走过的路径，队列中的状态会将整个路径保存在起来。

程序

from collections import deque

def solve(from_, to_):
    queue = deque([(0, from_, "*")]) ❶
    visited = set([]) ❷

    def next_value(pos, value):
        if pos == 0: # 在左边位置时
            yield 1, value+7, "7"
            if value % 2==0: # 只有当前的值为偶数时才选择除以2这条路
                yield 1, value//2, "2"
        if pos == 1: # 在中间位置时
            yield 0, value+7, "7"
            if value % 2==0:
                yield 0, value//2, "2"
            yield 2, value*3, "3"
            yield 2, value-5, "5"
        if pos == 2: # 在右边位置时
            yield 1, value*3, "3"
            yield 1, value-5, "5"

    while True:
        pos, value, path = queue.popleft()
        last = path[-1] # 最后走过的路径
        visit = (pos, value, last)
        if visit in visited: continue ❸
        visited.add(visit) ❹
        for p, v, n in next_value(pos, value):
            if n != last: ❺
                if p == 2 and v == to_: # 如果右边位置，并且值为目标值则返回路径
                    return path + n
                queue.append((p, v, path+n))

path = solve(2011, 2012)

❶程序采用deque队列保存待搜索的状态节点，一开始只包含初始状态。❷为了加快搜索速度，我们使用一个visited集合保存所有访问过的状态节点。每访问一个状态节点，就将(位置, 数值, 最后走过的路径)存放到visited集合之中。❸如果从队列中取出的状态已经在visited集合中，就没有必要对其进行展开了。❹将展开过一次的状态保存到visited集合中。

next_value(pos, value)返回在pos位置，值为value时所有可能走的路径，其中包括上一次走过的路径。因此需要❺判断是否和上一次走的路径相同。

程序的输出为：

*7272753272735272753532753275

deque简介

在Python中，列表是一个动态的数组，在其尾部添加或删除元素的时间复杂度都是常数，但是在头部添加或删除元素则需要移动列表中所有的元素，因此时间复杂度为O(n)。显然列表只适合作为栈而不适合作为队列。deque是一个双向链表结构，从头部和尾部添加或删除元素的时间复杂度都为常数，但是访问某个下标的元素需要遍历链表，因此访问元素的时间复杂度为O(n)。