a星算法计算

1. 如何基于cocos2dx3.x实现A星寻路算法

在学习本篇教程之前，如果你有cocos2d-x的开发经验，将会有所帮助。如果没有也没关系，因为你可以将这里讲解的例子迁移到其他的语言或者框架中。
找到到达你键盘的最短路径，开始吧！
Maze猫
首先介绍下我们将要在本篇教程中开发的简单游戏。
前往下载本篇教程的 工程代码 。编译运行工程，你将看到以下画面。

在这款游戏中，你扮演着一只小偷猫，在一个由危险的狗守护着的地牢里小心穿行。如果你试图穿过一只狗，他会把你吃掉 – 除非你可以用骨头去贿赂它！
所以在这款游戏中，你的任务是尝试以正确的顺序捡起骨头，然后 寻找路线 穿过狗逃离。
注意到猫只能水平或者垂直的移动（例如不能斜线移动），并且会从一个方块的中心点移动到另一个中心点。每个方块既可以是可通行的也可以是不可通行的。
尝试下这款游戏，看看你能否找到出路！建议你阅读代码以熟悉它的原理。这是一款相当普通的方块-地图式游戏，我们会在接下来的教程中修改它并使用上A星寻路算法。
Maze猫和A星概览
正如你所看到的，当你点击地图某处时，猫会沿着你点击的方向跳到相邻的方块上。
我们想对程序做修改，让猫持续的往你点击的方块方向前进，就像许多RPGs或者point-and-click冒险类游戏。
让我们看下控制触摸事件代码的工作原理。如果你打开HelloWorldScene.cpp文件，你将看到像下面这样去实现触摸操作：
auto listener = EventListenerTouchOneByOne::create();
listener->setSwallowTouches( true );
listener->onTouchBegan = [ this ](Touch *touch, Event *event){
if (_gameOver)
{
return false ;
}
Point touchLocation = _tileMap->convertTouchToNodeSpace(touch);
_cat->moveToward(touchLocation);
return true ;
};
_eventDispatcher->(listener, this );
你可以看到这里只是对猫精灵调用了一个方法，让猫在方块地图上往你点击的地方移动。
我们现在要做的是修改在CatSprite.m文件中的以下方法，寻找到达该点的最短路径，并且开始前进：
void CatSprite::moveToward( const Point &target)
{
}
创建ShortestPathStep类
我们开始创建一个内部类，代表路径上的一步操作。在这种情况下，它是一个方块和由A星算法计算出来的的F,G和H scores。
class ShortestPathStep : public cocos2d::Object
{
public :
ShortestPathStep();
~ShortestPathStep();
static ShortestPathStep *createWithPosition( const cocos2d::Point &pos);
bool initWithPosition( const cocos2d::Point &pos);
int getFScore() const ;
bool isEqual( const ShortestPathStep *other) const ;
std::string getDescription() const ;
CC_SYNTHESIZE(cocos2d::Point, _position, Position);
CC_SYNTHESIZE( int , _gScore, GScore);
CC_SYNTHESIZE( int , _hScore, HScore);
CC_SYNTHESIZE(ShortestPathStep*, _parent, Parent);
};
现在添加以下代码到CatSprite.cpp文件的顶部。
CatSprite::ShortestPathStep::ShortestPathStep() :
_position(Point::ZERO),
_gScore(0),
_hScore(0),
_parent(nullptr)
{
}
CatSprite::ShortestPathStep::~ShortestPathStep()
{
}
CatSprite::ShortestPathStep *CatSprite::ShortestPathStep::createWithPosition( const Point &pos)
{
ShortestPathStep *pRet = new ShortestPathStep();
if (pRet && pRet->initWithPosition(pos))
{
pRet->autorelease();
return pRet;
}
else
{
CC_SAFE_DELETE(pRet);
return nullptr;
}
}
bool CatSprite::ShortestPathStep::initWithPosition( const Point &pos)
{
bool bRet = false ;
do
{
this ->setPosition(pos);
bRet = true ;
} while (0);
return bRet;
}
int CatSprite::ShortestPathStep::getFScore() const
{
return this ->getGScore() + this ->getHScore();
}
bool CatSprite::ShortestPathStep::isEqual( const CatSprite::ShortestPathStep *other) const
{
return this ->getPosition() == other->getPosition();
}
std::string CatSprite::ShortestPathStep::getDescription() const
{
return StringUtils::format( "pos=[%.0f;%.0f] g=%d h=%d f=%d" ,
this ->getPosition().x, this ->getPosition().y,
this ->getGScore(), this ->getHScore(), this ->getFScore());
}
正如所见，这是一个很简单的类，记录了以下内容：
- 方块的坐标
- G值（记住，这是开始点到当前点的方块数量）
- H值（记住，这是当前点到目标点的方块估算数量）
- Parent是它的上一步操作
- F值，这是方块的和值（它是G+H的值）
这里定义了getDescription方法，以方便调试。创建了isEquals方法，当且仅当两个ShortestPathSteps的方块坐标相同时，它们相等（例如它们代表着相同的方块）。
创建Open和Closed列表
打开CatSprite.h文件，添加如下代码：
cocos2d::Vector _spOpenSteps;
cocos2d::Vector _spClosedSteps;
检查开始和结束点
重新实现moveToward方法，获取当前方块坐标和目标方块坐标，然后检查是否需要计算一条路径，最后测试目标方块坐标是否可行走的（在这里只有墙壁是不可行走的）。打开CatSprite.cpp文件，修改moveToward方法，为如下：
void CatSprite::moveToward( const Point &target)
{
Point fromTileCoord = _layer->tileCoordForPosition( this ->getPosition());
Point toTileCoord = _layer->tileCoordForPosition(target);
if (fromTileCoord == toTileCoord)
{
CCLOG( "You're already there! :P" );
return ;
}
if (!_layer->isValidTileCoord(toTileCoord) || _layer->isWallAtTileCoord(toTileCoord))
{
SimpleAudioEngine::getInstance()->playEffect( "hitWall.wav" );
return ;
}
CCLOG( "From: %f, %f" , fromTileCoord.x, fromTileCoord.y);
CCLOG( "To: %f, %f" , toTileCoord.x, toTileCoord.y);
}
编译运行，在地图上进行点击，如果不是点击到墙壁的话，可以在控制台看到如下信息：
From: 24.000000, 0.000000
To: 20.000000, 0.000000
其中 **From** 就是猫的方块坐标，**To**就是所点击的方块坐标。
实现A星算法
根据算法，第一步是添加当前坐标到open列表。还需要三个辅助方法：
- 一个方法用来插入一个ShortestPathStep对象到适当的位置（有序的F值）
- 一个方法用来计算从一个方块到相邻方块的移动数值
- 一个方法是根据"曼哈顿距离"算法，计算方块的H值
打开CatSprite.cpp文件，添加如下方法：
void CatSprite::insertInOpenSteps(CatSprite::ShortestPathStep *step)
{
int stepFScore = step->getFScore();
ssize_t count = _spOpenSteps.size();
ssize_t i = 0;
for (; i < count; ++i)
{
if (stepFScore <= _spOpenSteps.at(i)->getFScore())
{
break ;
}
}
_spOpenSteps.insert(i, step);
}
int CatSprite::computeHScoreFromCoordToCoord( const Point &fromCoord, const Point &toCoord)
{
// 忽略了可能在路上的各种障碍
return abs(toCoord.x - fromCoord.x) + abs(toCoord.y - fromCoord.y);
}
int CatSprite::( const ShortestPathStep *fromStep, const ShortestPathStep *toStep)
{
// 因为不能斜着走，而且由于地形就是可行走和不可行走的成本都是一样的
// 如果能够对角移动，或者有沼泽、山丘等等，那么它必须是不同的
return 1;
}
接下来，需要一个方法去获取给定方块的所有相邻可行走方块。因为在这个游戏中，HelloWorld管理着地图，所以在那里添加方法。打开HelloWorldScene.cpp文件，添加如下方法：
PointArray *HelloWorld::( const Point &tileCoord) const
{
PointArray *tmp = PointArray::create(4);
// 上
Point p(tileCoord.x, tileCoord.y - 1);
if ( this ->isValidTileCoord(p) && ! this ->isWallAtTileCoord(p))
{
tmp->addControlPoint(p);
}
// 左
p.setPoint(tileCoord.x - 1, tileCoord.y);
if ( this ->isValidTileCoord(p) && ! this ->isWallAtTileCoord(p))
{
tmp->addControlPoint(p);
}
// 下
p.setPoint(tileCoord.x, tileCoord.y + 1);
if ( this ->isValidTileCoord(p) && ! this ->isWallAtTileCoord(p))
{
tmp->addControlPoint(p);
}
// 右
p.setPoint(tileCoord.x + 1, tileCoord.y);
if ( this ->isValidTileCoord(p) && ! this ->isWallAtTileCoord(p))
{
tmp->addControlPoint(p);
}
return tmp;
}
可以继续CatSprite.cpp中的moveToward方法了，在moveToward方法的后面，添加如下代码：
bool pathFound = false ;
_spOpenSteps.clear();
_spClosedSteps.clear();
// 首先，添加猫的方块坐标到open列表
this ->insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord));
do
{
// 得到最小的F值步骤
// 因为是有序列表，第一个步骤总是最小的F值
ShortestPathStep *currentStep = _spOpenSteps.at(0);
// 添加当前步骤到closed列表
_spClosedSteps.pushBack(currentStep);
// 将它从open列表里面移除
// 需要注意的是，如果想要先从open列表里面移除，应小心对象的内存
_spOpenSteps.erase(0);
// 如果当前步骤是目标方块坐标，那么就完成了
if (currentStep->getPosition() == toTileCoord)
{
pathFound = true ;
ShortestPathStep *tmpStep = currentStep;
CCLOG( "PATH FOUND :" );
do
{
CCLOG( "%s" , tmpStep->getDescription().c_str());
tmpStep = tmpStep->getParent(); // 倒退
} while (tmpStep); // 直到没有上一步
_spOpenSteps.clear();
_spClosedSteps.clear();
break ;
}
// 得到当前步骤的相邻方块坐标
PointArray *adjSteps = _layer->(currentStep->getPosition());
for (ssize_t i = 0; i < adjSteps->count(); ++i)
{
ShortestPathStep *step = ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex(i));
// 检查步骤是不是已经在closed列表
if ( this ->getStepIndex(_spClosedSteps, step) != -1)
{
continue ;
}
// 计算从当前步骤到此步骤的成本
int moveCost = this ->(currentStep, step);
// 检查此步骤是否已经在open列表
ssize_t index = this ->getStepIndex(_spOpenSteps, step);
// 不在open列表，添加它
if (index == -1)
{
// 设置当前步骤作为上一步操作
step->setParent(currentStep);
// G值等同于上一步的G值 + 从上一步到这里的成本
step->setGScore(currentStep->getGScore() + moveCost);
// H值即是从此步骤到目标方块坐标的移动量估算值
step->setHScore( this ->computeHScoreFromCoordToCoord(step->getPosition(), toTileCoord));
// 按序添加到open列表
this ->insertInOpenSteps(step);
}
else
{
// 获取旧的步骤，其值已经计算过
step = _spOpenSteps.at(index);
// 检查G值是否低于当前步骤到此步骤的值
if ((currentStep->getGScore() + moveCost) < step->getGScore())
{
// G值等同于上一步的G值 + 从上一步到这里的成本
step->setGScore(currentStep->getGScore() + moveCost);
// 因为G值改变了，F值也会跟着改变
// 所以为了保持open列表有序，需要将此步骤移除，再重新按序插入
// 在移除之前，需要先保持引用
step->retain();
// 现在可以放心移除，不用担心被释放
_spOpenSteps.erase(index);
// 重新按序插入
this ->insertInOpenSteps(step);
// 现在可以释放它了，因为open列表应该持有它
step->release();
}
}
}
} while (_spOpenSteps.size() > 0);
if (!pathFound)
{
SimpleAudioEngine::getInstance()->playEffect( "hitWall.wav" );
}
添加以下方法：
ssize_t CatSprite::getStepIndex( const cocos2d::Vector &steps, const CatSprite::ShortestPathStep *step)
{
for (ssize_t i = 0; i < steps.size(); ++i)
{
if (steps.at(i)->isEqual(step))
{
return i;
}
}
return -1;
}
编译运行，在地图上进行点击，如下图所示：

