本文链接
文章目录https://blog.csdn.net/weixin_46517149/article/details/124228180
- 一、背景
- 二、水排序谜题
- 三、问题构建
- 四、问题求解
- 1.BFS宽度优先搜索策略
- 2.BFS和剪枝
- 3. 启发式搜索
- A*搜索
- 从松弛问题出发设计一个启发式函数
- 启发式函数代码
- A*搜索代码
- 测试
- 4. 为解决第98关的问题改进算法
- 分析原因
- 改进方法
- 测试结果
- 五、总结
一、背景
在QQ小程序上偶然看的水排序谜题，打到了88关，打不过去了。就想着用算法解决问题。
二、水排序谜题
基本规则是：
每种颜色有4份水
每个杯子容量是4份，
任何水都不能倒入满杯子，
任何水都可以倒入空杯，
只有同色水可以倒入非满非空杯，
相邻的几份同色水是一块，
一次要将一块同色水一起倒过去，除非目标杯子已经满了
最后每一种颜色的4份水在同一个杯子里，即每个杯子是空的或有4份相同颜色的水
三、问题构建玩游戏的过程，就是一个寻找游戏问题解的过程。这个游戏就是一个典型的可以通过搜索求解的问题。
通过搜索进行问题求解，首先要定义问题的初始状态和状态空间、转移模型（每个状态可以采取的行动及到达的状态）、目标、路径消耗（这个问题中，倒一次路径消耗就是1）。
import copy
class Puzzle(object):
def __init__(self,cup_num=0,capacity=0) -> None:
self.cup_num = cup_num #杯子数
self.capacity = capacity #杯子容量
self.empty_cup = 0
self.state = None
def create(self):
# 输入状态
self.cup_num = int(input("杯子数:"))
self.capacity = int(input("杯子容量:"))
cup_num = self.cup_num
capacity = self.capacity
self.state = []
for i in range(cup_num):
# 空格分隔颜色
# 空行即为空杯
water = input("第%d个杯子(从下到上): "%i).split()[:capacity]
if len(water) == 0:
self.empty_cup += 1
self.state.append(water)
return self.state
def readfile(self,file):
# 从文件读取状态
with open(file,'r') as f:
self.cup_num = int(f.readline())
self.capacity = int(f.readline())
self.state = []
for i in range(self.cup_num):
water = f.readline().split()[:self.capacity]
if len(water) == 0:
self.empty_cup += 1
self.state.append(water)
return self.state
def get_successors(self):
# 获取所有的后继状态及动作
suc = []
for i in range(self.cup_num):
for j in range(self.cup_num):
if self.isAction((j,i)):
suc.append(((j,i),self.move((j,i))))
return suc
def isAction(self,act:tuple,state=None):
# 判断是否是一个合法的动作
# from j to i
j,i = act
if state == None:
state = self.state
return i!=j and len(state[j])>0 and len(state[i])<self.capacity and (len(state[i])==0 or state[j][-1]==state[i][-1])
# 两个不同的杯子 且 原杯子非空 且 目标杯子未满 且 （目标杯子为空 或 顶部颜色相同）
def move(self,act:tuple):
# 对当前状态实行动作并产生一个新的状态
j,i = act
state = copy.deepcopy(self.state)
while self.isAction(act,state):
state[i].append(state[j].pop())
# 一次移动一块水而不是一份
new_puzzle = Puzzle(self.cup_num,self.capacity)
new_puzzle.empty_cup = self.empty_cup
new_puzzle.state = state
return new_puzzle
def isRight(self)->bool:
# 是目标状态
if self.state is None:
return False
for i in range(self.cup_num):
if len(self.state[i]) != 0 and len(self.state[i]) != self.capacity:
return False
elif len(self.state[i]) == self.capacity:
for j in range(1,self.capacity):
if self.state[i][j] != self.state[i][0]:
return False
return True
def print(self,cup_width=6, cup_interval=3):
# 打印当前状态
if self.state is None:
print(None)
return None
width = cup_width
interval = cup_interval
space = " "*interval
a = ""
for i in range(self.cup_num):
a += ("#%d"%i).center(width+2)+space
print(a)
print()
for j in range(self.capacity-1,-1,-1):
a = ""
for i in range(self.cup_num):
if len(self.state[i]) > j:
color = self.state[i][j]
else:
color = "."
a += "|"+("%s"%color).center(width)+"|"+space
print(a)
a = ""
for i in range(self.cup_num):
a += "\"+"_".center(width,"_")+"/"+space
print(a)
return None
输入一个简单的问题测试一下：
p.txt
4
4
1 3 2 2
2 3 1 3
2 1 1 3
test = Puzzle()
# test.create()
test.readfile("p.txt")
print(test.state)
test.print()
print(test.get_successors())
输出:
.代表空
[[], ['1', '3', '2', '2'], ['2', '3', '1', '3'], ['2', '1', '1', '3']]
#0 #1 #2 #3
| . | | 2 | | 3 | | 3 |
| . | | 2 | | 1 | | 1 |
| . | | 3 | | 3 | | 1 |
| . | | 1 | | 2 | | 2 |
\______/ \______/ \______/ \______/
[((1, 0), <__main__.Puzzle object at 0x000001FC01DE8820>), ((2, 0), <__main__.Puzzle object at 0x000001FC01EE7310>), ((3, 0), <__main__.Puzzle object at 0x000001FC01F19D90>)]
为了方便测试，写一个简单的问题生成器：
puzzle_generator.py
import random
cup_num = int(input("杯子数:"))
capacity = int(input("杯子容量:"))
empty_cup = int(input("空杯数:"))
state = []
for i in range(cup_num):
if i < empty_cup:
state.append([])
else:
state.append([i]*capacity)
path = []
N = 100
for step in range(N):
i = random.randint(0,cup_num-1)
while len(state[i])==0:
i = random.randint(0,cup_num-1)
j = random.randint(0,cup_num-1)
while j == i or len(state[j]) == capacity:
j = random.randint(0,cup_num-1)
state[j].append(state[i].pop())
path.append((j,i))
for i in range(empty_cup):
while len(state[i])!=0:
j = random.randint(empty_cup,cup_num-1)
while j == i or len(state[j]) == capacity:
j = random.randint(empty_cup,cup_num-1)
state[j].append(state[i].pop())
path.append((j,i))
print(state)
with open("p.txt",'w') as f:
f.writelines([str(cup_num)+'\n',str(capacity)+'\n'])
sss = []
for cup in state:
a = ""
for w in cup:
a += str(w)+" "
sss.append(a+'\n')
f.writelines(sss)
我首先想到的求解方式就是直接暴力搜索，因为简单好写，虽然不优雅，但能求解出来就行。
为什么不使用DFS深度优先搜索呢？因为我考虑到其中会有一些循环的动作，比如A倒B，B又倒A，导致深度不断加深找不到解，并且DFS不能保证最优。
BFS代码如下：
def bfs(puzzle:Puzzle,attemp=100000):
ttt = 0
q = []
q.append(([],puzzle))
while len(q)>0:
path,pz = q.pop(0)
if pz.isRight():
print("%d states searched"%ttt)
return path,pz
for succ in pz.get_successors():
act,suc_pz = succ
q.append((path.copy()+[act],suc_pz))
ttt += 1
if (ttt>attemp):
print("超出最大次数")
return None
print("无解")
return None
测试：
test = Puzzle()
# test.create()
test.readfile("p.txt")
test.print()
a = bfs(test)
if a == None:
print("None!")
else:
print("%d steps"%len(a[0]))
print(a[0])
a[1].print()
输出：
#0 #1 #2 #3
| . | | 2 | | 3 | | 3 |
| . | | 2 | | 1 | | 1 |
| . | | 3 | | 3 | | 1 |
| . | | 1 | | 2 | | 2 |
\______/ \______/ \______/ \______/
98 states searched
8 steps
[(2, 0), (3, 0), (2, 3), (2, 0), (1, 2), (1, 0), (3, 1), (3, 2)]
#0 #1 #2 #3
| 3 | | 1 | | 2 | | . |
| 3 | | 1 | | 2 | | . |
| 3 | | 1 | | 2 | | . |
| 3 | | 1 | | 2 | | . |
\______/ \______/ \______/ \______/
很快啊，一下就出结果了！
这问题简简单单！
但是，杯子数一多，就变慢了
4个杯子两个空杯，要搜索2080个状态
5个杯子两个空杯，要搜索85219个状态
6个杯子两个空杯，要搜索大于1000000个状态
这怎么行！
直接BFS不行，那就剪一剪枝
在搜索中很可能会遇到A倒B，B倒A的情况，这种情况对于求解没有任何帮助，直接剪掉
比如：
#A #B
| . | | 3 |
| 3 | | 3 |
| 2 | | 4 |
| 2 | | 2 |
\______/ \______/
这种情况下，B->A是一个合法动作，但是倒过去后，A->B是一个合法动作，可能就会出现来回倒的情况
代码如下：
def bfs_prune(puzzle:Puzzle,attemp=1000000):
ttt = 0
q = []
q.append(([],puzzle))
while len(q)>0:
path,pz = q.pop(0)
if pz.isRight():
print("%d states searched"%ttt)
return path,pz
if len(path)<2 or (len(path)>=2 and not (path[-1][1] == path[-2][0] and path[-1][0] == path[-2][1])):
# 剪枝
for succ in pz.get_successors():
act,suc_pz = succ
q.append((path.copy()+[act],suc_pz))
ttt += 1
if (ttt>attemp):
print("超出最大次数")
return None
print("无解")
return None
测试确实有效果：
相同的问题
4个杯子两个空杯，要搜索1599个状态
5个杯子两个空杯，要搜索60440个状态
6个杯子两个空杯，要搜索大于1000000个状态
还是不行
看来无信息的搜索策略是不行的，必须使用启发式搜索
对于启发式搜索，参考《人工智能 一种现代的方法 第3版》
启发式函数就是对于从当前状态到目标状态的代价的最低估计，并且估计代价要小于实际代价（可采纳的）
从松弛问题出发设计启发式常用的方法。
目前游戏问题有多种约束条件，可以去掉几种条件得到松弛问题。
我去掉空杯是有限的这个条件，假设空杯无限多。
那么，会得到什么样的代价估计呢？
#0 #1 #2 #3 #4 #5 #6 #7 #8
| . | | . | | 4 | | 1 | | . | | . | | . | | . | | . |
| . | | 3 | | 3 | | 2 | | . | | . | | . | | . | | . |
| 2 | | 2 | | 2 | | 4 | | 3 | | . | | 5 | | . | | . |
| 1 | | 1 | | 1 | | 4 | | 3 | | 4 | | 5 | | 5 | | 5 |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
要装满一个杯子，首先要清除上部的不同颜色。
一个杯子中有多种颜色
1、杯子上部
对于#0杯子，我们很显然要得到一个装满1的杯子。那么，首先要清除上部，把2 倒出去，需要至少1步。
对于#1杯子，首先要把2 3倒出去，需要2步。
同样的，#2需要3步，#3需要2步
要得到一个装满1的杯子，我们可以在清除其他杯子上部时，把1倒过来就可以了
2、杯子底部
#0 #1 #2 杯子底部都是1，我们不能对每个杯子都期望得到一个装满1的杯子，三个杯子要有两个杯子的1倒入另外一个杯子中，至少需要2步
一个杯子中只有一种颜色
这种杯子只有底部，没有上部
杯子未满的情况下：
对于#4杯子，其他杯子底部没有3，只需让其他杯子移开3的时候放到#4杯子（而不是无限多的空杯）里就行了，不需要消耗步骤
对于#5杯子，#3杯子底部有4，至少需要1步把它们放到一个杯子里（这里的代价计算与一个杯子中有多种颜色的杯子底部计算有重复，需要注意不要重复计算）
对于#6 #7 #8杯子，至少需要2步把5放到一个杯子里
杯子已满：
不需要 *** 作，代价是0
但是，我在实际测试中发现，将满杯子的代价计算为-1会大大减少搜索的状态数量。
class Puzzle(object):
...
def A_star_cost(self)->int:
#smaller is better
# 可采纳并且一致的启发式
c = 0
bottom = {}
for cup in self.state:
if len(cup)==0:
continue
bottom[cup[0]] = bottom.get(cup[0],-1) + 1
w0 = cup[0]
all_same = 0
for i in range(1,len(cup)):
if cup[i] != w0:
w0 = cup[i]
c += 1
all_same = 1
if all_same == 0 and len(cup) == self.capacity:
c -= 1
if all_same == 0 and len(cup) < self.capacity and bottom[cup[0]]>=1:
c += 1
bottom[cup[0]] -= 1 #不要重复计算
c += sum(bottom.values())
return c
from queue import PriorityQueue
def A_star(puzzle:Puzzle,attemp=100000):
ttt = 0
q = PriorityQueue()
q.put((puzzle.A_star_cost(),[],puzzle))
while not q.empty():
score,path,pz = q.get()
if pz.isRight():
print("%d states searched"%ttt)
return path,pz
if len(path)<2 or (len(path)>=2 and not (path[-1][1] == path[-2][0] and path[-1][0] == path[-2][1])):
for succ in pz.get_successors():
act,suc_pz = succ
q.put((len(path)+suc_pz.A_star_cost(),path.copy()+[act],suc_pz))
ttt += 1
if (ttt>attemp):
print("超出最大次数")
return None
print("无解")
return None
89.txt
11
4
g r r b0
po g0 br po
br y y g0
g o o g0
g y po br
b0 po b o
b b0 br r
b y o b
b0 g r g0
test = Puzzle()
# test.create()
test.readfile("89.txt")
test.print()
a = A_star(test)
if a == None:
print("None!")
else:
print("%d steps"%len(a[0]))
print(a[0])
a[1].print()
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10
| . | | . | | b0 | | po | | g0 | | g0 | | br | | o | | r | | b | | g0 |
| . | | . | | r | | br | | y | | o | | po | | b | | br | | o | | r |
| . | | . | | r | | g0 | | y | | o | | y | | po | | b0 | | y | | g |
| . | | . | | g | | po | | br | | g | | g | | b0 | | b | | b | | b0 |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
33 states searched
29 steps
[(4, 0), (4, 1), (5, 0), (6, 4), (3, 6), (3, 4), (3, 0), (10, 0), (6, 3), (7, 5), (8, 10), (8, 4), (1, 6), (2, 8), (2, 1), (10, 1), (2, 10), (5, 2), (5, 10),
(6, 5), (9, 7), (9, 2), (9, 5), (7, 9), (7, 3), (7, 8), (10, 6), (8, 10), (8, 9)]
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10
| g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 |
| g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 |
| g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 |
| g0 | | r | | o | | po | | br | | y | | g | | . | | . | | b | | b0 |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
97.txt
11
4
po o g y
g0 o po g
g b y o
po po br r
b g b0 o
b0 y br b
br y br r
g0 b0 b0 g0
b g0 r r
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10
| . | | . | | y | | g | | o | | r | | o | | b | | r | | g0 | | r |
| . | | . | | g | | po | | y | | br | | b0 | | br | | br | | b0 | | r |
| . | | . | | o | | o | | b | | po | | g | | y | | y | | b0 | | g0 |
| . | | . | | po | | g0 | | g | | po | | b | | b0 | | br | | g0 | | b |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
52 states searched
27 steps
[(2, 0), (3, 2), (5, 1), (8, 1), (8, 5), (8, 0), (10, 1), (5, 8), (3, 5), (4, 3), (4, 0), (6, 3), (7, 4), (7, 8), (7, 0), (6, 7), (2, 6), (9, 10), (9, 7), (9, 10), (2, 9), (2, 5), (3, 9), (10, 3), (4, 10), (6, 4), (6, 10)]
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10
| y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b |
| y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b |
| y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b |
| y | | r | | . | | g0 | | g | | po | | . | | b0 | | br | | o | | b |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
效果非常好，可以快速的解决问题
4. 为解决第98关的问题改进算法启发式搜索一直到97关都很顺利，但是到98关就卡住了，搜不到解了。
经过我坚持不懈的人工探索，发现正确解法的第一步应当是把棕色放到空杯中。我给搜索算法一个提示，让它搜索已经将棕色放到空杯中的状态的解，很快就找到了。看来是第一步没有找对。
经过分析，我认为没有找到解的原因如下：
1、给出的问题初始状态一定会有两个空杯，其余杯子是满的，所以，第一步一定是将其他杯子顶部的某种颜色倒入一个空杯中。而我的算法没有考虑这点，只会一步一步的搜索，比如，先尝试将一份水倒入空杯，然后尝试将另一份水倒入另一个空杯，这显然大大增加了搜索的空间。
2、第一步的 *** 作很关键，开始的前几步常常包含了很大的搜索空间，第一步走错又不能快速的走出来，就会很难找到问题的解。
3、设计的启发式函数对第一步的引导效果不好。由于我没有考虑第一步一定是将一种颜色全都倒到一个空杯中，算法要将所有棕色都放到一个空杯里需要三步，搜索树需要扩展三层，这很显然对搜索是不利的。
我定义第一步的 *** 作一定是将一种颜色全部放入一个空杯中，来减少搜索空间。
修改代码
class Puzzle(object):
def __init__(self,cup_num=0,capacity=0) -> None:
...
self.state = None
+++ self.first = False
def create(self):
...
+++ self.first = True
...
def readfile(self,file):
+++ self.first = True
...
def get_successors(self):
+++ if self.first:
+++ return self.get_first_step()
...
...
++++++
def selfmove(self,act:tuple)->bool:
j,i = act
state = self.state
flag = False
while self.isAction(act,state):
state[i].append(state[j].pop())
flag = True
return flag
def selfmovePath(self,path:list)->bool:
for act in path:
if not self.selfmove(act):
return False
return True
def get_first_step(self):
if self.empty_cup==0:
return None
top = {}
empty_cup = -1
for i,cup in enumerate(self.state):
if len(cup) == 0:
empty_cup = i
continue
top[cup[-1]] = top.get(cup[-1],[]) + [i]
if empty_cup == -1:
return None
res = []
for c in top.values():
puzzle0 = self.move((c[0],empty_cup))
act = [(c[0],empty_cup)]
for j in range(1,len(c)):
puzzle0.selfmove((c[j],empty_cup))
act.append((c[j],empty_cup))
res.append((act,puzzle0))
return res
++++++
98.txt
14
4
gg rr po ge
ge g0 po b0
pi g0 bb oo
gg bb rr br
pi yy bb b0
br g0 rr oo
rr oo zz gg
g0 pi ge br
yy zz b0 yy
pi zz zz br
b0 po bb ge
oo po gg yy
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13
| . | | . | | ge | | b0 | | oo | | br | | b0 | | oo | | gg | | br | | yy | | br | | ge | | yy |
| . | | . | | po | | po | | bb | | rr | | bb | | rr | | zz | | ge | | b0 | | zz | | bb | | gg |
| . | | . | | rr | | g0 | | g0 | | bb | | yy | | g0 | | oo | | pi | | zz | | zz | | po | | po |
| . | | . | | gg | | ge | | pi | | gg | | pi | | br | | rr | | g0 | | yy | | pi | | b0 | | oo |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
6032 states searched
38 steps
[[(5, 1), (9, 1), (11, 1)], (2, 9), (3, 0), (2, 3), (5, 2), (6, 0), (6, 5), (10, 6), (10, 0), (13, 6), (8, 13), (8, 10), (4, 8), (4, 5), (7, 8), (7, 2),
(7, 4), (1, 7), (10, 1), (6, 10), (11, 1), (6, 11), (3, 6), (3, 4), (9, 3), (12, 3), (9, 11), (4, 9), (4, 11), (5, 4), (12, 4), (12, 6), (0, 12), (13, 5),
(13, 6), (8, 13), (2, 8), (2, 5)]
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13
| . | | zz | | . | | ge | | bb | | gg | | po | | br | | rr | | g0 | | yy | | pi | | b0 | | oo |
| . | | zz | | . | | ge | | bb | | gg | | po | | br | | rr | | g0 | | yy | | pi | | b0 | | oo |
| . | | zz | | . | | ge | | bb | | gg | | po | | br | | rr | | g0 | | yy | | pi | | b0 | | oo |
| . | | zz | | . | | ge | | bb | | gg | | po | | br | | rr | | g0 | | yy | | pi | | b0 | | oo |
\______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/ \______/
五、总结
本文设计了一个用于解决水排序谜题的启发式函数，并实现了A*搜索算法，达到了非常好的效果。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）