Eine gute Problemlösung in der Informatik hängt stark von effizienten Algorithmen wie Greedy Best First Search (GBFS) ab. GBFS hat sich als beste Lösung für Pfadfindungs- oder Optimierungsprobleme einen Namen gemacht. Daher besprechen wir in diesem Artikel GBFS ausführlich und untersuchen gleichzeitig seine Implementierung mit C++.
void greedyBestFirstSearch(Graph graph, Node startNode, Node goalNode);
Der Greedy-Best-First-Suchalgorithmus zielt darauf ab, den Pfad von einem bestimmten Startknoten zu einem Zielknoten im Diagramm zu finden. Hier sind die allgemeinen Schritte des Algorithmus -
Initialisieren Sie eine leere Prioritätswarteschlange.
Stellen Sie den Startknoten in die Prioritätswarteschlange.
Erstellen Sie einen leeren Satz, um besuchte Knoten zu verfolgen.
Wenn die Prioritätswarteschlange nicht leer ist -
Entfernen Sie den Knoten mit der höchsten Priorität aus der Warteschlange.
Wenn der aus der Warteschlange entfernte Knoten der Zielknoten ist, wird der Algorithmus beendet und der Pfad wird gefunden.
Andernfalls markieren Sie den Dequeue-Knoten als besucht.
Alle nicht besuchten Nachbarknoten des aus der Warteschlange entfernten Knotens in die Prioritätswarteschlange stellen.
Wenn die Prioritätswarteschlange leer wird, bevor der Zielknoten erreicht wird, ist kein Pfad vorhanden.
#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!
Dieser Code enthält zwei Schlüsselelemente. Erstens enthält es die Definition der Graph-Klasse, die eine Graphstruktur mithilfe von Adjazenzlisten darstellt.
Zweitens wird CompareEuclideanDistance eingeführt – ein benutzerdefinierter Komparator zur Bewertung von Knoten durch Schätzung ihrer Entfernung vom Zielknoten mithilfe der euklidischen Entfernungsformel.
Die GreedyBestFirstSearch-Funktion implementiert den Greedy-Best-First-Suchalgorithmus. Es verwendet eine Prioritätswarteschlange, um Knoten basierend auf ihren heuristischen Werten zu speichern.
Der Algorithmus stellt zunächst den Startknoten in die Prioritätswarteschlange.
In jeder Iteration wird der Knoten mit der höchsten Priorität aus der Warteschlange entfernt und geprüft, ob es sich um den Zielknoten handelt.
Wenn der Zielknoten gefunden wird, wird die Meldung „Pfad gefunden!“ gedruckt. Andernfalls markiert der Algorithmus den aus der Warteschlange entfernten Knoten als besucht und stellt seine nicht besuchten Nachbarknoten in die Warteschlange.
Wenn die Prioritätswarteschlange leer wird und kein Zielknoten gefunden wird, wird die Meldung „Pfad existiert nicht!“ gedruckt.
Die Hauptfunktion demonstriert die Verwendung des Algorithmus, indem sie ein Diagramm erstellt, den Startknoten und den Zielknoten definiert und die Funktion „greedyBestFirstSearch“ aufruft.
Unsere Strategie zur Lösung dieses Problems erfordert die Verwendung einer heuristischen Funktion, die auf dem Konzept der Manhattan-Distanz basiert. Dieses Distanzmaß, manchmal auch Rolldistanz genannt, umfasst die Addition der horizontalen und vertikalen Abstände zwischen Knoten.
#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!
Dieser Code folgt einer ähnlichen Struktur wie Methode 1, verwendet jedoch einen benutzerdefinierten Komparator, CompareManhattanDistance, der die Manhattan-Distanzformel verwendet, um Knoten basierend auf ihrer geschätzten Entfernung zum Zielknoten zu vergleichen.
Die GreedyBestFirstSearch-Funktion implementiert den Greedy-Best-First-Suchalgorithmus mithilfe der Manhattan-Distanzheuristik.
Die Hauptfunktion demonstriert die Verwendung des Algorithmus, erstellt ein Diagramm, definiert den Startknoten und den Zielknoten und ruft die GreedyBestFirstSearch-Funktion auf.
In diesem Artikel untersuchen wir den gierigen Best-First-Suchalgorithmus und seine Implementierung in C++. Durch den Einsatz dieser Methoden können Programmierer effizient Pfade in Diagrammen finden und Optimierungsprobleme lösen. Die Wahl einer heuristischen Funktion, wie z. B. der euklidischen Distanz oder der Manhattan-Distanz, kann die Leistung des Algorithmus in verschiedenen Szenarien erheblich beeinflussen.
Das obige ist der detaillierte Inhalt vonImplementierung des Greedy-Best-First-Suchalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
