Nguyên lý hoạt động

Thuật toán A* sử dụng công thức sau để tính mức độ ưu tiên của các nút:

f(n) = g(n) + h(n)

• f(n): Tổng mức độ ưu tiên của nút n, biểu thị chi phí ước lượng từ điểm bắt đầu thông qua nút n đến đích.
• g(n): Chi phí thực tế từ điểm bắt đầu đến nút n.
• h(n): Chi phí ước lượng heuristic từ nút n đến điểm đích.

Tâm điểm của thuật toán A* là chọn nút có giá trị f(n) thấp nhất để mở rộng, giúp đảm bảo tính chính xác đồng thời cải thiện hiệu suất.

Hàm heuristic (hàm ước lượng)

Hàm h(n) quyết định hiệu quả và độ chính xác của thuật toán:

• Đồng nhất (Consistency): Nếu h(n) thỏa mãn bất đẳng thức tam giác, tức là h(n) ≤ c(n,n′) + h(n′), thuật toán sẽ đảm bảo tối ưu.
• Các hàm heuristic phổ biến:
• Khoảng cách Manhattan (phù hợp với bản đồ lưới):

h(n) = |x1 − x2| + |y1 − y2|

• Khoảng cách Euclid (phù hợp với bản đồ hình học).
• Hàm heuristic tùy chỉnh: Được thiết kế cho các trường hợp cụ thể.

Quy trình thuật toán

Khởi tạo:

• Thêm điểm khởi đầu vào danh sách mở (Open List).
• Danh sách đóng (Closed List) rỗng.

Tìm kiếm lặp lại:

1. Chọn nút n có giá trị f(n) nhỏ nhất từ danh sách mở.
2. Nếu n là nút đích, dừng và trả về đường đi.
3. Di chuyển nút n từ danh sách mở sang danh sách đóng.
4. Mở rộng tất cả các nút láng giềng của nút n:

• Nếu láng giềng không nằm trong danh sách đóng:
• Tính g(n), h(n) và f(n) của láng giềng.
• Nếu láng giềng không nằm trong danh sách mở, thêm nó vào danh sách mở.
• Nếu láng giềng đã tồn tại trong danh sách mở nhưng g(n) mới tốt hơn, cập nhật giá trị của láng giềng.

Trả về kết quả:

• Nếu danh sách mở trống, nghĩa là không có giải pháp.
• Ngược lại, trả về đường đi.

Thực hiện bằng mã code

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
using namespace std;

// Định nghĩa cấu trúc nút
struct Vertex {
    int row, col;           // Toạ độ
    double costSoFar, estimate, totalCost;
    Vertex* predecessor;

    Vertex(int row, int col, double costSoFar = 0, double estimate = 0, Vertex* predecessor = nullptr)
        : row(row), col(col), costSoFar(costSoFar), estimate(estimate), totalCost(costSoFar + estimate), predecessor(predecessor) {}

    bool operator<(const Vertex& other) const {
        return totalCost > other.totalCost; // Hàng đợi ưu tiên theo tổng chi phí
    }
};

// Hàm heuristic: Khoảng cách Manhattan
double estimateCost(int row1, int col1, int row2, int col2) {
    return abs(row1 - row2) + abs(col1 - col2);
}

// Kiểm tra điểm có nằm trong lưới hay không
bool isWithinBounds(int row, int col, int rows, int cols) {
    return row >= 0 && row < rows && col >= 0 && col < cols;
}

// Tìm kiếm A*
vector<pair<int, int>> performAStar(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> target) {
    int rows = grid.size();
    int cols = grid[0].size();

    priority_queue<Vertex, vector<Vertex>, greater<Vertex>> openQueue; // Hàng đợi ưu tiên nhỏ nhất
    unordered_map<int, bool> closedQueue; // Danh sách đóng (danh sách các điểm đã thăm)

    auto encodePosition = [&](int row, int col) { return row * cols + col; }; // Mã hóa toạ độ

    // Nút ban đầu
    Vertex* startVertex = new Vertex(start.first, start.second, 0, estimateCost(start.first, start.second, target.first, target.second));
    openQueue.push(*startVertex);

    // Xác định hướng di chuyển
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (!openQueue.empty()) {
        Vertex current = openQueue.top();
        openQueue.pop();

        // Kiểm tra nếu đã đạt đến đích
        if (current.row == target.first && current.col == target.second) {
            vector<pair<int, int>> path;
            Vertex* temp = &current;
            while (temp) {
                path.emplace_back(temp->row, temp->col);
                temp = temp->predecessor;
            }
            reverse(path.begin(), path.end());
            return path;
        }

        // Đánh dấu điểm hiện tại đã được thăm
        closedQueue[encodePosition(current.row, current.col)] = true;

        // Mở rộng các nút láng giềng
        for (auto& dir : directions) {
            int newRow = current.row + dir.first;
            int newCol = current.col + dir.second;

            if (isWithinBounds(newRow, newCol, rows, cols) && grid[newRow][newCol] == 0 && !closedQueue[encodePosition(newRow, newCol)]) {
                double updatedCost = current.costSoFar + 1; // Giả sử mỗi bước có chi phí là 1
                double estimatedCost = estimateCost(newRow, newCol, target.first, target.second);
                openQueue.push(Vertex(newRow, newCol, updatedCost, estimatedCost, new Vertex(current.row, current.col, current.costSoFar, current.estimate, current.predecessor)));
            }
        }
    }

    return {}; // Không tìm thấy đường đi
}

int main() {
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0},
    };

    pair<int, int> startPoint = {0, 0};
    pair<int, int> endPoint = {4, 4};

    vector<pair<int, int>> path = performAStar(grid, startPoint, endPoint);

    if (!path.empty()) {
        cout << "Đường đi được tìm thấy:\n";
        for (auto& p : path) {
            cout << "(" << p.first << ", " << p.second << ") -> ";
        }
        cout << "Đích\n";
    } else {
        cout << "Không tìm thấy đường đi.\n";
    }

    return 0;
}

Phức tạp độ thời gian

• Trường hợp xấu nhất: O(E), trong đó E là số cạnh của đồ thị.
• Hiệu quả cao trên đồ thị thưa, thường kết hợp với cấu trúc dữ liệu tối ưu (như đống Fibonacci) để tăng cường hiệu năng.

Ứng dụng

• Điều hướng bản đồ (như Google Maps).
• Quy hoạch đường đi AI trong trò chơi.
• Quy hoạch đường đi cho robot.