计算机科学中良好的问题解决很大程度上依赖于高效的算法，例如贪婪最佳优先搜索（GBFS）。 GBFS 已经确立了作为寻路或优化问题的最佳解决方法的可信度。因此，我们在本文中深入讨论 GBFS，同时探索其使用 C++ 的实现方法。
语法
void greedyBestFirstSearch(Graph graph, Node startNode, Node goalNode);
算法
贪心最佳优先搜索算法旨在找到图中从给定起始节点到目标节点的路径。以下是该算法的一般步骤 –
初始化一个空的优先级队列。
将起始节点放入优先级队列。
立即学习“C++免费学习笔记（深入）”；
创建一个空集来跟踪访问过的节点。
当优先级队列不为空时 –
将优先级最高的节点从队列中出列。
如果出队的节点是目标节点，则算法终止，并找到路径。
否则，将出队节点标记为已访问。
将出队节点的所有未访问的邻居节点放入优先级队列中。
如果优先级队列在到达目标节点之前变空，则不存在路径。
方法一：基于欧氏距离的启发式函数
示例
#include #include #include #include #include using namespace std;// Structure to represent a node in the graphstruct Node { int x, y; // Coordinates of the node int cost; // Cost to reach this node};// Euclidean distance heuristic functiondouble 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 queuestruct NodeCompare { bool operator()(const Node& node1, const Node& node2) const { return node1.cost > node2.cost; }};// Greedy Best-First Search functionvoid greedyBestFirstSearch(vector<vector>& 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, NodeCompare> pq; // Visited nodes set unordered_set 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 = 0 && newX = 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> 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 #include #include #include #include using namespace std;// Structure to represent a node in the graphstruct Node { int x, y; // Coordinates of the node int cost; // Cost to reach this node};// Manhattan distance heuristic functionint manhattanDistance(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2);}// Custom comparison function for nodes in the priority queuestruct NodeCompare { bool operator()(const Node& node1, const Node& node2) const { return node1.cost > node2.cost; }};// Greedy Best-First Search functionvoid greedyBestFirstSearch(vector<vector>& 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, NodeCompare> pq; // Visited nodes set unordered_set 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 = 0 && newX = 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> 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++ 中的实现。通过采用这些方法，程序员可以有效地找到图中的路径并解决优化问题。启发式函数的选择，例如欧氏距离或曼哈顿距离，可以显着影响算法在不同场景下的性能。
以上就是贪婪最佳优先搜索算法（Greedy Best-First Search Algorithm）在C++中的实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445111.html
微信扫一扫 
支付宝扫一扫 
