Bài 26.3: Bài toán tìm đường đi tối ưu trong C++

Chào mừng trở lại với chuỗi bài viết về C++! Hôm nay, chúng ta sẽ cùng nhau đào sâu vào một chủ đề cực kỳ hấp dẫn và có ứng dụng rộng rãi trong nhiều lĩnh vực: Bài toán tìm đường đi tối ưu.

Bài toán này không chỉ đơn thuần là "tìm đường", mà còn là tìm con đường tốt nhất dựa trên một tiêu chí nào đó. Tiêu chí "tốt nhất" này có thể là:

  • Đường đi ngắn nhất (ít bước nhất).
  • Đường đi có tổng chi phí nhỏ nhất (ví dụ: chi phí di chuyển, thời gian, năng lượng tiêu thụ).
  • Đường đi an toàn nhất, nhanh nhất, v.v.

Chúng ta thấy bài toán này ở khắp mọi nơi: từ các ứng dụng bản đồ chỉ đường (Google Maps, Grab), trong game (di chuyển của nhân vật, kẻ địch), trong logistic (lập kế hoạch vận chuyển hàng hóa), hay thậm chí là trong thiết kế mạch điện tử.

Về cơ bản, bài toán tìm đường đi tối ưu thường được mô hình hóa trên một đồ thị (graph), nơi các địa điểm là các đỉnh (vertices/nodes) và các con đường nối giữa chúng là các cạnh (edges). Các cạnh này có thể có trọng số (weights) biểu thị chi phí hoặc khoảng cách.

Các loại bài toán tìm đường đi và Thuật toán

Có nhiều biến thể của bài toán tìm đường đi, tùy thuộc vào cấu trúc đồ thị và tiêu chí tối ưu:

  1. Tìm đường đi ngắn nhất trên đồ thị không trọng số: Mục tiêu là tìm đường đi có số lượng cạnh ít nhất. Thuật toán phổ biến nhất cho loại này là Tìm kiếm theo chiều rộng (Breadth-First Search - BFS).
  2. Tìm đường đi ngắn nhất trên đồ thị có trọng số không âm: Mục tiêu là tìm đường đi có tổng trọng số của các cạnh là nhỏ nhất. Thuật toán kinh điển là Dijkstra.
  3. Tìm đường đi ngắn nhất trên đồ thị có trọng số (bao gồm cả trọng số âm): Phức tạp hơn, cần thuật toán như Bellman-Ford (hoặc Floyd-Warshall cho tất cả các cặp đỉnh).
  4. Tìm đường đi tối ưu có sử dụng thông tin heuristic: Các thuật toán như A* (A-Star) sử dụng thông tin ước lượng (heuristic) về khoảng cách từ điểm hiện tại đến đích để tìm đường đi hiệu quả hơn, đặc biệt phổ biến trong các bài toán không gian 2D/3D như tìm đường trên bản đồ hoặc trong game.

Trong phạm vi bài viết này, chúng ta sẽ tập trung vào trường hợp phổ biến và dễ tiếp cận nhất khi mới bắt đầu: Tìm đường đi ngắn nhất trên một ma trận (grid) không trọng số, sử dụng thuật toán BFS. Ma trận là một dạng đồ thị đặc biệt, nơi mỗi ô là một đỉnh và các ô lân cận (trên, dưới, trái, phải) được nối với nhau bằng các cạnh không trọng số.

Tìm đường đi ngắn nhất trên Ma trận bằng BFS

Hãy tưởng tượng một ma trận 2D đại diện cho một khu vực, với một số ô là "chướng ngại vật" (không đi qua được). Chúng ta muốn tìm đường đi ngắn nhất (ít bước nhất) từ một điểm bắt đầu đến một điểm kết thúc.

Tại sao BFS lại phù hợp? BFS hoạt động bằng cách khám phá các đỉnh "gần" điểm bắt đầu nhất trước, theo từng lớp. Nó giống như việc thả một viên đá xuống nước và nhìn các gợn sóng lan tỏa. Gợn sóng đầu tiên chạm tới điểm nào thì đó chính là đường đi ngắn nhất (về số bước) đến điểm đó.

