python小练习（075）：A*算法求解转珠游戏MaxComb的最优路径

jerryxjr1220

其实，本季的python小练习到上一节应该算已经全部结束了，但是既然讲了深度优先搜索和广度优先搜索，那么就不得不提A*算法，它结合了深度优先搜索和广度优先搜索的优点，它是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。

该算法综合了BFS(Breadth First Search)和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（基于评估函数）。
在此算法中，如果以 g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么 A*算法的估算函数为：
f(n) = g(n)+h(n)
这个公式遵循以下特性：
如果g(n)为0，即只计算任意顶点n到目标的评估函数h(n)，而不计算起点到顶点n的距离，则算法转化为BFS(Breadth First Search),此时使用的是贪心策略，速度最快，但可能得不出最优解；
如果h(n)不为0，则一定可以求出最优解，而且h(n)越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
如果h(n)为0，即只需求出起点到任意顶点n的最短路径g(n)，而不计算任何评估函数h(n)，则转化为单源最短路径问题，即Dijkstra算法，此时需要计算最多的定点；

我想了一下，既然是python小练习没有习题总归不好，那还是放一道练习题说明一下A*算法好了。

不知道有鱼油玩过类似"神魔之塔"之类的转珠游戏，就是连续交换相邻的珠子，使横排或者竖排有3个或以上同色珠子，即可消除，连续消除多组就会产生Max Comb。
类似这样的:

如果我们把不同颜色的珠子，用不同的数字表示的话（心为0，红为1，绿为2，蓝为3，黄为4，紫为5），那么上图的排列就可以写成一个二维数组：
“452102，304555，500452，450415，102112”。然后就可以解题啦！

我们先来看程序的输出：
==================================================
original puzzle:
4 5 2 1 0 2
3 0 4 5 5 5
5 0 0 4 5 2
4 5 0 4 1 5
1 0 2 1 1 2
Find way:  [[4, 2], [3, 2], [3, 1], [4, 1], [4, 2], [4, 3], [4, 4], [3, 4], [3, 5], [2, 5]]
solution:
4 5 2 1 0 2
3 0 4 5 5 5
5 0 0 4 5 2
4 0 5 4 5 2
1 0 1 1 1 2
Max Comb: 5
Optimization Movement:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 10
0 3 2 0 8 9
0 4 5 6 7 0
==================================================
注：由于第一个个（4，2）被后一个（4，2）覆盖了，所以在Optimization Movement里面没有显示“1”，其实“1”与“5”的位置重合了。
按照上述的顺序移动就可以在不考虑“天降”的情况下，完成至少5 Combo 。如果算上后期天降，每轮7 Combo不是梦

下面就让我们详细分析源代码：

游客，如果您要查看本帖隐藏内容请回复

所以，可以看到A*算法是同时结合了深度优先搜索和广度优先搜索的一种搜索算法，可以利用2种算法的优点，既快又准地找到最优路径。

感谢关注python小练习，本季完！

新手·ing

虽然看不懂，但是还是值得学习的，谢谢

jerryxjr1220

想了一下，python小练习还是得要放上练习题才好
作为本季小练习的结尾篇！

qidian_zl

具体代码是什么呢？

Abner_jue

前排插眼  mark

yaha888

学习学习

JAY饭

这个二维列表描述和图不符

jerryxjr1220

JAY饭 发表于 2018-3-8 14:04
这个二维列表描述和图不符

嗯，可能图帖错了。不过意思是一样的，数字只是一个代号，解法不变的。

JAY饭

写到一半，总觉得不对劲，然后查了一下这个游戏，才知道这个和消消乐不一样。不知道怎么操作了，还是继续写消消乐吧

JAY饭

洗了个消消乐的最优决策，太乱了，还是不写注释了。

1. 
   
2. class joy():
   
3. 
   
4.     def __init__(self,lst):
   
5.         self.fac = lst
   
6.         self.itm = []
   
7.         self.sav = {3:[]}
   
8.         self.step = [(0,1),(1,0),(-1,0),(0,-1)]
   
9.         self.com = []
   
10.         self.right = {0:[]}
    
11.         
    
12.     def check_1(self):
    
13.         for line in range(5):
    
14.             sam = self.fac[line][0]
    
15.             cot = 1
    
16.             self.sav[3] = [(line,0)]
    
17.             for each in range(1,6):
    
18.                 sam,cot = self.condition(sam,cot,line,each,sign=False)
    
19. 
    
20.     def check_2(self):
    
21.         for ver in range(6):
    
22.             sam = self.fac[0][ver]
    
23.             cot = 1
    
24.             self.sav[3] = [(0,ver)]
    
25.             for each in range(1,5):
    
26.                 sam,cot = self.condition(sam,cot,each,ver,sign=True)
    
27.                
    
