Maison > Article > développement back-end > 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++.
void greedyBestFirstSearch(Graph graph, Node startNode, Node goalNode);
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.
#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!
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 fonctiongreedyBestFirstSearch 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.
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.
#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; }
Goal node reached!
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 fonctiongreedyBestFirstSearch 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.
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!