Implémentation de l'algorithme de recherche Greedy Best-First en C++

Une bonne résolution de problèmes en informatique repose fortement sur des algorithmes efficaces tels que Greedy Best First Search (GBFS). GBFS a établi sa crédibilité comme la meilleure solution aux problèmes de recherche de chemin ou d'optimisation. Par conséquent, dans cet article, nous discutons en profondeur de GBFS tout en explorant son implémentation en utilisant C++.

Grammaire

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

Algorithme

Le meilleur premier algorithme de recherche glouton vise à trouver le chemin d'un nœud de départ donné à un nœud cible dans le graphique. Voici les étapes générales de l'algorithme -

• Initialisez une file d'attente prioritaire vide.

• Mettez le nœud de départ dans la file d'attente prioritaire.

• Créez un ensemble vide pour suivre les nœuds visités.

• Quand la file d'attente prioritaire n'est pas vide -

• Supprimez de la file d'attente le nœud ayant la priorité la plus élevée.

• Si le nœud retiré de la file d'attente est le nœud cible, l'algorithme se termine et le chemin est trouvé.

• Sinon, marquez le nœud de sortie de file d'attente comme visité.

• Mettez tous les nœuds voisins non visités du nœud retiré de la file d'attente dans la file d'attente prioritaire.

• Si la file d'attente prioritaire devient vide avant d'atteindre le nœud cible, aucun chemin n'existe.

Méthode 1 : Fonction heuristique basée sur la distance euclidienne

Exemple

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

Sortie

Goal node reached!

Instructions

Ce code contient deux éléments clés. Tout d’abord, il contient la définition de la classe Graph, qui représente une structure graphique utilisant des listes de contiguïté.

Deuxièmement, il introduit CompareEuclideanDistance - un comparateur personnalisé pour évaluer les nœuds en estimant leur distance par rapport au nœud cible à l'aide de la formule de distance euclidienne.

La fonction

greedyBestFirstSearch implémente le meilleur algorithme de recherche gourmand. Il utilise une file d'attente prioritaire pour stocker les nœuds en fonction de leurs valeurs heuristiques.

L'algorithme place d'abord le nœud de départ dans la file d'attente prioritaire.

À chaque itération, il retire le nœud la plus prioritaire et vérifie s'il s'agit du nœud cible.

Si le nœud cible est trouvé, un message « Chemin trouvé ! » est imprimé. Sinon, l'algorithme marque le nœud retiré de la file d'attente comme visité et met en file d'attente ses nœuds voisins non visités.

Si la file d'attente prioritaire devient vide et qu'aucun nœud cible n'est trouvé, un message « Le chemin n'existe pas ! » est imprimé.

La fonction principale démontre l'utilisation de l'algorithme en créant un graphique, en définissant le nœud de départ et le nœud cible et en appelant la fonction greedyBestFirstSearch.

Méthode 2 : Fonction heuristique basée sur la distance de Manhattan

Notre stratégie pour résoudre ce problème nécessite l'utilisation d'une fonction heuristique qui s'appuie sur le concept de distance de Manhattan. Cette mesure de distance, parfois appelée distance de taxi, consiste à additionner les distances horizontales et verticales entre les nœuds.

Exemple

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

Sortie

Goal node reached!

Instructions

Ce code suit une structure similaire à la méthode 1, mais utilise un comparateur personnalisé, CompareManhattanDistance, qui utilise la formule de distance de Manhattan pour comparer les nœuds en fonction de leur distance estimée par rapport au nœud cible.

La fonction

greedyBestFirstSearch implémente le meilleur algorithme de recherche gourmand en utilisant l'heuristique de distance de Manhattan.

La fonction principale démontre l'utilisation de l'algorithme, crée un graphique, définit le nœud de départ et le nœud cible et appelle la fonction greedyBestFirstSearch.

Conclusion

Dans cet article, nous explorons l'algorithme de recherche glouton du meilleur premier et son implémentation en C++. En employant ces méthodes, les programmeurs peuvent trouver efficacement des chemins dans les graphiques et résoudre des problèmes d'optimisation. Le choix de la fonction heuristique, telle que la distance euclidienne ou la distance de Manhattan, peut affecter considérablement les performances de l'algorithme dans différents scénarios.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!