启发式搜索 - 进阶搜索 - 深入浅出程序设计竞赛(进阶篇) - 书籍

启发式搜索是一种用于解决搜索问题的算法，它通过使用启发式函数来评估哪些路径最有可能导致目标。启发式函数是一种估计，表示从当前节点到目标节点的预期成本。这种方法可以显著地减少搜索空间，提高搜索效率。

# A* 算法

A*（A-Star）算法是启发式搜索中最著名的算法之一。它结合了最佳优先搜索和 Dijkstra 算法的特点：使用启发式信息来指导搜索方向，并确保找到最短路径。

A * 算法的关键在于其评价函数 (f (n) = g (n) + h (n))，其中：

(g (n)) 是从起始节点到当前节点 (n) 的实际成本。
(h (n)) 是从节点 (n) 到目标节点的预估成本，由启发式函数给出。
(f (n)) 是节点 (n) 的总预估成本。

# 示例

假设我们要在一个网格上找到从点 S（起点）到点 T（目标点）的最短路径。障碍物将阻挡路径。我们的目标是找到一条避开障碍物的最短路径。

# 代码

以下是 A * 搜索算法在简化网格中寻找最短路径的 C++ 实现。为了简化，我们假设每个移动的成本相同，启发式函数 (h (n)) 使用曼哈顿距离作为节点 (n) 到目标的预估成本。

	#include <iostream>
	#include <vector>
	#include <queue>
	#include <map>
	#include <cmath>
	#include <set>

	using namespace std;

	struct Node {
	int x, y;
	int g, h;
	Node *parent;

	Node(int x, int y, Node *p = nullptr) : x(x), y(y), g(0), h(0), parent(p) {}

	int f() const { return g + h; }

	bool operator<(const Node& o) const { return f() > o.f(); }
	};

	int heuristic(int x, int y, int goalX, int goalY) {
	// 使用曼哈顿距离作为启发式函数
	return abs(x - goalX) + abs(y - goalY);
	}

	bool isValid(int x, int y, int N, int M, const vector<vector<bool>>& obstacles) {
	return x >= 0 && y >= 0 && x < N && y < M && !obstacles[x][y];
	}

	vector<Node*> aStarSearch(int startX, int startY, int goalX, int goalY, const vector<vector<bool>>& obstacles) {
	int N = obstacles.size(), M = obstacles[0].size();
	priority_queue<Node> openList;
	set<pair<int, int>> closedList;
	openList.emplace(startX, startY);

	while (!openList.empty()) {
	Node current = openList.top();
	openList.pop();

	if (current.x == goalX && current.y == goalY) {
	vector<Node*> path;
	Node *node = new Node(current.x, current.y, current.parent);
	while (node != nullptr) {
	path.push_back(node);
	node = node->parent;
	}
	return path;
	}

	closedList.insert({current.x, current.y});

	vector<pair<int, int>> directions<!--swig0-->;
	for (const auto& dir : directions) {
	int newX = current.x + dir.first;
	int newY = current.y + dir.second;

	if (!isValid(newX, newY, N, M, obstacles) \|\| closedList.find({newX, newY}) != closedList.end())
	continue;

	Node *successor = new Node(newX, newY, new Node(current.x, current.y, current.parent));
	successor->g = current.g + 1;
	successor->h = heuristic(newX, newY, goalX, goalY);
	openList.push(*successor);
	}
	}

	return {};
	}

	int main() {
	vector<vector<bool>> obstacles = {
	{false, false, false, false},
	{false, true, true, false},
	{false, false, false, false},
	{false, false, true, false}
	};

	auto path = aStarSearch(0, 0, 3, 3, obstacles);
	for (auto it = path.rbegin(); it != path.rend(); ++it) {
	cout << "(" << (it)->x << ", " << (it)->y << ") ";
	}
	return 0;
	}

在这个例子中， Node 结构体代表网格中的一个节点，包含其位置、从起点到该节点的成本 (g)、从该节点到终点的启发式估计成本 (h) 和父节点指针。 aStarSearch 函数实现了 A * 搜索算法，搜索网格上从起点到终点的最短路径。 heuristic 函数计算启发式函数值，这里使用曼哈顿距离作为估计。

请注意，这个实现主要用于说明 A * 算法的基本思想，并未处理所有边界情况或优化性能。在实际应用中，可能需要更多的考虑，例如更有效的内存管理和复杂场景下的启发式函数选择。

进阶技巧与思想启发式搜索

# A* 算法

# 示例

# 代码

迭代加深与双向搜索

二叉堆