Pelaksanaan Algoritma Carian Terbaik-Pertama Tamak dalam C++

Penyelesaian masalah yang baik dalam sains komputer sangat bergantung pada algoritma yang cekap seperti Greedy Best First Search (GBFS). GBFS telah mewujudkan kredibiliti sebagai penyelesaian terbaik untuk mencari laluan atau masalah pengoptimuman. Oleh itu, dalam artikel ini kita membincangkan GBFS secara mendalam sambil meneroka pelaksanaannya menggunakan C++.

Tatabahasa

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

Algoritma

Algoritma carian pertama terbaik yang tamak bertujuan untuk mencari laluan daripada nod permulaan yang diberikan kepada nod sasaran dalam graf. Berikut ialah langkah umum algoritma -

• Mulakan baris gilir keutamaan kosong.

• Letakkan nod permulaan ke dalam baris gilir keutamaan.

• Buat set kosong untuk menjejaki nod yang dilawati.

• Apabila barisan keutamaan tidak kosong -

• Buang giliran nod dengan keutamaan tertinggi daripada baris gilir.

• Jika nod yang ditamatkan giliran ialah nod sasaran, algoritma ditamatkan dan laluan ditemui.

• Jika tidak, tandakan nod dequeue sebagai dilawati.

• Masukkan semua nod jiran yang tidak dilawati bagi nod yang ditolak ke dalam baris gilir keutamaan.

• Jika baris gilir keutamaan menjadi kosong sebelum mencapai nod sasaran, tiada laluan wujud.

Kaedah 1: Fungsi heuristik berdasarkan jarak Euclidean

Contoh

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

Output

Goal node reached!

Arahan

Kod ini mengandungi dua elemen utama. Pertama, ia mengandungi takrif kelas Graf, yang mewakili struktur graf menggunakan senarai bersebelahan.

Kedua, ia memperkenalkan CompareEuclideanDistance - pembanding tersuai untuk menilai nod dengan menganggar jaraknya dari nod sasaran menggunakan formula jarak Euclidean.

Fungsi greedyBestFirstSearch melaksanakan algoritma carian pertama terbaik yang tamak. Ia menggunakan baris gilir keutamaan untuk menyimpan nod berdasarkan nilai heuristiknya.

Algoritma terlebih dahulu meletakkan nod permulaan ke dalam baris gilir keutamaan.

Dalam setiap lelaran, ia menafikan nod keutamaan tertinggi dan menyemak sama ada ia adalah nod sasaran.

Jika nod sasaran ditemui, "Mesej Laluan Ditemui!" Jika tidak, algoritma menandakan nod yang dinyah gilir sebagai dilawati dan memasukkan nod jiran yang tidak dilawati.

Jika baris gilir keutamaan menjadi kosong dan tiada nod sasaran ditemui, "Mesej tidak wujud!"

Fungsi utama menunjukkan penggunaan algoritma dengan mencipta graf, mentakrifkan nod permulaan dan nod sasaran, dan memanggil fungsi greedyBestFirstSearch.

Kaedah 2: Fungsi heuristik berdasarkan jarak Manhattan

Strategi kami untuk menyelesaikan masalah ini memerlukan penggunaan fungsi heuristik yang bergantung pada konsep jarak Manhattan. Ukuran jarak ini, kadangkala dipanggil jarak teksi, melibatkan penambahan jarak mendatar dan menegak antara nod.

Contoh

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

Output

Goal node reached!

Arahan

Kod ini mengikut struktur yang serupa dengan Kaedah 1, tetapi menggunakan pembanding tersuai, CompareManhattanDistance, yang menggunakan formula jarak Manhattan untuk membandingkan nod berdasarkan anggaran jaraknya ke nod sasaran.

Fungsi greedyBestFirstSearch melaksanakan algoritma carian pertama terbaik tamak menggunakan heuristik jarak Manhattan.

Fungsi utama menunjukkan penggunaan algoritma, mencipta graf, mentakrifkan nod permulaan dan nod sasaran, dan memanggil fungsi greedyBestFirstSearch.

Kesimpulan

Dalam artikel ini, kami meneroka algoritma carian terbaik pertama yang tamak dan pelaksanaannya dalam C++. Dengan menggunakan kaedah ini, pengaturcara boleh mencari laluan dalam graf dengan cekap dan menyelesaikan masalah pengoptimuman. Pilihan fungsi heuristik, seperti jarak Euclidean atau jarak Manhattan, boleh menjejaskan prestasi algoritma dengan ketara dalam senario yang berbeza.

Atas ialah kandungan terperinci Pelaksanaan Algoritma Carian Terbaik-Pertama Tamak dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!