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!
Comment télécharger et enregistrer les vidéos phares du jour
Comment apprendre la programmation Python à partir de zéro
Utilisation courante de Array.slice
menu contextuel
vim sauvegarder et quitter la commande
diffusion sur iPad
Quels sont les outils de développement ?
Méthode d'optimisation du classement des mots clés Baidu SEO
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
