ค้นหาแบบสองทิศทาง?

การค้นหาแบบสองทิศทาง เป็นเทคนิคการค้นหาที่ทำงานสองทาง ทำงานร่วมกับผู้ค้นหาสองคนที่ทำงานพร้อมกัน คนแรกจากแหล่งที่มาด้วยเป้าหมาย และอีกคนหนึ่งจากเป้าหมายหนึ่งไปยังอีกแหล่งที่มาในทิศทางย้อนกลับ ในสถานะที่เหมาะสม การค้นหาทั้งสองจะพบกันที่กึ่งกลางของโครงสร้างข้อมูล

อัลกอริทึมการค้นหาแบบสองทิศทางทำงานบนกราฟกำกับเพื่อค้นหาเส้นทางที่สั้นที่สุดระหว่างแหล่งที่มา (โหนดเริ่มต้น) ไปยังโหนดเป้าหมาย การค้นหาทั้งสองจะเริ่มจากตำแหน่งที่เกี่ยวข้องกัน และอัลกอริทึมจะหยุดเมื่อการค้นหาทั้งสองมาบรรจบกันที่โหนด

ความสำคัญของแนวทางแบบสองทิศทาง − เป็นเทคนิคที่เร็วกว่า และปรับปรุงระยะเวลาที่จำเป็นสำหรับการสำรวจกราฟ

วิธีการนี้มีประสิทธิภาพในกรณีที่โหนดเริ่มต้นและโหนดเป้าหมายไม่ซ้ำกันและกำหนดไว้ ปัจจัยการแตกแขนงจะเท่ากันทั้งสองทิศทาง

การวัดประสิทธิภาพ

• ความสมบูรณ์ − การค้นหาแบบสองทิศทางจะสมบูรณ์หากใช้ BFS ในการค้นหาทั้งสองแบบ

• ความเหมาะสม − เป็นการดีที่สุดหากใช้ BFS สำหรับการค้นหาและเส้นทางมีราคาเท่ากัน

• ความซับซ้อนของเวลาและอวกาศ − ความซับซ้อนของเวลาและพื้นที่คือ O(b^{d/2})

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Graph {
   int V;
   list<int> *adj;
   public:
      Graph(int V);
      int isIntersecting(bool *s_visited, bool *t_visited);
      void addEdge(int u, int v);
      void printPath(int *s_parent, int *t_parent, int s,
      int t, int intersectNode);
      void BFS(list<int> *queue, bool *visited, int *parent);
      int biDirSearch(int s, int t);
};
Graph::Graph(int V) {
   this->V = V;
   adj = new list<int>[V];
};
void Graph::addEdge(int u, int v) {
   this->adj[u].push_back(v);
   this->adj[v].push_back(u);
};
void Graph::BFS(list<int> *queue, bool *visited,
int *parent) {
   int current = queue->front();
   queue->pop_front();
   list<int>::iterator i;
   for (i=adj[current].begin();i != adj[current].end();i++) {
      if (!visited[*i]) {
         parent[*i] = current;
         visited[*i] = true;
         queue->push_back(*i);
      }
   }
};
int Graph::isIntersecting(bool *s_visited, bool *t_visited) {
   int intersectNode = -1;
   for(int i=0;i<V;i++) {
      if(s_visited[i] && t_visited[i])
         return i;
   }
   return -1;
};
void Graph::printPath(int *s_parent, int *t_parent,
int s, int t, int intersectNode) {
   vector<int> path;
   path.push_back(intersectNode);
   int i = intersectNode;
   while (i != s) {
      path.push_back(s_parent[i]);
      i = s_parent[i];
   }
   reverse(path.begin(), path.end());
   i = intersectNode;
   while(i != t) {
      path.push_back(t_parent[i]);
      i = t_parent[i];
   }
   vector<int>::iterator it;
   cout<<"Path Traversed by the algorithm\n";
   for(it = path.begin();it != path.end();it++)
      cout<<*it<<" ";
      cout<<"\n";
};
int Graph::biDirSearch(int s, int t) {
   bool s_visited[V], t_visited[V];
   int s_parent[V], t_parent[V];
   list<int> s_queue, t_queue;
   int intersectNode = -1;
   for(int i=0; i<V; i++) {
      s_visited[i] = false;
      t_visited[i] = false;
   }
   s_queue.push_back(s);
   s_visited[s] = true;
   s_parent[s]=-1;
   t_queue.push_back(t);
   t_visited[t] = true;
   t_parent[t] = -1;
   while (!s_queue.empty() && !t_queue.empty()) {
      BFS(&s_queue, s_visited, s_parent);
      BFS(&t_queue, t_visited, t_parent);
      intersectNode = isIntersecting(s_visited, t_visited);
      if(intersectNode != -1) {
         cout << "Path exist between " << s << " and "
         << t << "\n";
         cout << "Intersection at: " << intersectNode << "\n";
         printPath(s_parent, t_parent, s, t, intersectNode);
         exit(0);
      }
   }
   return -1;
}
int main() {
   int n=15;
   int s=0;
   int t=14;
   Graph g(n);
   g.addEdge(0, 4);
   g.addEdge(1, 4);
   g.addEdge(2, 5);
   g.addEdge(3, 5);
   g.addEdge(4, 6);
   g.addEdge(5, 6);
   g.addEdge(6, 7);
   g.addEdge(7, 8);
   g.addEdge(8, 9);
   g.addEdge(8, 10);
   g.addEdge(9, 11);
   g.addEdge(9, 12);
   g.addEdge(10, 13);
   g.addEdge(10, 14);
   if (g.biDirSearch(s, t) == -1)
      cout << "Path don't exist between "
      << s << " and " << t << "\n";
   return 0;
}

ผลลัพธ์

Path Traversed by the algorithm
0 4 6 7 8 10 14