Bài 25: Robot hút bụi đi khắp nhà như thế nào? BFS và bài toán phủ kín

Robot hút bụi chạy quanh nhà, len qua gầm bàn, tránh chân ghế rồi tự quay về chỗ sạc. Nó làm sao biết chỗ nào đã lau, chỗ nào chưa? Và vì sao robot đời mới dọn nhanh hơn hẳn robot đời đầu? Câu trả lời nằm ở một thuật toán bạn có thể đã học: BFS.

Bài thứ hai mươi lăm của chuyên mục "Thuật toán trong đời sống": robot hút bụi, BFS trên lưới và bài toán phủ kín.

1. Từ đi ngẫu nhiên đến vẽ bản đồ

• Theo hồ sơ iRobot gửi Ủy ban Chứng khoán Mỹ (SEC), chiếc robot hút bụi Roomba đầu tiên ra đời năm 2002.
• Các thế hệ Roomba đầu tiên không có bản đồ: robot đi xoắn ốc, men theo tường, va vào vật cản thì quay một góc ngẫu nhiên rồi đi tiếp.
• Năm 2015, iRobot giới thiệu Roomba 980 với công nghệ vSLAM (định vị và lập bản đồ bằng camera) – theo hãng, đây là lần đầu công nghệ này có trên một sản phẩm tiêu dùng. Một số hãng khác như Neato dùng cảm biến laser quay tròn để quét phòng.

Bên cạnh câu chuyện công nghệ là câu chuyện kinh doanh: sau khi thương vụ Amazon mua lại iRobot bị hủy năm 2024, iRobot gặp khó khăn tài chính. Tháng 12/2025, công ty công bố kế hoạch tái cấu trúc theo Chương 11 Luật Phá sản Mỹ; ngày 23/1/2026, iRobot hoàn tất giao dịch dưới sự giám sát của tòa án và trở thành công ty tư nhân thuộc Picea – nhà sản xuất đối tác của họ.

2. Mô hình bài toán: căn phòng là một lưới ô vuông

Chia sàn nhà thành các ô vuông: ô "#" là tường hoặc đồ đạc, ô "." là sàn cần lau. Robot mỗi bước đi sang một ô kề (lên, xuống, trái, phải). Mục tiêu: đi qua mọi ô sàn với ít bước nhất. Đây là bài toán phủ kín (coverage path planning) – một hướng nghiên cứu lớn của ngành robot.

3. Chiến lược tham lam: luôn đi tới ô bẩn gần nhất

Khi đã có bản đồ, robot có thể dùng BFS (tìm kiếm theo chiều rộng) để tìm ô chưa lau gần nhất, đi tới đó, rồi lặp lại. Ta so sánh với robot "đời đầu" chọn bừa một hướng ở mỗi bước:

Robot lau nhà: BFS tham lam và đi ngẫu nhiên

#include <bits/stdc++.h>
using namespace std;
vector<string> room = {"#########",
                       "#R...#..#",
                       "#.##.#..#",
                       "#....#..#",
                       "#.##....#",
                       "#.......#",
                       "#########"};      // '#': tường/đồ đạc, '.': sàn cần lau
int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
set<pair<int,int>> dirty;
// BFS tìm ô bẩn gần nhất, trả về số bước và cập nhật vị trí
int goNearest(pair<int,int>& pos){
    map<pair<int,int>, int> dist; queue<pair<int,int>> q;
    dist[pos] = 0; q.push(pos);
    while(!q.empty()){
        auto [r, c] = q.front(); q.pop();
        if(dirty.count({r, c})){ pos = {r, c}; return dist[{r, c}]; }
        for(int k = 0; k < 4; k++){
            int nr = r + dr[k], nc = c + dc[k];
            if(room[nr][nc] != '#' && !dist.count({nr, nc})){ dist[{nr, nc}] = dist[{r, c}] + 1; q.push({nr, nc}); }
        }
    }
    return 0;
}
int main(){
    pair<int,int> start;
    for(int r = 0; r < (int)room.size(); r++)
        for(int c = 0; c < (int)room[r].size(); c++){
            if(room[r][c] == 'R') start = {r, c};
            if(room[r][c] != '#') dirty.insert({r, c});
        }
    auto all = dirty; int cells = dirty.size(), steps = 0;
    pair<int,int> pos = start; dirty.erase(pos);
    while(!dirty.empty()){ steps += goNearest(pos); dirty.erase(pos); }   // tham lam: ô bẩn gần nhất
    printf("So o san: %d\nRobot di: %d buoc\nIt nhat can: %d buoc (moi buoc lau them 1 o)\n", cells, steps, cells - 1);
    // So sánh: robot đi ngẫu nhiên
    long long x = 12345; int rnd = 0; dirty = all; pos = start; dirty.erase(pos);
    while(!dirty.empty()){
        x = (x * 1103515245 + 12345) % 2147483648LL;
        vector<pair<int,int>> opts;
        for(int k = 0; k < 4; k++){ int nr = pos.first + dr[k], nc = pos.second + dc[k]; if(room[nr][nc] != '#') opts.push_back({nr, nc}); }
        pos = opts[(x >> 16) % opts.size()]; rnd++; dirty.erase(pos);
    }
    printf("Robot di ngau nhien: %d buoc\n", rnd);
}

