|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 jerryxjr1220 于 2017-2-10 21:17 编辑
不知道有鱼油玩过类似"神魔之塔"之类的转珠游戏，就是连续交换相邻的珠子，使横排或者竖排有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*算法结合了深度优先搜索和广度优先搜索的优点，它是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的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算法，此时需要计算最多的定点；
所以，可以看到A*算法是同时结合了深度优先搜索和广度优先搜索的一种搜索算法，可以利用2种算法的优点，既快又准地找到最优路径。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2017-2-10 21:06:32
置顶卡
千斤顶
显身卡
发表于 2018-2-10 21:57:09
