Implementierung des Greedy-Best-First-Suchalgorithmus in C++

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++.

Grammatik

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

Algorithmus

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.

Methode 1: Heuristische Funktion basierend auf der euklidischen Distanz

Beispiel

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

Ausgabe

Goal node reached!

Anleitung

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.

Methode 2: Heuristische Funktion basierend auf der Manhattan-Distanz

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.

Beispiel

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

Ausgabe

Goal node reached!

Anleitung

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.

Fazit

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!