欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

Dijkstra算法与A*算法关于H值取值分析（含c++代码）

程序员文章站 2022-04-15 16:33:23
...

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。
A*算法是在Dijkstra的进一步发展，由于Dijkstra算法虽然能够搜索到最优路径，但是其搜索空间一般比较大。在此基础上，对其进行优化，加入了一个启发式函数H，便于在搜索到最优路径的情况下，减小其搜索空间。
二者的伪代码如下所示：
Dijkstra算法伪代码：
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
Astar算法伪代码：
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
具体算法实现如下：
Astar.h

#pragma once
/*
//A*算法对象类
*/
#include <vector>
#include <list>

const int kcost1 = 10;
const int kcost2 = 14;

struct Point {
	int x;
	int y;

	int f_score, g_score, h_score;
	Point* father;
	Point(int _x, int _y) :x(_x), y(_y), f_score(0), g_score(0), h_score(0), father(NULL)
	{
	}
};

class Astar {
public:
	void  InitAstar(std::vector<std::vector<int>>& _map);
	std::list<Point*> GetPath(Point& start, Point& end, bool isIgnoreCorner);
	std::list<Point*> openlist();
	std::list<Point*> closelist();
private:
	Point* findPath(Point& start, Point& end, bool isIgnoreCorner);
	std::vector<Point*> getSurPoints(const Point* curpoint, bool isIgnoreCorner) const;
	bool isCanSearch(const Point* start, const Point* target, bool isIgnoreCorner) const;
	Point* isInList(const std::list<Point*>& list, const Point* point) const;
	Point* getLeastFpoint();

	int getH(Point* start, Point* end);
	int getG(Point* start, Point* temp);
	int getF(Point* current);
private:
	std::vector<std::vector<int>> map;
	std::list<Point*> openList;
	std::list<Point*> closeList;
};

Astar.cpp:

#include <math.h>
#include "Astar.h"
#include <algorithm>
void Astar::InitAstar(std::vector<std::vector<int>>& _map) {
	map = _map;
}

int Astar::getH(Point* start, Point* end) {
	int dx = abs(end->x - start->x);
	int dy = abs(end->y - start->y);
	//Euclidean距离
	//return sqrt((double)(end->x - start->x) * (double)(end->x - start->x) + (double)(end->y - start->y) * (double)(end->y - start->y)) * kcost1;
	//return (abs(end->x - start->x) + abs(end->y - start->y)) * kcost1;  //Manhattan距离
	//return (dx+dy+(double)(sqrt(2)-2)*std::min(dx,dy))*kcost1; //对角线距离
	return 0;   //Dijkstra算法
}
int Astar::getG(Point* start, Point* temp) {
	int g_temp = (abs(temp->x - start->x) + abs(temp->y - start->y)) == 1 ? kcost1 : kcost2;
	int g_before = temp->father == NULL ? 0 : temp->father->g_score;
	return g_temp + g_before;
}
int Astar::getF(Point* current) {
	return current->g_score + current->h_score;
}

Point* Astar::getLeastFpoint() {
	if (!openList.empty()) {
		auto respoint = openList.front();
		for (auto& p : openList)
			if (p->f_score < respoint->f_score)
				respoint = p;
		return respoint;
	}
	return NULL;
}
Point* Astar::findPath(Point& start, Point& end, bool isIgnoreCorner) {
	openList.push_back(new Point(start.x, start.y));
	while (!openList.empty())
	{
		auto curpoint = getLeastFpoint();
		openList.remove(curpoint);
		closeList.push_back(curpoint);

		auto surPoints = getSurPoints(curpoint, isIgnoreCorner);
		for (auto& target : surPoints) {
			if (!isInList(openList, target)) {
				target->father = curpoint;

				target->g_score = getG(curpoint, target);
				target->h_score = getH(target, &end);
				target->f_score = getF(target);

				openList.push_back(target);
			}
			else {
				Point* p_open = isInList(openList, target);
				int tempG = getG(curpoint, target);
				if (tempG < p_open->g_score) {
					target->father = curpoint;

					target->g_score = tempG;
					target->f_score = getF(target);
				}
			}
			Point* respoint = isInList(openList, &end);
			if (respoint)
				return respoint;
		}
	}
	return NULL;
}

std::list<Point*> Astar::GetPath(Point& start, Point& end, bool isIgnoreCorner) {
	std::list<Point*> path;
	Point* curpoint = findPath(start, end, isIgnoreCorner);
	while (curpoint)
	{
		path.push_front(curpoint);
		curpoint = curpoint->father;
	}
	//openList.clear();
	//closeList.clear();

	return path;
}