28.     def condition(self,sam,cot,line,each,sign= False):
    
29.         if self.fac[line][each] == sam and sam != 0:
    
30.             cot += 1
    
31.             self.sav[3].append((line,each))
    
32.             if not sign:
    
33.                 if each == 5 and cot >= 3:
    
34.                     temp = self.sav[3][:]
    
35.                     self.itm.append(temp)
    
36.             else:
    
37.                 if line == 4 and cot >=3:
    
38.                     temp = self.sav[3][:]
    
39.                     self.itm.append(temp)
    
40.         else:
    
41.             if cot >= 3:
    
42.                 temp = self.sav[3][:]
    
43.                 self.itm.append(temp)
    
44.             sam = self.fac[line][each]
    
45.             cot = 1
    
46.             self.sav[3] = [(line,each)]
    
47.         return sam,cot
    
48. 
    
49.     def sove(self):
    
50.         for line in self.itm:
    
51.             for L in line:
    
52.                 self.fac[L[0]][L[1]] = 0
    
53.         for i in range(5):
    
54.             for j in range(6):
    
55.                 if not self.fac[i][j] and i > 0:
    
56.                     t = i
    
57.                     while t:
    
58.                         self.fac[t][j] = self.fac[t-1][j]
    
59.                         self.fac[t-1][j] = 0
    
60.                         t -= 1
    
61.                         
    
62.     def show(self):
    
63.         for each in self.fac:
    
64.             print('  ',end='')
    
65.             for i in each:
    
66.                 print(i,end=' ')
    
67.             print('')
    
68. 
    
69.     def move(self):
    
70.         self.right = {}
    
71.         for i in range(5):
    
72.             for j in range(6):
    
73.                 self.comb(i,j)
    
74. 
    
75.     def comb(self,a,b):
    
76.         for i in self.step:
    
77.             j = a + i[0]
    
78.             k = b + i[1]
    
79.             if 0 <= j < 5 and 0 <= k < 6:
    
80.                 if self.fac[j][k] != self.fac[a][b]and [(j,k),(a,b)] not in self.com:
    
81.                     self.fac[a][b],self.fac[j][k] = self.fac[j][k],self.fac[a][b]
    
82.                     self.check_1()
    
83.                     self.check_2()
    
84.                     if len(self.itm) > 0:              
    
85.                         lst = [tuple(m) for m in self.fac]
    
86.                         self.combmax(a,b,j,k)
    
87.                         self.fac = [list(n) for n in lst]
    
88.                         self.com.append([(a,b),(j,k)])
    
89.                     self.fac[j][k],self.fac[a][b] = self.fac[a][b],self.fac[j][k]
    
90. 
    
91.     def combmax(self,a,b,j,k):
    
92.         count = 0
    
93.         item = []
    
94.         while True:
    
95.             self.sove()
    
96.             item += self.itm[:]            
    
97.             self.itm = []
    
98.             self.check_1()
    
99.             self.check_2()
    
100.             if len(self.itm) == 0:
     
101.                 break
     
102.         for i in item:
     
103.             if len(i) == 3: count += 1
     
104.             elif len(i) == 4: count += 2
     
105.             elif len(i) == 5: count += 3
     
106.             else: count += 4
     
107. 
     
108.         self.right[count] = [(a,b),(j,k)]
     
109. 
     
110.     def zuizhong(self,a,b,j,k):
     
111.         item = []
     
112.         while True:
     
113.             self.sove()
     
114.             self.show()
     
115.             print()
     
116.             item += self.itm[:]            
     
117.             self.itm = []
     
118.             self.check_1()
     
119.             self.check_2()
     
120.             if len(self.itm) == 0:
     
121.                 break
     
122.         
     
123. st = '''3 5 2 1 1 2
     
124. 3 2 6 5 1 5
     
125. 2 6 5 6 5 1
     
126. 4 2 1 5 6 5
     
127. 6 1 4 1 1 2'''
     
128. 
     
129. lst = [each.split(' ') for each in st.split('\n')]
     
130. lst = [[int(j) for j in i] for i in lst]
     
131. J = joy(lst)
     
132. J.show()
     
133. J.move()
     
134. print('产生最高comb数的交换路径是')
     
135. print(J.right[max(J.right)],'产生的comb数是%s'%max(J.right))
     
136. print('移动后的界面：')
     
137. [(a,b),(c,d)] = J.right[max(J.right)]
     
138. J.fac[a][b],J.fac[c][d] =J.fac[c][d],J.fac[a][b]
     
139. J.zuizhong(a,b,c,d)

复制代码

wenweno

dennis701007

看看代碼研究

LYZ1148779746

看看吧

mui

这个很强悍啊

qingquanwu

看看~

urnion

虽然看不懂，但是还是值得学习的，谢谢

f244968

学习学习

choukou

看看

a5151351509

學習