द्विदिशात्मक खोज (Bidirectional Search) एल्गोरिदम C++ में

द्विदिशात्मक खोज क्या है?

द्विदिशात्मक खोज (Bidirectional Search) एक खोज तकनीक है जो दो दिशाओं में चलती है। यह दो खोजों के साथ काम करती है जो एक साथ चलती हैं: पहली स्रोत (source) से लक्ष्य (goal) तक और दूसरी लक्ष्य से स्रोत तक पीछे की दिशा में। एक आदर्श स्थिति में, दोनों खोजें डेटा संरचना के बीच में मिलती हैं।

द्विदिशात्मक खोज एल्गोरिदम एक डायरेक्टेड ग्राफ पर काम करता है ताकि स्रोत (प्रारंभिक नोड) से लक्ष्य नोड तक का सबसे छोटा पथ ढूंढा जा सके। दोनों खोजें अपने-अपने स्थानों से शुरू होती हैं और एल्गोरिदम तब रुकता है जब दोनों खोजें एक नोड पर मिलती हैं।

द्विदिशात्मक दृष्टिकोण का महत्व

• यह एक तेज़ तकनीक है
• ग्राफ को पार करने के लिए आवश्यक समय की मात्रा में सुधार करती है

यह दृष्टिकोण उस मामले में कुशल है जब प्रारंभिक नोड और लक्ष्य नोड यूनिक और परिभाषित हों, और दोनों दिशाओं के लिए ब्रांचिंग फैक्टर समान हो।

प्रदर्शन माप

• पूर्णता (Completeness) - यदि दोनों खोजों में BFS उपयोग किया जाए तो द्विदिशात्मक खोज पूर्ण होती है
• इष्टतमता (Optimality) - यदि खोज के लिए BFS उपयोग किया जाए और पथों की लागत समान हो तो यह इष्टतम होती है
• समय और स्थान जटिलता - O(b^{d/2}) जहां b ब्रांचिंग फैक्टर है और d गहराई है

उदाहरण

#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();
    for (auto 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) {
    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];
    }
    cout << "Path Traversed by the algorithm\n";
    for(auto 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

लाभ

• मानक BFS/DFS की तुलना में बहुत तेज़
• बड़े ग्राफ में मेमोरी उपयोग कम करता है
• सबसे छोटा पथ ढूंढने के लिए आदर्श