一个BFS应用的实例

先介绍一下题目：

首先有一种类似魔方抽象出来的一组数组，

一个BFS应用的实例

然后呢这个数组有三种变换方式，第一种是上下交换,rotation exchange变换后如图这样，

一个BFS应用的实例

第二种变换是是把前三列向前移一格，最后一列移到最前面叫做right circular shift。

一个BFS应用的实例

第三种变换是把中间的第二列和第三列的数字按照顺指针旋转一个格子得到的。middle clockwise rotation。

一个BFS应用的实例

一共就只有这三种变换，然后给你一个数组“12345678”，和一个变换后的数组比如”23415786“问你最少经过多少次的变换能够得到还原成”12345678“。

首先这个问题我们用广度优先搜索来做，广度优先搜索就是每次搜索一层，没找到就继续搜索下一层，对于我们这一题呢，就是每次搜索完这一层发现没有匹配的，就把变换次数加一，如果发现匹配的数组就结束循环返回该次数。

我们先定义这三种变换函数。

第一种就是把 ”12345678“经过Rotation Exchange之后变成”87654321“

def RX(rectangle):
    return rectangle[::-1]

第二中 ”12345678“经过 right circular shift变成”41236785“

def RCS(rectangle):
    result = ""
    return rectangle[3] + rectangle[0:3] + rectangle[5:8] + rectangle[4]

第三种 ”12345678“经过middle clockwise rotation变成 ”17245368“

def MCR(rectangle):
    return rectangle[0] + rectangle[6] + rectangle[1] + rectangle[3] + rectangle[4] +rectangle[2] + rectangle[5] + rectangle[7]

接下来我们写个函数，它可以调用这三种变换，rectangle这个参数肯定需要的，然后还要知道我们需要调用哪一个函数，我们假设给这三个变换命名为，0， 1， 2对应着 RX， RCX 和 MCR这三个函数。

def orientation_change(rectangle, num):
    if num == 0:
        return RX(rectangle)
    elif num == 1:
        return RCS(rectangle)
    else:
        return MCR(rectangle)

最后我们要写最重要的 BFS 他有两个参数，一个是打乱之后的数组，还有一个是我们希望变换后得到的数组。

def BFS(rectangle, result):
    queue = deque()
    queue.append(rectangle)
    seen = set()
    seen.add(rectangle)
    queue_level = deque()
    queue_level.append(0)
    while queue:
        node = queue.popleft()
        level = queue_level.popleft()
        if node == result:
            return level
        for i in range(3):
            res = orientation_change(i, node)
            if res not in seen:
                queue.append(res)
                queue_level.append(level + 1)
BFS("32415786", "12345678")

秒客网

一个BFS应用的实例

相关文章