Để triển khai BFS cho bài toán này, chúng ta cần:

  • Một hàng đợi (queue) để lưu trữ các ô (đỉnh) cần thăm.
  • Một cách để đánh dấu các ô đã thăm để tránh lặp lại và đi vào vòng lặp vô hạn.
  • Một cách để lưu trữ đường đi hoặc thông tin để tái tạo đường đi sau khi tìm thấy đích. Chúng ta có thể lưu trữ ô "cha" (ô mà từ đó ta đi đến ô hiện tại) cho mỗi ô.
Cấu trúc dữ liệu cần thiết
  • grid: Ma trận biểu diễn bản đồ (ví dụ: vector<vector<char>>).
  • visited: Ma trận cùng kích thước để đánh dấu các ô đã thăm (vector<vector<bool>>).
  • parent: Ma trận cùng kích thước để lưu trữ tọa độ ô "cha" (vector<vector<pair<int, int>>>). parent[r][c] sẽ lưu tọa độ (pr, pc) của ô mà từ đó ta đi đến (r, c).
Các bước của thuật toán BFS
  1. Khởi tạo hàng đợi, đánh dấu tất cả các ô chưa thăm (visited là false), và đặt ô cha ban đầu là một giá trị đặc biệt.
  2. Đưa điểm bắt đầu vào hàng đợi, đánh dấu là đã thăm.
  3. Trong khi hàng đợi chưa rỗng:
    • Lấy một ô từ đầu hàng đợi.
    • Nếu ô đó là điểm kết thúc, ta đã tìm thấy đường đi ngắn nhất. Dừng thuật toán.
    • Duyệt qua các ô lân cận (trên, dưới, trái, phải) của ô hiện tại:
      • Kiểm tra xem ô lân cận có hợp lệ không (nằm trong ma trận, không phải chướng ngại vật, chưa thăm).
      • Nếu hợp lệ: Đánh dấu là đã thăm, lưu ô hiện tại làm ô cha của ô lân cận, và đưa ô lân cận vào cuối hàng đợi.
  4. Nếu hàng đợi rỗng mà chưa tìm thấy đích, nghĩa là không có đường đi.

Sau khi tìm thấy đích, ta có thể tái tạo đường đi bằng cách đi ngược từ điểm kết thúc theo các con trỏ "cha" cho đến khi về đến điểm bắt đầu.

Ví dụ minh họa bằng C++

Chúng ta sẽ implement bài toán tìm đường đi ngắn nhất trên một ma trận đơn giản.

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // For pair
#include <tuple>   // For tuple (optional, can use pair or struct)
#include <algorithm> // For reverse

// Định nghĩa hướng di chuyển: Trên, Dưới, Trái, Phải
int dr[] = {-1, 1, 0, 0}; // Thay đổi hàng: -1 (lên), 1 (xuống), 0 (ngang)
int dc[] = {0, 0, -1, 1}; // Thay đổi cột: 0 (ngang), -1 (trái), 1 (phải)

// Hàm kiểm tra xem một ô có hợp lệ để đi tới không
bool isValid(int r, int c, int rows, int cols, const vector<vector<char>>& grid, const vector<vector<bool>>& visited) {
    // Kiểm tra nằm trong biên
    if (r < 0 || r >= rows || c < 0 || c >= cols) {
        return false;
    }
    // Kiểm tra không phải chướng ngại vật ('#') và chưa được thăm
    if (grid[r][c] == '#' || visited[r][c]) {
        return false;
    }
    return true;
}

