鱼C论坛

 找回密码
 立即注册
查看: 10717|回复: 32

[技术交流] python小练习(075):A*算法求解转珠游戏MaxComb的最优路径

[复制链接]
发表于 2017-2-10 09:28:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-3-24 00:11 编辑

其实,本季的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。
类似这样的:
tmpr3rkod.BMP
如果我们把不同颜色的珠子,用不同的数字表示的话(心为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小练习,本季完!

评分

参与人数 1荣誉 +10 鱼币 +10 贡献 +6 收起 理由
v.ki + 10 + 10 + 6

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-10 15:22:51 | 显示全部楼层
虽然看不懂,但是还是值得学习的,谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-2-10 20:42:44 | 显示全部楼层
想了一下,python小练习还是得要放上练习题才好
作为本季小练习的结尾篇!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-21 14:14:34 | 显示全部楼层
具体代码是什么呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2017-6-26 09:50:08 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-10 22:01:46 | 显示全部楼层
前排插眼  mark
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-11 00:01:13 From FishC Mobile | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-8 14:04:37 | 显示全部楼层
这个二维列表描述和图不符
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-3-8 15:41:01 | 显示全部楼层
JAY饭 发表于 2018-3-8 14:04
这个二维列表描述和图不符

嗯,可能图帖错了。不过意思是一样的,数字只是一个代号,解法不变的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-8 18:44:35 | 显示全部楼层
写到一半,总觉得不对劲,然后查了一下这个游戏,才知道这个和消消乐不一样。不知道怎么操作了,还是继续写消消乐吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-9 13:43:30 | 显示全部楼层
洗了个消消乐的最优决策,太乱了,还是不写注释了。
class joy():

    def __init__(self,lst):
        self.fac = lst
        self.itm = []
        self.sav = {3:[]}
        self.step = [(0,1),(1,0),(-1,0),(0,-1)]
        self.com = []
        self.right = {0:[]}
        
    def check_1(self):
        for line in range(5):
            sam = self.fac[line][0]
            cot = 1
            self.sav[3] = [(line,0)]
            for each in range(1,6):
                sam,cot = self.condition(sam,cot,line,each,sign=False)

    def check_2(self):
        for ver in range(6):
            sam = self.fac[0][ver]
            cot = 1
            self.sav[3] = [(0,ver)]
            for each in range(1,5):
                sam,cot = self.condition(sam,cot,each,ver,sign=True)
                
    def condition(self,sam,cot,line,each,sign= False):
        if self.fac[line][each] == sam and sam != 0:
            cot += 1
            self.sav[3].append((line,each))
            if not sign:
                if each == 5 and cot >= 3:
                    temp = self.sav[3][:]
                    self.itm.append(temp)
            else:
                if line == 4 and cot >=3:
                    temp = self.sav[3][:]
                    self.itm.append(temp)
        else:
            if cot >= 3:
                temp = self.sav[3][:]
                self.itm.append(temp)
            sam = self.fac[line][each]
            cot = 1
            self.sav[3] = [(line,each)]
        return sam,cot

    def sove(self):
        for line in self.itm:
            for L in line:
                self.fac[L[0]][L[1]] = 0
        for i in range(5):
            for j in range(6):
                if not self.fac[i][j] and i > 0:
                    t = i
                    while t: 
                        self.fac[t][j] = self.fac[t-1][j]
                        self.fac[t-1][j] = 0
                        t -= 1
                        
    def show(self):
        for each in self.fac:
            print('  ',end='')
            for i in each:
                print(i,end=' ')
            print('')

    def move(self):
        self.right = {}
        for i in range(5):
            for j in range(6):
                self.comb(i,j)

    def comb(self,a,b):
        for i in self.step:
            j = a + i[0]
            k = b + i[1]
            if 0 <= j < 5 and 0 <= k < 6:
                if self.fac[j][k] != self.fac[a][b]and [(j,k),(a,b)] not in self.com:
                    self.fac[a][b],self.fac[j][k] = self.fac[j][k],self.fac[a][b]
                    self.check_1()
                    self.check_2()
                    if len(self.itm) > 0:              
                        lst = [tuple(m) for m in self.fac]
                        self.combmax(a,b,j,k)
                        self.fac = [list(n) for n in lst]
                        self.com.append([(a,b),(j,k)])
                    self.fac[j][k],self.fac[a][b] = self.fac[a][b],self.fac[j][k]

    def combmax(self,a,b,j,k):
        count = 0
        item = []
        while True:
            self.sove()
            item += self.itm[:]            
            self.itm = []
            self.check_1()
            self.check_2()
            if len(self.itm) == 0:
                break
        for i in item:
            if len(i) == 3: count += 1
            elif len(i) == 4: count += 2
            elif len(i) == 5: count += 3
            else: count += 4

        self.right[count] = [(a,b),(j,k)]

    def zuizhong(self,a,b,j,k):
        item = []
        while True:
            self.sove()
            self.show()
            print()
            item += self.itm[:]            
            self.itm = []
            self.check_1()
            self.check_2()
            if len(self.itm) == 0:
                break
        
st = '''3 5 2 1 1 2
3 2 6 5 1 5
2 6 5 6 5 1
4 2 1 5 6 5
6 1 4 1 1 2'''

lst = [each.split(' ') for each in st.split('\n')] 
lst = [[int(j) for j in i] for i in lst]
J = joy(lst)
J.show()
J.move()
print('产生最高comb数的交换路径是')
print(J.right[max(J.right)],'产生的comb数是%s'%max(J.right))
print('移动后的界面:')
[(a,b),(c,d)] = J.right[max(J.right)]
J.fac[a][b],J.fac[c][d] =J.fac[c][d],J.fac[a][b]
J.zuizhong(a,b,c,d)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-17 15:43:51 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-4-24 13:06:33 | 显示全部楼层
看看代碼研究
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-18 11:27:02 | 显示全部楼层
看看吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-8-30 08:29:20 | 显示全部楼层
这个很强悍啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-1-18 11:55:22 | 显示全部楼层
看看~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-3-1 10:31:39 | 显示全部楼层
虽然看不懂,但是还是值得学习的,谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-6 09:33:46 | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-9 17:36:59 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-5-13 21:40:07 | 显示全部楼层
學習
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-25 10:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表