问题出处
我最初是在OSChina上看到这个问题的,有人在论坛上把这个问题提了出来,寻求算法来解决。最初的问题其实是一个Flash小游戏,简单来说,就是一共有6只青蛙,左右各3只,中间还有一个空格,我们的任务是经过有限步的跳跃,将左右青蛙的位置交换。交换的时候会有一些限制条件:
- 青蛙只能前进,不能后退
- 每次只能前进1格或2格
当时试玩的时候,玩了好几次才成功……我实在太笨了-.-.
用算法求解
当考虑用算法求解这个问题的时候,首先要将这个题目数字化,就是如何在程序中表达这个游戏过程。如果把注意力集中在青蛙身上,一共有6只青蛙,那就是说需要设置6个变量,并且需要时刻跟踪这6个变量的变化,这样的程序难度太大了,而且如果青蛙数目继续增加的话,程序就更不好处理了,这显然不是一个好方法。我们可以换个角度来看待这个问题,不需要盯着青蛙是如何运动的,只需要盯着当中那个空格是如何运动的。因为所有的格子总会比青蛙多一个,所以我们只需要关注格子的位置就可以了。
因为在每次的移动过程中,空格只有四种情况:往左移动2格、往左移动1格、往右移动2格、往右移动1格。因此我把整个青蛙序列作为一个状态,每一个状态都可以经由4条不同的路径转移到下一个状态(对应于4种移动方案),这样我就能把原问题转化为一个图搜索问题:从初始状态开始,找到一条达到目标状态的路径。
根据问题中的限制条件,空格只能和其左右2格以内的青蛙进行交换,并且空格往右移动的时候只能和原本在右边的青蛙交换,同样,往左移动的时候,只能和原本在左边的青蛙交换。因此我可以将整个青蛙序列用一个数组表示,原来在左侧的青蛙用-1表示,原来在右侧的青蛙用1表示,空格用0表示。同时,我用-2、-1、1、2分别表示空格往左移动2格,往左移动1格,往右移动1格,往右移动2格。注意,这里我使用了一个小技巧:空格能够往左(-1,-2)移动的条件是,左边要交换的位置上有一个原来在左侧(-1)的青蛙,这样的话,我只需要判断往左的代表值和青蛙的代表值是否同号,我就能判断能否进行交换了。
代码
#!python
#深度遍历,其中order参数是用来记录路径的
def deepexplore(table,order):
index = table.index(0)
#判断是否是终点状态
if index == len(table) // 2 and sum(table[:index]) == len(table)//2:
print('Swap Complete!')
return True
#顺序尝试四条路径
for i in range(-2,3):
#判断是否越界,是否倒退
if i == 0 or index + i < 0 or index + i >= len(table) or table[index+i] * i <=0:
continue
else:
table[index+i],table[index] = table[index],table[index+i]
order.append(table[:])
if deepexplore(table,order) == True:
return True
order.pop(-1)
table[index+i],table[index] = table[index],table[index+i]
def widthexplore(table):
stack = []
stack.append((table[:],False))
while len(stack)!=0:
state = stack.pop(0)
index = state[0].index(0)
#判断是否是终点
if index == len(state[0]) // 2 and sum(state[0][:index]) == len(state[0])//2:
print('Swap Complete!')
break
for i in range(-2,3):
#判断是否越界,是否倒退
if i == 0 or index + i < 0 or index + i >= len(state[0]) or state[0][index+i] * i <=0:
continue
else:
newstate = (state[0][:],state)
newstate[0][index+i],newstate[0][index] = newstate[0][index],newstate[0][index+i]
stack.append(newstate)
#还原路径
order = []
while state[1] != False:
order.append(state[0])
state = state[1]
order.append(state[0])
order.reverse()
return order
def frogchess(n):
table = [-1] * n + [0] + [1] * n
order=[]
order.append(table[:])
deepexplore(table,order)
order.reverse()
for item in order:
print(item)
if __name__ == '__main__':
frogchess(4)
上述代码中,我用了两种方法进行搜索,分别是深度优先和广度优先,本来以为广度优先能够找到最少的移动序列,但是程序跑下来,广度优先除了更加耗时间以外,找到的路径和深度优先是一样的。
总结
本来想从数学角度来推导得到一个比较美观的公式的,可是数学功底不扎实,实在找不到什么数学原理,只能直接用程序来计算,上面的算法只是利用计算机的高速计算的特点从解空间中寻找答案。 一旦青蛙的数量有所提高,计算量就迅速增大,这样的解法就不再适合了(\(N>20\)),应该要从数学角度寻求更优的解法。
Comments
So what do you think? Did I miss something? Is any part unclear? Leave your comments below