// Hàm thực hiện BFS tìm đường đi
// Trả về vector các tọa độ của đường đi ngắn nhất (bao gồm start và end)
// Trả về vector rỗng nếu không tìm thấy đường đi
vector<pair<int, int>> bfs(const vector<vector<char>>& grid, pair<int, int> start, pair<int, int> end) {
    int rows = grid.size();
    int cols = grid[0].size();

    // Kiểm tra điểm bắt đầu và kết thúc có hợp lệ không
    if (start.first < 0 || start.first >= rows || start.second < 0 || start.second >= cols ||
        end.first < 0 || end.first >= rows || end.second < 0 || end.second >= cols ||
        grid[start.first][start.second] == '#' || grid[end.first][end.second] == '#') {
        cerr << "Điểm bắt đầu hoặc kết thúc không hợp lệ!" << endl;
        return {}; // Trả về vector rỗng
    }

    // Ma trận theo dõi các ô đã thăm
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    // Ma trận lưu trữ ô cha để tái tạo đường đi
    // Lưu {pr, pc} của ô cha tại {r, c}
    vector<vector<pair<int, int>>> parent(rows, vector<pair<int, int>>(cols, {-1, -1})); // {-1,-1} là giá trị ban đầu

    // Hàng đợi cho BFS. Lưu trữ tọa độ {r, c}
    queue<pair<int, int>> q;

    // Bắt đầu BFS
    q.push(start);
    visited[start.first][start.second] = true;
    // parent của start không cần thiết, sẽ dừng khi reconstruct

    // Vòng lặp BFS chính
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        // Nếu đến đích, dừng lại
        if (curr.first == end.first && curr.second == end.second) {
            // Đã tìm thấy đường đi, tiến hành tái tạo
            vector<pair<int, int>> path;
            pair<int, int> step = end;
            while (step.first != -1 && step.second != -1) { // Đi ngược lại từ đích đến khi gặp {-1,-1} (start)
                path.push_back(step);
                step = parent[step.first][step.second];
            }
            reverse(path.begin(), path.end()); // Đảo ngược để có đường đi từ start đến end
            return path;
        }

        // Duyệt qua 4 hướng lân cận
        for (int i = 0; i < 4; ++i) {
            int nextR = curr.first + dr[i];
            int nextC = curr.second + dc[i];

            // Kiểm tra ô lân cận có hợp lệ không
            if (isValid(nextR, nextC, rows, cols, grid, visited)) {
                // Nếu hợp lệ, đánh dấu đã thăm, lưu ô cha và đưa vào hàng đợi
                visited[nextR][nextC] = true;
                parent[nextR][nextC] = curr; // Lưu lại ô hiện tại là cha của ô kế tiếp
                q.push({nextR, nextC});
            }
        }
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy đích
    return {}; // Trả về vector rỗng
}