From: 24.000000, 0.000000
To: 23.000000, 3.000000
PATH FOUND :
pos=[23;3] g=10 h=0 f=10
pos=[22;3] g=9 h=1 f=10
pos=[21;3] g=8 h=2 f=10
pos=[20;3] g=7 h=3 f=10
pos=[20;2] g=6 h=4 f=10
pos=[20;1] g=5 h=5 f=10
pos=[21;1] g=4 h=4 f=8
pos=[22;1] g=3 h=3 f=6
pos=[23;1] g=2 h=2 f=4
pos=[24;1] g=1 h=3 f=4
pos=[24;0] g=0 h=0 f=0
注意该路径是从后面建立的，所以必须从下往上看猫选择了哪条路径。
跟随路径前进
现在已经找到了路径，只需让猫跟随前进即可。需要创建一个数组去存储路径，打开CatSprite.h文件，添加如下代码：
cocos2d::Vector _shortestPath;
打开CatSprite.cpp文件，更改moveToward方法，注释掉语句**bool pathFound = false**;，如下：
//bool pathFound = false;
替换语句**pathFound = true;**为如下：
//pathFound = true;
this ->(currentStep);
并且注释掉下方的调试语句：
//ShortestPathStep *tmpStep = currentStep;
//CCLOG("PATH FOUND :");
//do
//{
// CCLOG("%s", tmpStep->getDescription().c_str());
// tmpStep = tmpStep->getParent(); // 倒退
/