Point* Astar::isInList(const std::list<Point*>& list, const Point* point) const {
	for (auto p : list)
		if (p->x == point->x && p->y == point->y)
			return p;
	return NULL;
}

bool Astar::isCanSearch(const Point* start, const Point* target, bool isIgnoreCorner) const
{
	if (target->x < 0 || target->x > map.size() - 1
		|| target->y < 0 || target->y > map[0].size() - 1
		|| map[target->x][target->y] == 1  //障碍物
		|| target->x == start->x && target->y == start->y  //重合
		|| isInList(closeList, target))
		return false;
	else {
		if (abs(target->x - start->x) + abs(target->y - start->y) == 1)
			return true;
		else {
			if (map[start->x][target->y] == 0 && map[target->x][start->y] == 0) {
				return true;
			}
			else
				return isIgnoreCorner;
		}
	}
}
std::vector<Point*> Astar::getSurPoints(const Point* curpoint, bool isIgnoreCorner) const {
	std::vector<Point*> surPoints;
	for (int i = curpoint->x - 1; i <= curpoint->x + 1; i++)
		for (int j = curpoint->y - 1; j <= curpoint->y + 1; j++)
			if (isCanSearch(curpoint, new Point(i, j), isIgnoreCorner)) {
				surPoints.push_back(new Point(i, j));
			}
	return surPoints;
}

std::list<Point*> Astar::openlist() {
	std::list<Point*> path;
	for (auto p : openList)
		path.push_back(p);
	return path;
}
std::list<Point*> Astar::closelist() {
	std::list<Point*> path;
	for (auto c : closeList)
		path.push_back(c);
	return path;
}

main.cpp(测试文件)：

#include <iostream>
#include "Astar.h"
using namespace std;

int main()
{
	//初始化地图，用二维矩阵代表地图，1表示障碍物，0表示可通
	vector<vector<int>> maze = {
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1 },
		{ 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1 },
		{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1 },
		{ 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
	};
	Astar astar;
	astar.InitAstar(maze);
	cout << "Initialization map:" << endl;
	for (int i = 0; i < maze.size(); i++)
		for (int j = 0; j < maze[0].size(); j++) {
			if (j != maze[0].size() - 1)
				cout << maze[i][j] << ",";
			else
				cout << maze[i][j] << endl;
		}
	//设置起始和结束点
	Point start(1, 1);
	Point end(6, 10);
	//A*算法找寻路径
	list<Point*> path = astar.GetPath(start, end, false);
	//打印
	list<Point*> openList = astar.openlist();
	list<Point*> closeList = astar.closelist();
	cout << "The search scope is: " << openList.size() + closeList.size() << endl;
	cout << "The optimal path:" << endl;
	for (auto& p : path) {
		maze[p->x][p->y] = 3;
		cout << '(' << p->x << ',' << p->y << ')';
	}
	cout << endl;

	for (auto& o : openList) {
		if (maze[o->x][o->y] == 3) {
			maze[o->x][o->y] = 3;
		}
		else {
			maze[o->x][o->y] = 4;
		}
}
	for (auto& c : closeList) {
		if (maze[c->x][c->y] == 3) {
			maze[c->x][c->y] = 3;
		}
		else {
			maze[c->x][c->y] = 4;
		}
	}
	cout << "The step numbers: " << path.size() << endl;
	for (int i = 0; i < maze.size(); i++)
		for (int j = 0; j < maze[0].size(); j++) {
			if (j != maze[0].size() - 1)
				cout << maze[i][j] << ",";
			else
				cout << maze[i][j] << endl;
		}
	system("pause");
	return 0;
}

算法实现参考了其他博主的代码，本文主要目的是通过对算法的改进，讲诉Dijkstra与A*，以及A*取各种不同的启发式函数，所产生的区别。
G：只有对角线移动和平移，其中斜对角线移动的G值为14，平移为10
H：采用Euclidean距离函数
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
G：同上
H：采用Manhattan距离函数
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
G：同上
H：采用对角线距离
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
G:同上
H：0，即Dijkstra算法
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
通过结果可见，只需要更改H值，可以产生不同的路径和搜索范围。Dijkstra虽然达到了最优路径，但是其搜索的范围却是最大的，这样容易造成时间的浪费。而不同的启发式函数H，在减小搜索范围的同时，也将产生不同的路径，因此在应用时，需要对其进行一定的设计。为了打破对称性，可以设计一个tie_break值，该值可以设计为：
Dijkstra算法与A*算法关于H值取值分析（含c++代码）
则H值可以更新为h=h+p。

相关标签： 自动驾驶

上一篇： Java 复杂计算器的实现

下一篇： Asp.Net Core 轻松学-利用 Swagger 自动生成接口文档

推荐阅读