int main() {
    // Minh họa ma trận
    // '.' là đường đi trống, '#' là chướng ngại vật, 'S' là bắt đầu, 'E' là kết thúc
    vector<vector<char>> grid = {
        {'S', '.', '.', '.', '#', '.'},
        {'.', '#', '.', '#', '.', '.'},
        {'.', '#', '.', '.', '.', '.'},
        {'.', '.', '.', '#', '#', '.'},
        {'#', '.', '.', '.', '.', 'E'}
    };

    pair<int, int> start = {0, 0}; // Tọa độ của 'S'
    pair<int, int> end = {4, 5};   // Tọa độ của 'E'

    cout << "Tim duong di tu (" << start.first << "," << start.second << ") den (" << end.first << "," << end.second << ")" << endl;

    // Gọi hàm BFS để tìm đường đi
    vector<pair<int, int>> path = bfs(grid, start, end);

    // In kết quả
    if (!path.empty()) {
        cout << "Tim thay duong di ngan nhat:" << endl;
        for (size_t i = 0; i < path.size(); ++i) {
            cout << "(" << path[i].first << "," << path[i].second << ")";
            if (i < path.size() - 1) {
                cout << " -> ";
            }
        }
        cout << endl;
        cout << "Do dai duong di (so buoc): " << path.size() - 1 << endl; // Số bước = số đỉnh - 1
    } else {
        cout << "Khong tim thay duong di." << endl;
    }

    return 0;
}
Giải thích mã C++
  • Header Files: Chúng ta sử dụng <iostream> cho nhập xuất, <vector> cho ma trận, <queue> cho hàng đợi BFS, <utility> cho pair (lưu trữ tọa độ), <tuple> có thể dùng nhưng pair gọn hơn cho tọa độ 2D, và <algorithm> cho reverse khi tái tạo đường đi.
  • dr, dc arrays: Đây là hai mảng đơn giản giúp chúng ta dễ dàng tính toán tọa độ của 4 ô lân cận (trên, dưới, trái, phải) từ ô hiện tại (r, c). (r + dr[i], c + dc[i]) sẽ cho tọa độ ô lân cận thứ i.
  • isValid function: Một hàm tiện ích để kiểm tra xem một ô với tọa độ (r, c) có thể được thăm hay không. Nó kiểm tra 3 điều kiện: có nằm trong ranh giới ma trận không, có phải là chướng ngại vật (#) không, và đã được thăm chưa.
  • bfs function: Đây là trái tim của thuật toán.
    • Nó nhận ma trận grid, điểm bắt đầu start, và điểm kết thúc end.
    • visited: Ma trận boolean đánh dấu các ô đã vào hàng đợi (đã thăm).
    • parent: Ma trận pair<int, int> lưu tọa độ của ô trước đó trên đường đi ngắn nhất. Đây là mấu chốt để tái tạo đường đi sau này. Giá trị {-1, -1} được dùng để đánh dấu ô bắt đầu (không có cha).
    • q: queue lưu trữ các ô cần xử lý.
    • Bắt đầu bằng cách đẩy start vào queue và đánh dấu đã thăm.
    • Vòng while (!q.empty()) là vòng lặp BFS chính. Lấy ô hiện tại, kiểm tra xem nó có phải là đích không.
    • Nếu là đích, ta dùng vòng while (step.first != -1) để đi ngược từ end về start theo parent và lưu vào vector path. Sau đó, đảo ngược vector này và trả về.
    • Nếu không phải đích, duyệt qua 4 hướng lân cận. Với mỗi lân cận hợp lệ (isValid trả về true), ta đánh dấu đã thăm, lưu curr làm cha của nó (parent[nextR][nextC] = curr;), và đẩy nó vào hàng đợi.
    • Nếu hàng đợi rỗng mà chưa tìm thấy đích (vòng while kết thúc), nghĩa là không có đường đi, hàm trả về vector rỗng.
  • main function:
    • Tạo một ma trận ví dụ.
    • Định nghĩa tọa độ start và end.
    • Gọi hàm bfs.
    • Kiểm tra kết quả trả về. Nếu vector path không rỗng, in ra đường đi. Nếu rỗng, thông báo không tìm thấy đường đi.

Mở rộng và các thuật toán khác

Như đã đề cập, BFS chỉ là một trong những thuật toán tìm đường đi.

  • Nếu các ô có "chi phí" khác nhau để đi qua (ví dụ: đi qua bùn lầy tốn 2 chi phí, đi qua đường lát đá tốn 1 chi phí), bài toán trở thành tìm đường đi có tổng chi phí nhỏ nhất trên đồ thị có trọng số. Lúc này, bạn cần sử dụng Dijkstra. Dijkstra sử dụng một priority queue (hàng đợi ưu tiên) để luôn luôn thăm ô chưa thăm có chi phí tích lũy từ điểm bắt đầu là nhỏ nhất.
  • Đối với các bài toán lớn hơn và có thông tin ước lượng về khoảng cách đến đích (heuristic), thuật toán A* thường là lựa chọn tối ưu. A* kết hợp chi phí thực tế đã đi được (từ start đến điểm hiện tại) với chi phí ước lượng còn lại (từ điểm hiện tại đến end) để ưu tiên khám phá các đường có vẻ hứa hẹn hơn.

Comments

There are no comments at the moment.