1229 : A*搜索

时间限制:1 Sec 内存限制:128 MiB
提交:211 答案正确:97

提交 状态 讨论区

题目描述

A*搜寻算法俗称A星算法。
这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。

A*改变它自己行为的能力基于启发式代价函数,启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中,你并不真
正需要得到最好的路径,仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么,或者运行游戏的机器有多快。
假设你的游戏有两种地形,平原和山地,在平原中的移动代价是1而在山地则是3。
A* is going to search three times as far along flat land as it does along mountainous land.
这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较,这并不比把3和1比较差。

It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up
up A*'s search by decreasing the amount it searches for paths around mountains―just tell A* that the movement cost on mountains is 2 instead of 3.
Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.

速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体(units)的数量、物体的重要性、组(group)的大小、难度或者其
他任何因素来进行动态的选择。取得动态的折衷的一个方法是,建立一个启发式函数用于假定通过一个网格空间的最小代价是1,然后建立一个代价函数(cost function)用
于测量
(scales):g’(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0,则改进后的代价函数的值总是1。这种情况下,地形代价被完全忽略,A*工作变成简单地判断一个网格可否通过。如果alpha是1,则最初的代价函数将起作用,
然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。你也可以考虑对启发式函数的返回值做选择:绝对最小代价或者期望最小代价。例如,如果你的地图大部
分地形是代价为2的草地,其它一些地方是代价为1的道路,那么你可以考虑让启发式函数不考虑道路,而只返回2*距离。速度和精确度之间的选择并不是全局的。在地图上的
某些区域,精确度是重要的,你可以基于此进行动态选择。例如,假设我们可能在某点停止重新计算路径或者改变方向,则在接近当前位置的地方,选择一条好的路径则是更重
要的,因此为何要对后续路径的精确度感到厌烦?或者,对于在地图上的一个安全区域,最短路径也许并不十分重要,但是当从一个敌人的村庄逃跑时,安全和速度是最重要的。
在游戏中,路径潜在地花费了许多存储空间,特别是当路径很长并且有很多物体需要寻路时。路径压缩,导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间
需求。

Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths
calculated beforehand between specially marked places on the map.

如果路径仍然用了许多存储空间,可以限制路径长度,这就回到了经典的时间-空间折衷法:为了节省空间,信息可以被丢弃,稍后才重新计算它。

如果你看到这里,好了,这道题你就过了,真的,其实这道题和A星半毛钱关系都没有-_-#,写那么长的目的只有两个,第一,告诉你要敢于读题,不管这题目描述有多长;第二,
A星算法真的很有用,这里小打下广告,多年以后,如果你做游戏的话,你会感谢我的

输入

这道题是多组测试数据,每组第一行一个整数N,然后是一个N*N的矩阵,由*或者@组成,

输出


每组输出占一行,输出*的个数和@的个数的差就好。

样例输入

复制
5
*****
@**@@
**@**
@*@**
*****
4
@***
****
****
***@

样例输出

复制
13
12

提示


			

来源

2013.5校赛