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函数实现了贪心最佳优先搜索算法。它使用一个优先队列来存储节点，根据它们的启发式值进行排序。

该算法首先将起始节点入队到优先队列中。

在每次迭代中，它出队优先级最高的节点，并检查它是否为目标节点。

如果找到目标节点，则打印出”找到路径！”的消息。否则，算法将已出队的节点标记为已访问，并将其未访问的相邻节点入队。

如果优先队列在没有找到目标节点的情况下变为空，则打印出”路径不存在！”的消息。

主函数通过创建一个图、定义起始节点和目标节点，然后调用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;
}