Implementation of Greedy Best-First Search Algorithm in C++

Good problem solving in computer science relies heavily on efficient algorithms such as Greedy Best First Search (GBFS). GBFS has established credibility as the best solution to pathfinding or optimization problems. Therefore, in this article we discuss GBFS in depth while exploring its implementation in C.

grammar

void greedyBestFirstSearch(Graph graph, Node startNode, Node goalNode);

algorithm

The greedy best first search algorithm aims to find the path from a given start node to a target node in the graph. The following are the general steps of the algorithm -

• Initialize an empty priority queue.

• Put the starting node into the priority queue.

• Create an empty set to track visited nodes.

• When the priority queue is not empty -

• Dequeue the node with the highest priority from the queue.

• If the dequeued node is the target node, the algorithm terminates and the path is found.

• Otherwise, mark the dequeue node as visited.

• Put all unvisited neighbor nodes of the dequeued node into the priority queue.

• If the priority queue becomes empty before reaching the destination node, no path exists.

Method 1: Heuristic function based on Euclidean distance

Example

#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;
}

Output

Goal node reached!

illustrate

This code contains two key elements. First, it contains the definition of the Graph class, which represents a graph structure using adjacency lists.

Secondly, it introduces CompareEuclideanDistance - a custom comparator for evaluating nodes by estimating their distance from the target node using the Euclidean distance formula.

greedyBestFirstSearch function implements the greedy best first search algorithm. It uses a priority queue to store nodes based on their heuristic values.

This algorithm first puts the starting node into the priority queue.

In each iteration, it dequeues the highest priority node and checks if it is the target node.

If the target node is found, the "Path Found!" message will be printed. Otherwise, the algorithm marks the dequeued node as visited and enqueues its unvisited neighboring nodes.

If the priority queue becomes empty and no target node is found, a "Path does not exist!" message is printed.

The main function demonstrates the usage of the algorithm by creating a graph, defining the starting node and target node, and calling the greedyBestFirstSearch function.

Method 2: Heuristic function based on Manhattan distance

Our strategy for solving this problem requires the use of a heuristic function that relies on the concept of Manhattan distance. This distance measure, sometimes called taxi distance, involves adding the horizontal and vertical distances between nodes.

Example

#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;
}

Output

Goal node reached!

illustrate

This code follows a similar structure to Method 1, but uses a custom comparator, CompareManhattanDistance, which uses the Manhattan distance formula to compare nodes based on their estimated distance to the target node.

greedyBestFirstSearch function implements the greedy best first search algorithm using the Manhattan distance heuristic.

The main function demonstrates the use of the algorithm, creates a graph, defines the starting node and target node, and calls the greedyBestFirstSearch function.

in conclusion

In this article, we explore the greedy best-first search algorithm and its implementation in C. By employing these methods, programmers can efficiently find paths in graphs and solve optimization problems. The choice of heuristic function, such as Euclidean distance or Manhattan distance, can significantly affect the performance of the algorithm in different scenarios.

The above is the detailed content of Implementation of Greedy Best-First Search Algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!