Tìm kiếm hai chiều (Bidirectional Search) là kỹ thuật tìm kiếm chạy theo hai hướng. Nó hoạt động với hai quá trình tìm kiếm chạy đồng thời: một từ nguồn (source) đến đích (goal), và một từ đích ngược về nguồn theo hướng ngược lại. Trong trạng thái tối ưu, cả hai tìm kiếm sẽ gặp nhau ở giữa cấu trúc dữ liệu.
Thuật toán tìm kiếm hai chiều hoạt động trên đồ thị có hướng để tìm đường đi ngắn nhất giữa nút nguồn (nút ban đầu) và nút đích. Hai tìm kiếm bắt đầu từ vị trí của chúng và thuật toán dừng lại khi hai tìm kiếm gặp nhau tại một nút.
Tầm quan trọng của phương pháp hai chiều
- Là kỹ thuật nhanh hơn, cải thiện thời gian cần thiết để duyệt đồ thị.
- Hiệu quả khi nút bắt đầu và nút đích là duy nhất và được xác định rõ.
- Hệ số nhánh (branching factor) giống nhau cho cả hai hướng.
Đo lường hiệu suất
- Tính hoàn chỉnh (Completeness) - Bidirectional search hoàn chỉnh nếu BFS được dùng cho cả hai tìm kiếm.
- Tính tối ưu (Optimality) - Tối ưu nếu BFS được dùng và các đường đi có chi phí đồng nhất.
- Độ phức tạp thời gian và không gian - O(b^(d/2)) với b là hệ số nhánh, d là độ sâu.
Ví dụ code C++
#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;
}
Kết quả
Path Traversed by the algorithm 0 4 6 7 8 10 14