我使用 Justin Heyes-Jones 实现 astar 算法。我的启发式函数只是欧几里得距离。在附图中(抱歉质量不好)描述了一个特定的情况:假设我们从节点 1 到节点 2。最短的方法是通过节点 a - b - c - d - e。但是带有欧几里得启发式的逐步 Astar 将为我们提供通过以下节点的方法:a - b' - c' - d' - e 我理解为什么会发生这种情况。但是我该怎么做才能让它返回最短路径?!
真正的路线图导入代码:
#include "search.h"
class ArcList;
class MapNode
{
public:
int x, y; // ���������� ����
MapNode();
MapNode(int X, int Y);
float Get_h( const MapNode & Goal_node );
bool GetNeighbours( AStarSearch<MapNode> *astarsearch, MapNode *parent_node );
bool IsSamePosition( const MapNode &rhs );
void PrintNodeInfo() const;
bool operator == (const MapNode & other) const;
void setArcList( ArcList * list );
private:
ArcList * list;
};
class Arc
{
public:
MapNode A1;
MapNode B1;
Arc(const MapNode & a, const MapNode & b);
};
class ArcList
{
public:
void setArcs( const std::vector<Arc> & arcs );
void addArc( const Arc & arc );
size_t size() const;
bool addNeighbours( AStarSearch<MapNode> * astarsearch, const MapNode & neighbour );
private :
std::vector<Arc> arcs;
};
std::vector <MapNode> FindPath(const MapNode & StartNode, const MapNode & GoalNode)
{
AStarSearch<MapNode> astarsearch;
astarsearch.SetStartAndGoalStates( StartNode, GoalNode );
unsigned int SearchState;
unsigned int SearchSteps = 0;
do
{
if ( SearchSteps % 100 == 0)
std::cout << "making step " << SearchSteps << endl;
SearchState = astarsearch.SearchStep();
SearchSteps++;
}
while ( SearchState == AStarSearch<MapNode>::SEARCH_STATE_SEARCHING );
std::vector<MapNode> S;
if ( SearchState == AStarSearch<MapNode>::SEARCH_STATE_SUCCEEDED )
{
int steps = 0;
for ( MapNode * node = astarsearch.GetSolutionStart(); node != 0; node = astarsearch.GetSolutionNext() )
{
S.push_back(*node);
// node->PrintNodeInfo();
}
astarsearch.FreeSolutionNodes();
}
else if ( SearchState == AStarSearch<MapNode>::SEARCH_STATE_FAILED )
{
throw " SEARCH_FAILED ";
}
return S;
}
函数 FindPath 给了我结果节点的向量。
这是 addNeighbours 方法:
bool ArcList::addNeighbours( AStarSearch<MapNode> * astarsearch, const MapNode & target )
{
assert(astarsearch != 0);
bool found = false;
for (size_t i = 0; i < arcs.size(); i++ )
{
Arc arc = arcs.at(i);
if (arc.A1 == target)
{
found = true;
astarsearch->AddSuccessor( arc.B1 );
}
else if (arc.B1 == target )
{
found = true;
astarsearch->AddSuccessor( arc.A1 );
}
}
return found;
}
和 get_h 方法:
float MapNode::Get_h( const MapNode & Goal_node )
{
float dx = x - Goal_node.x;
float dy = y - Goal_node.y;
return ( dx * dx + dy * dy );
}
我知道它不是精确的距离(这里不取平方根) - 这样做是为了在评估时节省一些机器资源。