2. 搜索算法中,A算法A*算法的区别（急）

a*算法：a*（a-star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好
a*
（a-star)算法是一种静态路网中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索算法。之后涌现了很多预处理算法（alt，ch，hl等等），在线查询效率是a*算法的数千甚至上万倍。
公式表示为：
f(n)=g(n)+h(n),
其中
f(n)
是从初始点经由节点n到目标点的估价函数，
g(n)
是在状态空间中从初始节点到n节点的实际代价，
h(n)
是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取：
估价值h(n)<=
n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行，
此时的搜索效率是最高的。
如果
估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

3. 计算机求百钱买百鸡问题采用的算法是

算法如下：

int main()

{

int x, y, z;

for (int k = 1; k <= 3; k++)

{

x = 4 * k;

y = 25 - 7 * k;

z = 75 + 3 * k;

printf("公鸡:%d只，母鸡:%d只,小鸡:%d只 ", x, y, z);

(3)a星算法计算扩展阅读：

A*搜寻算法

俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

Beam Search

束搜索(beam search)方法是解决优化问题的一种启发式方法，它是在分枝定界方法基础上发展起来的，它使用启发式方法估计k个最好的路径，仅从这k个路径出发向下搜索，即每一层只有满意的结点会被保留，其它的结点则被永久抛弃，从而比分枝定界法能大大节省运行时间。

束搜索于20 世纪70年代中期首先被应用于人工智能领域,1976 年Lowerre在其称为HARPY的语音识别系统中第一次使用了束搜索方法。他的目标是并行地搜索几个潜在的最优决策路径以减少回溯，并快速地获得一个解。

二分取中查找算法

一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。

4. 矩阵a*算法是什么

矩阵A*表示A矩阵的伴随矩阵。

伴随矩阵的定义：某矩阵A各元素的代数余子式，组成一个新的矩阵后再进行一下转置，叫做A的伴随矩阵。

某元素代数余子式就是去掉矩阵中某元素所在行和列元素后的形成矩阵的行列式，再乘上-1的（行数+列数）次方。

伴随矩阵的求发：当矩阵是大于等于二阶时：

主对角元素是将原矩阵该元素所在行列去掉再求行列式。

非主对角元素是原矩阵该元素的共轭位置的元素去掉所在行列求行列式乘以(-1)^(x+y) x,y为该元素的共轭位置的元素的行和列的序号，序号从1开始的。

主对角元素实际上是非主对角元素的特殊情况，因为x=y,所以(-1)^(x+y)=(-1)^(2x)=1,一直是正数，没必要考虑主对角元素的符号问题。

5. 人工智能 A*算法原理

A 算法是启发式算法重要的一种，主要是用于在两点之间选择一个最优路径，而A 的实现也是通过一个估值函数

上图中这个熊到树叶的 曼哈顿距离 就是蓝色线所表示的距离，这其中不考虑障碍物，假如上图每一个方格长度为1，那么此时的熊的曼哈顿距离就为9.
起点（X1,Y1）,终点（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我们也可以通过几何坐标点来算出曼哈顿距离，还是以上图为例，左下角为（0，0）点，熊的位置为（1，4），树叶的位置为（7，1），那么H=|7-1|+|1-4|=9。

还是以上图为例，比如刚开始熊位置我们会加入到CLOSE列表中，而熊四周它可以移动到的点位我们会加入到OPEN列表中，并对熊四周的8个节点进行F=G+H这样的估值运算，然后在这8个节点中选中一个F值为最小的节点，然后把再把这个节点从OPEN列表中删除，加入到Close列表中，从接着在对这个节点的四周8个节点进行一个估值运算，再接着依次运算，这样说大家可能不是太理解，我会在下边做详细解释。

从起点到终点，我们通过A星算法来找出最优路径

我们把每一个方格的长度定义为1，那从起始点到5位置的代价就是1，到3的代价为1.41，定义好了我们接着看上图，接着运算

第一步我们会把起始点四周的点加入OPEN列表中然后进行一个估值运算，运算结果如上图，这其中大家看到一个小箭头都指向了起点，这个箭头就是指向父节点，而open列表的G值都是根据这个进行计算的，意思就是我从上一个父节点运行到此处时所需要的总代价，如果指向不一样可能G值就不一样，上图中我们经过计算发现1点F值是7.41是最小的，那我们就选中这个点，并把1点从OPEN列表中删除，加入到CLOSE列表中，但是我们在往下运算的时候发现1点的四周，2点，3点和起始点这三个要怎么处理，首先起始点已经加入到了CLOSE，他就不需要再进行这种运算，这就是CLOSE列表的作用，而2点和3点我们也可以对他进行运算，2点的运算，我们从1移动到2点的时候，他需要的代价也就是G值会变成2.41，而H值是不会变的F=2.41+7=9.41，这个值我们发现大于原来的的F值，那我们就不能对他进行改变（把父节点指向1，把F值改为9.41，因为我们一直追求的是F值最小化），3点也同理。

在对1点四周进行运算后整个OPEN列表中有两个点2点和3点的F值都是7.41，此时我们系统就可能随机选择一个点然后进行下一步运算，现在我们选中的是3点，然后对3点的四周进行运算，结果是四周的OPEN点位如果把父节点指向3点值时F值都比原来的大，所以不发生改变。我们在看整个OPEN列表中，也就2点的7.41值是最小的，那我们就选中2点接着运算。

我们在上一部运算中选中的是1点，上图没有把2点加入OPEN列表，因为有障碍物的阻挡从1点他移动不到2点，所以没有把2点加入到OPEN列表中，整个OPEN列表中3的F=8是最小的，我们就选中3，我们对3点四周进行运算是我们发现4点经过计算G=1+1=2，F=2+6=8所以此时4点要进行改变，F变为8并把箭头指向3点（就是把4点的父节点变为3），如下图

我们就按照这种方法一直进行运算，最后 的运算结果如下图

而我们通过目标点位根据箭头（父节点），一步一步向前寻找最后我们发现了一条指向起点的路径，这个就是我们所需要的最优路径。 如下图的白色选中区域

但是我们还要注意几点

最优路径有2个

这是我对A*算法的一些理解，有些地方可能有BUG，欢迎大家指出，共同学习。