Thuật toán BFS 0-1

Giới thiệu

Thuật toán BFS 0-1, đúng như tên gọi của nó, là một cải tiến của thuật toán BFS. Tuy không quá khó để cài đặt, BFS 0-1 lại có thể giúp ta tối ưu hiệu quả trong một số bài toán lập trình thi đấu nhất định.

Đặt vấn đề

Trước khi tìm hiểu thêm về thuật toán BFS 0-1, mời bạn đọc xem qua bài toán sau đây.

Bài toán: https://www.spoj.com/problems/KATHTHI/

Tóm tắt:

Cho ma trận có kích thước

$R\times C$. Ta cần đi từ vị trí

$(0,0)$ đến vị trí

$(R-1,C-1)$. Ta có thể di chuyển theo 4 hướng sang các ô kề cạnh. Gọi

$(x,y)$ là toạ độ của ô hiện tại và

$(u,v)$ là toạ độ của ô đi tới. Nếu kí tự tại ô

$(x,y)$ giống kí tự tại ô

$(u,v)$ thì bước di chuyển đó tốn chi phí là

$0$, ngược lại thì chi phí là

$1$.

Yêu cầu tìm chi phí nhỏ nhất để đi từ ô

$(0,0)$ đến ô

$(R-1,C-1)$.

Input

• Dòng đầu tiên chứa số nguyên
  $t$ (
  $t\le 10$) là số bộ test.
• Mỗi bộ test chứa hai số nguyên
  $R(R\le 1000)$ và
  $C(C\le 1000)$ là số dòng và số cột của ma trận. Theo sau là
  $R$ xâu thể hiện ma trận đề bài.

Output

• Với mỗi bộ test, in ra chi phí nhỏ nhất để đi từ ô
  $(0,0)$ đến ô
  $(R-1,C-1)$.

Sample Input

1
5 5
abbbc
abacc
aaacc
aefci
cdgdd

Sample Output

2

Thuật toán "ngây thơ"

Với bài toán này, ta có thể xem mỗi ô là một đỉnh và mỗi bước đi là một cạnh trong đồ thị sau đó áp dụng thuật toán Dijkstra để tìm đường đi ngắn nhất.

Tuy nhiên, cách làm này không đem lại hiệu quả cao với độ phức tạp

$O(t\ast ((V+E)\log V))$. Trong đó

$V$ là số lượng đỉnh (

$R\times C$) và

$E$ là số cạnh trong đồ thị.

Lúc này, do trọng số cạnh chỉ là

$0$ hoặc

$1$, ta có thể dùng thuật toán BFS 0-1 để giải quyết bài toán trong

$O(t\ast (V+E))$.

Giải thích thuật toán

Thuận toán BFS 0-1 có thể được phát triển qua việc quan sát thuật toán Dijkstra cổ điển. Để thuận tiện cho việc cài đặt ta xem xét một bài toán tương tự:

Cho đồ thị

$G$ có

$V$ đỉnh và

$E$ cạnh. Mỗi cạnh chỉ có thể có trọng số

$0$ hoặc

$1$. Tìm đường đi ngắn nhất từ một đỉnh cho trước đến các đỉnh còn lại.

Để tìm khoảng cách nhỏ nhất từ một đỉnh đến các đỉnh còn lại, ta sử dụng thuật toán Dijkstra kết hợp cải tiến hàng chờ ưu tiên như sau:

void dijkstra(int s){
    //Gán giá trị ban đầu cho đường đi lớn nhỏ nhất đến các đỉnh
    memset(d, 0x3f, sizeof d);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    //Thêm đỉnh s được cho vào hàng đầu hàng đợi 
    q.push({0, s}); 
    d[s] = 0; 
    
    while (!q.empty()){
        //Lấy ra phần tử có giá trị nhỏ nhất trong hàng đợi
        pair<int, int> k = q.top();
        q.pop();
        if (k.first > d[k.second]) continue;
        for (pair<int, int> edge : g[k.second]){
            int node = edge.first;
            int weight = edge.second;
            //Xét điều kiện để đỉnh tới được tối ưu
            if (weight + k.first < d[node]){
                d[node] = weight + k.first;
                q.push({d[node], node});
            }
        }
    }
}

Ta có thể thấy được rằng ở mọi thời điểm, với mọi đỉnh

$u$ và

$v$ thuộc hàng chờ ưu tiên,

$|d_u-d_v|\le 1$. Do hàng chờ ưu tiên luôn lấy ra hết các giá trị

$d_u$ rồi mới tới

$d_u+1$ nên không thể tồn tại giá trị

$d_v\ge d_u+2$ khi

$d_u$ vẫn còn trong hàng chờ.

Qua đó, ta có thể không dùng đến hàng chờ ưu tiên mà vẫn có thể đảm bảo việc thăm các đỉnh theo thứ tự tăng dần

$d_u$ như trong thuật toán Dijkstra. Cụ thể hơn, nếu cạnh đang xét có trọng số là 0, ta sẽ ưu tiên đưa đỉnh tới thành đỉnh được xét kế tiếp.

Trong cài đặt, ta sẽ sử dụng cấu trúc dữ liệu deque. Với những cạnh trọng số 0, ta đưa đỉnh tới vào đầu deque (đỉnh được xét tiếp theo). Ngược lại, với những cạnh trọng số 1, ta đưa đỉnh vào cuối deque. Bằng cách cài đặt này, ta sẽ bảo toàn được thứ tự xét của các đỉnh trong đồ thị.

Thuật toán BFS 0-1 sử dụng deque như ta vừa mô tả có thể được minh hoạ như sau:

Cài đặt

Như đã đề cập ở trên, ta sử dụng cấu trúc dữ liệu deque để cài đặt thuật toán BFS 0-1

void bfs01(int s){
    //Gán giá trị ban đầu cho đường đi lớn nhỏ nhất đến các đỉnh
    memset(d, 0x3f, sizeof d); 
    deque<int> q; 
    //Thêm đỉnh s được cho vào hàng đầu hàng đợi
    q.push_front(s); 
    d[s] = 0;
    
    while (!q.empty()){
        //Lấy ra phần tử đứng đầu của hàng đợi
        int k = q.front();
        q.pop_front();
        for (pair<int, int> edge : g[k]){
            int node = edge.first;
            int weight = edge.second;
            //Xét điều kiện để đỉnh tới được tối ưu
            if (weight + d[k] < d[node]){
                d[node] = weight + d[k];
                //Nếu cạnh có trọng số 0 thì ta đưa đỉnh vào đầu hàng đợi
                if (weight == 0) 
                    q.push_front(node);
                // Nếu cạnh có trọng số 1 thì ta đưa đỉnh vào cuối hàng đợi
                else 
                    q.push_back(node);
            }
        }
    }
}

Đánh giá

Vì mỗi đỉnh sẽ chỉ được duyệt qua một lần nên độ phức tạp của thuật toán BFS 0-1 cài đặt như trên là

$O(V+E)$, nhanh hơn nhiều so với độ phức tạp

$O((V+E)\log V)$ của thuật toán Dijkstra khi đã cải tiến.

Luyện tập

• KATHTHI
• Labyrinth
• Olya and Energy Drink
• Spiral Maximum