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;

// 表示图中节点的结构
struct Node {
    int x, y; // 节点的坐标
    int cost; // 到达此节点的成本
};

// 欧几里得距离启发式函数
double euclideanDistance(int x1, int y1, int x2, int y2) {
    return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));
}

// 优先级队列中节点的自定义比较函数
struct NodeCompare {
    bool operator()(const Node& node1, const Node& node2) const {
        return node1.cost > node2.cost;
    }
};

// 贪婪最佳优先搜索函数
void greedyBestFirstSearch(vector<vector<int>>& graph, Node start, Node goal) {
    int rows = graph.size();
    int cols = graph[0].size();
    
    // 待探索节点的优先级队列
    priority_queue<Node, vector<Node>, NodeCompare> pq;
    
    // 已访问节点集
    unordered_set<int> visited;
    
    // 将起始节点添加到优先级队列
    pq.push(start);
    
    while (!pq.empty()) {
        // 获取成本最低的节点
        Node current = pq.top();
        pq.pop();
        
        // 检查当前节点是否为目标节点
        if (current.x == goal.x && current.y == goal.y) {
        cout << "Goal node reached!" << endl;
        return;
        }
        
        // 将当前节点标记为已访问
        int nodeId = current.x * cols + current.y;
        visited.insert(nodeId);
        
        // 探索相邻节点
        int dx[] = {-1, 1, 0, 0}; // 可能的 x 方向移动
        int dy[] = {0, 0, -1, 1}; // 可能的 y 方向移动
        
        for (int i = 0; i < 4; i++) {
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];
            
            // 检查邻近节点是否在图边界内
            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
                // 计算邻近节点的启发式值
                double heuristicValue = euclideanDistance(newX, newY, goal.x, goal.y);
                
                // 检查邻近节点是否未被访问过
                if (visited.find(newX * cols + newY) == accessed.end()) {
                    // 为邻近位置创建新节点
                    Node neighbour;
                    neighbour.x = newX;
                    neighbour.y = newY;
                    neighbour.cost = current.cost + graph[newX][newY];
                    
                    // 将邻近节点添加到优先级队列
                    pq.push(neighbor);
                }
            }
        }
   }

   cout << "Goal node not reachable!" << endl;
}

int main() {
    // 以 2D 向量表示的示例图
    vector<vector<int>> graph = {
        {3, 5, 1, 2},
        {1, 3, 2, 4},
        {5, 2, 6, 7},
        {4, 3, 1, 2}
    };
    
    节点开始;
    start.x = 0; // 起始 x 坐标
    start.y = 0; // 起始 y 坐标
    start.cost = 0; // 到达起始节点的成本
    
    节点目标;
    goal.x = 3; // 目标 x 坐标
    goal.y = 3; // 目标 y 坐标
    
    // 运行贪婪最佳优先搜索算法
    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;

// 表示图中节点的结构
struct Node {
    int x, y; // 节点的坐标
    int cost; // 到达此节点的成本
};

// 曼哈顿距离启发式函数
int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// 优先级队列中节点的自定义比较函数
struct NodeCompare {
   bool operator()(const Node& node1, const Node& node2) const {
      return node1.cost > node2.cost;
   }
};

// 贪婪最佳优先搜索函数
void greedyBestFirstSearch(vector<vector<int>>& graph, Node start, Node goal) {
    int rows = graph.size();
    int cols = graph[0].size();
    
    // 待探索节点的优先级队列
    priority_queue<Node, vector<Node>, NodeCompare> pq;
    
    // 已访问节点集
    unordered_set<int> visited;
    
    // 将起始节点添加到优先级队列
    pq.push(start);
    
    while (!pq.empty()) {
        // 获取成本最低的节点
        Node current = pq.top();
        pq.pop();
        
        // 检查当前节点是否为目标节点
        if (current.x == goal.x && current.y == goal.y) {
        cout << "Goal node reached!" << endl;
        return;
        }
        
        // 将当前节点标记为已访问
        int nodeId = current.x * cols + current.y;
        visited.insert(nodeId);
        
        // 探索邻近节点
        int dx[] = {-1, 1, 0, 0}; // 可能的 x 方向移动
        int dy[] = {0, 0, -1, 1}; // 可能的 y 方向移动

        for (int i = 0; i < 4; i++) {
         int newX = current.x + dx[i];
         int newY = current.y + dy[i];
            
         // 检查邻近节点是否在图边界内
         if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
            // 计算邻近节点的启发式值
            int heuristicValue = manhattanDistance(newX, newY, goal.x, goal.y);
            
            // 检查邻近节点是否未被访问过
            if (visited.find(newX * cols + newY) == visited.end()) {
               // 为邻近位置创建一个新节点
               Node neighbor;
               neighbor.x = newX;
               neighbor.y = newY;
               neighbor.cost = current.cost + graph[newX][newY];
        
               // 将邻居节点加入到优先级队列
               pq.push(neighbor);
            }
         }
        }
   }

   cout << "Goal node not reachable!" << endl;
}

int main() {
    // 以 2D 向量表示的示例图
    vector<vector<int>> graph = {
        {3, 5, 1, 2},
        {1, 3, 2, 4},
        {5, 2, 6, 7},
        {4, 3, 1, 2}
    };
    
    节点开始;
    start.x = 0; // 起始 x 坐标
    start.y = 0; // 起始 y 坐标
    start.cost = 0; // 到达起始节点的成本
    
    节点目标;
    goal.x = 3; // 目标 x 坐标
    goal.y = 3; // 目标 y 坐标
    
    // 运行贪婪最佳优先搜索算法
    greedyBestFirstSearch(graph, start, goal);
    
    return 0;
}

输出

Goal node reached!

解释

代码遵循与方法 1 类似的结构，但使用自定义比较器 CompareManhattanDistance，该比较器使用曼哈顿距离公式根据节点与目标节点的估计距离对节点进行比较。

greedyBestFirstSearch 函数使用曼哈顿距离启发式方法实现贪婪最佳优先搜索算法。

主函数演示了算法的用法、创建图、定义起始节点和目标节点以及调用 greedyBestFirstSearch 函数。

结论

在本文中，我们探讨了贪婪最佳优先搜索算法及其在 C++ 中的实现。通过采用这些方法，程序员可以有效地在图中查找路径并解决优化问题。启发式函数的选择(例如欧几里得距离或曼哈顿距离)会显著影响算法在不同场景下的性能。

相关文章

• C++ 程序在 K 次左旋转后查找数组的第 M 个元素
• 使用 C++ 查找五角金字塔数
• 使用 C++ 查找佩尔数
• C++ 返回扩展矩阵中的前一个元素
• 使用 C++ 查找 0 内 1 的模式
• C++ 使用队列反转 BST 中的路径
• 使用 C++ 查找数组中的正负值对\
• 使用 C++ 在矩阵中查找具有最大和的对
• 使用 C++ 在矩阵中查找具有给定总和的对
• C++ 用其他数的幂表示数字