from collections import deque

room = ["#########",
        "#R...#..#",
        "#.##.#..#",
        "#....#..#",
        "#.##....#",
        "#.......#",
        "#########"]                          # '#': tường/đồ đạc, '.': sàn cần lau, 'R': robot
H, W = len(room), len(room[0])
pos = next((r, c) for r in range(H) for c in range(W) if room[r][c] == "R")
dirty = {(r, c) for r in range(H) for c in range(W) if room[r][c] in ".R"}

def bfs(start):
    # Tìm ô bẩn gần nhất bằng BFS, trả về (ô đó, số bước)
    dist = {start: 0}; q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) in dirty: return (r, c), dist[(r, c)]
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nr, nc = r + dr, c + dc
            if room[nr][nc] != "#" and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1; q.append((nr, nc))
    return None, 0

start, all_dirty = pos, set(dirty)
cells, steps = len(dirty), 0
dirty.discard(pos)
while dirty:
    target, d = bfs(pos)                      # tham lam: luôn đi tới ô bẩn gần nhất
    steps += d; pos = target; dirty.discard(pos)
print("So o san:", cells)
print("Robot di:", steps, "buoc")
print("It nhat can:", cells - 1, "buoc (moi buoc lau them 1 o)")

# So sánh: robot đi ngẫu nhiên (chọn bừa một hướng đi được ở mỗi bước)
x, pos, dirty, rnd = 12345, start, set(all_dirty) - {start}, 0
while dirty:
    x = (x * 1103515245 + 12345) % 2**31
    opts = [(pos[0] + dr, pos[1] + dc) for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0))
            if room[pos[0] + dr][pos[1] + dc] != "#"]
    pos = opts[(x >> 16) % len(opts)]; rnd += 1; dirty.discard(pos)
print("Robot di ngau nhien:", rnd, "buoc")

Kết quả chạy:

So o san: 28
Robot di: 36 buoc
It nhat can: 27 buoc (moi buoc lau them 1 o)
Robot di ngau nhien: 435 buoc

Robot có bản đồ chỉ cần 36 bước để lau 28 ô – gần với giới hạn tốt nhất có thể là 27 bước. Robot đi ngẫu nhiên tốn tới 435 bước, gấp khoảng 12 lần, vì nó liên tục quay lại những ô đã sạch.

Có thể tối ưu tuyệt đối không? Tìm đường đi ngắn nhất qua mọi ô là bài toán khó, họ hàng với bài toán người du lịch (TSP – xem Bài 7 của chuyên mục). Vì vậy robot thật dùng các chiến lược "đủ tốt": chia phòng thành từng vùng rồi đi theo đường zíc zắc trong mỗi vùng, kết hợp tìm đường để di chuyển giữa các vùng.

4. Robot thật còn phải lo những gì?

• Định vị: robot phải biết mình đang ở đâu trên bản đồ, dù bánh xe có thể trượt.
• Vật cản thay đổi: ghế bị dời, đồ chơi nằm giữa nhà – bản đồ phải được cập nhật liên tục.
• Pin: khi gần hết pin, robot dùng thuật toán tìm đường để quay về đế sạc, rồi tiếp tục từ chỗ dở dang.

5. Bạn học được gì từ đây?

• BFS trên lưới là kỹ thuật nền tảng, xuất hiện rất nhiều trong đề thi HSG.
• Có thông tin (bản đồ) giúp thuật toán hiệu quả hơn hẳn so với đi mò.
• Khi bài toán quá khó để giải tối ưu, chiến lược tham lam hợp lý thường cho kết quả rất tốt.

Bài tập luyện tập

• CSES – Counting Rooms (đếm số phòng bằng BFS/DFS trên lưới)
• CSES – Labyrinth (tìm đường ngắn nhất trong mê cung)
• Sửa code để robot ưu tiên lau theo hàng (zíc zắc) khi có nhiều ô bẩn cùng khoảng cách. Số bước thay đổi thế nào?

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 26: Xếp hàng vào thùng và chọn đơn cho xe giao hàng – Bài toán cái túi và bài toán xếp thùng

Đọc tiếp: xếp thùng & cái túi →

← Bài trước: bàn phím & cây TrieXem tất cả 27 bài →

Nguồn tham khảo

• iRobot – Hồ sơ 8-K gửi SEC (14/12/2025)
• iRobot (16/09/2015) – iRobot Enters the Smart Home with Roomba 980
• iRobot (23/01/2026) – iRobot Completes Court-Supervised Transaction with Picea
• Popular Science – Laser-Guided Vacuum Could Best the Roomba
• Galceran & Carreras (2013) – A survey on coverage path planning for robotics