Giải thuật A* - Tìm kiếm cực tiểu

1. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*

Đối với nhiều bài toán, việc tìm kiếm đường đi cực tiểu sẽ được định hướng tập trung xung quanh  đường đi tốt nhất; nếu sử dụng các thông tin đặc tả về bài toán gọi là các heuristic.
Đối với việc tìm kiếm đường đi với chi phí cực tiểu, người ta sử dụng hàm đánh giá heuristic như sau:
    Gọi g(n): giá cực tiểu đường đi từ n0->n. Tại đỉnh n, g(n) xác định được.
    Gọi h(n): giá cực tiểu đường đi từ n->DICH, h(n) không xác định được Þ người ta tìm cách ước lượng giá trị này.
    Đặt f0(n)=g0(n)+h0(n): dự đoán chi phí cực tiểu của đường đi từ n0->DICH có đi qua đỉnh n.
    g0(n) là chi phí của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét. h0(n) là ước lưọng (dự đoán) chi phí đường đi từ đỉnh n đến đích. Việc chọn giá trị xấp xỉ h0(n) của h(n) không có một phương pháp tổng quát và được xem như một nghệ thuật. Giá trị này sẽ do các chuyên gia đưa ra.
Lúc này giải thuật tìm kiếm cực tiểu sẽ thay việc xét hàm g bởi hàm f.
2. Giải thuật
Input:
    Đồ thị G = (V,E), Đỉnh xuất phát n0
    Hàm chi phí c: c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j
    h: h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích.
Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* thuộc DICH với giá thành cực tiểu


            bool result = false;
            openList.Push(n0);
            while (!openList.IsEmpty())
            {
                node = openList.Pop();
                if (node.Equals(n*))
                {
                    result = true;
                    break;
                }

                closeList.Push(node);
                for (n in Tn(node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        openList.Push(n);
                        n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
                        BeforeOfNode(n, node);
                    }
                    else if (!closeList.InList(n) && n.Cost > node.Cost + Edge(node, n).Value + n.Huerictis)
                    {
                        n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
                        BeforeOfNode(n, node);
                    }
                }
                openList.Sort(SortType.ASCENDING);//sắp xếp theo chi phí của mỗi đỉnh, giá trị Min ở đỉnh Stack
            }

            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }

3. Ví dụ

Cho đồ thị như hình vẽ

Với giá trị Hueristic của mỗi đỉnh như sau

H(1) = 1  H(2) = 3  H(3) = 5   H(4) = 6  H(5) = 4
H(6) = 1  H(7) = 2  H(8) = 3   H(9) = 1  H(10) = 6

Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

Kết quả

Với chi phí cực tiểu là 18

Mã nguồn tham khảo tại đây