数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的贪婪最佳优先搜索算法
计算机科学中的良好问题解决很大程度上依赖于高效的算法，例如贪婪最佳优先搜索 (GBFS)。GBFS 已经确立了作为路径查找或优化问题的最佳解决方案方法的可信度。因此，我们在本文中深入探讨了 GBFS，同时探索了使用 C++ 的实现方法。
语法
void greedyBestFirstSearch(Graph graph, Node startNode, Node goalNode);
算法
贪婪最佳优先搜索算法旨在找到图中从给定起始节点到目标节点的路径。以下是算法的常规步骤：
初始化一个空优先队列。
将起始节点入队到优先队列中。
创建一个空集合来跟踪已访问的节点。
当优先队列不为空时：
从队列中出队优先级最高的节点。
如果出队的节点是目标节点，则算法终止，并且找到路径。
否则，将出队的节点标记为已访问。
将出队的节点的所有未访问的相邻节点入队到优先队列中。
如果在到达目标节点之前优先队列变空，则不存在路径。
方法 1：基于欧几里得距离的启发式函数
示例
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#include <unordered_set>
using namespace std;
// Structure to represent a node in the graph
struct Node {
int x, y; // Coordinates of the node
int cost; // Cost to reach this node
};
// Euclidean distance heuristic function
double euclideanDistance(int x1, int y1, int x2, int y2) {
return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));
}
// Custom comparison function for nodes in the priority queue
struct NodeCompare {
bool operator()(const Node& node1, const Node& node2) const {
return node1.cost > node2.cost;
}
};
// Greedy Best-First Search function
void greedyBestFirstSearch(vector<vector<int>>& graph, Node start, Node goal) {
int rows = graph.size();
int cols = graph[0].size();
// Priority queue for nodes to be explored
priority_queue<Node, vector<Node>, NodeCompare> pq;
// Visited nodes set
unordered_set<int> visited;
// Add the start node to the priority queue
pq.push(start);
while (!pq.empty()) {
// Get the node with the lowest cost
Node current = pq.top();
pq.pop();
// Check if the current node is the goal node
if (current.x == goal.x && current.y == goal.y) {
cout << "Goal node reached!" << endl;
return;
}
// Mark the current node as visited
int nodeId = current.x * cols + current.y;
visited.insert(nodeId);
// Explore the neighboring nodes
int dx[] = {-1, 1, 0, 0}; // Possible x-direction movements
int dy[] = {0, 0, -1, 1}; // Possible y-direction movements
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
// Check if the neighboring node is within the graph boundaries
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
// Calculate the heuristic value for the neighboring node
double heuristicValue = euclideanDistance(newX, newY, goal.x, goal.y);
// Check if the neighboring node has not been visited
if (visited.find(newX * cols + newY) == visited.end()) {
// Create a new node for the neighboring position
Node neighbor;
neighbor.x = newX;
neighbor.y = newY;
neighbor.cost = current.cost + graph[newX][newY];
// Add the neighboring node to the priority queue
pq.push(neighbor);
}
}
}
}
cout << "Goal node not reachable!" << endl;
}
int main() {
// Example graph represented as a 2D vector
vector<vector<int>> graph = {
{3, 5, 1, 2},
{1, 3, 2, 4},
{5, 2, 6, 7},
{4, 3, 1, 2}
};
Node start;
start.x = 0; // Starting x-coordinate
start.y = 0; // Starting y-coordinate
start.cost = 0; // Cost to reach the starting node
Node goal;
goal.x = 3; // Goal x-coordinate
goal.y = 3; // Goal y-coordinate
// Run Greedy Best-First Search algorithm
greedyBestFirstSearch(graph, start, goal);
return 0;
}
输出
Goal node reached!
解释
这段代码包含两个关键元素。首先，它包含 Graph 类的定义，该类使用邻接表表示图结构。
其次，它引入了 CompareEuclideanDistance - 一个自定义比较器，用于通过使用欧几里得距离公式估计节点与目标节点的距离来评估节点。
greedyBestFirstSearch 函数实现了贪婪最佳优先搜索算法。它使用优先队列根据启发式值存储节点。
该算法首先将起始节点入队到优先队列中。
在每次迭代中，它都出队优先级最高的节点，并检查它是否为目标节点。
如果找到目标节点，则打印“路径已找到！”消息。否则，该算法将出队的节点标记为已访问，并将其未访问的相邻节点入队。
如果优先队列在未找到目标节点的情况下变空，则打印“不存在路径！”消息。
main 函数通过创建图、定义起始和目标节点以及调用 greedyBestFirstSearch 函数来演示算法的使用。
方法 2：基于曼哈顿距离的启发式函数
我们解决此问题的策略是使用依赖于曼哈顿距离概念的启发式函数。这种距离度量，有时称为出租车距离，涉及将节点之间的水平和垂直距离加起来。
示例
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#include <unordered_set>
using namespace std;
// Structure to represent a node in the graph
struct Node {
int x, y; // Coordinates of the node
int cost; // Cost to reach this node
};
// Manhattan distance heuristic function
int manhattanDistance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
// Custom comparison function for nodes in the priority queue
struct NodeCompare {
bool operator()(const Node& node1, const Node& node2) const {
return node1.cost > node2.cost;
}
};
// Greedy Best-First Search function
void greedyBestFirstSearch(vector<vector<int>>& graph, Node start, Node goal) {
int rows = graph.size();
int cols = graph[0].size();
// Priority queue for nodes to be explored
priority_queue<Node, vector<Node>, NodeCompare> pq;
// Visited nodes set
unordered_set<int> visited;
// Add the start node to the priority queue
pq.push(start);
while (!pq.empty()) {
// Get the node with the lowest cost
Node current = pq.top();
pq.pop();
// Check if the current node is the goal node
if (current.x == goal.x && current.y == goal.y) {
cout << "Goal node reached!" << endl;
return;
}
// Mark the current node as visited
int nodeId = current.x * cols + current.y;
visited.insert(nodeId);
// Explore the neighboring nodes
int dx[] = {-1, 1, 0, 0}; // Possible x-direction movements
int dy[] = {0, 0, -1, 1}; // Possible y-direction movements
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
// Check if the neighboring node is within the graph boundaries
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
// Calculate the heuristic value for the neighboring node
int heuristicValue = manhattanDistance(newX, newY, goal.x, goal.y);
// Check if the neighboring node has not been visited
if (visited.find(newX * cols + newY) == visited.end()) {
// Create a new node for the neighboring position
Node neighbor;
neighbor.x = newX;
neighbor.y = newY;
neighbor.cost = current.cost + graph[newX][newY];
// Add the neighboring node to the priority queue
pq.push(neighbor);
}
}
}
}
cout << "Goal node not reachable!" << endl;
}
int main() {
// Example graph represented as a 2D vector
vector<vector<int>> graph = {
{3, 5, 1, 2},
{1, 3, 2, 4},
{5, 2, 6, 7},
{4, 3, 1, 2}
};
Node start;
start.x = 0; // Starting x-coordinate
start.y = 0; // Starting y-coordinate
start.cost = 0; // Cost to reach the starting node
Node goal;
goal.x = 3; // Goal x-coordinate
goal.y = 3; // Goal y-coordinate
// Run Greedy Best-First Search algorithm
greedyBestFirstSearch(graph, start, goal);
return 0;
}
输出
Goal node reached!
解释
该代码的结构与方法 1 类似，但使用了一个自定义比较器 CompareManhattanDistance，该比较器使用曼哈顿距离公式根据节点到目标节点的估计距离对节点进行比较。
greedyBestFirstSearch 函数使用曼哈顿距离启发式实现了贪婪最佳优先搜索算法。
main 函数演示了算法的使用，创建了一个图，定义了起始和目标节点，并调用了 greedyBestFirstSearch 函数。
结论
在本文中，我们探讨了贪婪最佳优先搜索算法及其在 C++ 中的实现。通过使用这些方法，程序员可以有效地在图中找到路径并解决优化问题。启发式函数（例如欧几里得距离或曼哈顿距离）的选择会显着影响算法在不同场景下的性能。
更新于：2023-07-25
1K+ 阅读量
广告