Giải thuật AT - giá thành cực tiểu

1. Tìm kiếm đường đi có giá thành cực tiểu - Thuật toán AT
Cho đồ thị G= (V, E) biểu diễn bài toán với đỉnh xuất phát n0 và tập đích DICH xác định.
Với mỗi phép chuyển trạng thái n(i)->n(i+1) tốn chi phí c(i, i+1), ở đây có thể xem là trọng số của cung nối n(i) và n(i+1)
Phương pháp
Tương tự phương pháp tìm kiếm theo chiều sâu, nhưng tại mỗi biết ta tính giá thành của mỗi đỉnh và chọn đỉnh có giá thành tối ưu nhất
2. Giải thuật
Input:
    Đồ thị G = (V,E), Đỉnh xuất phát n0
    Hàm chi phí c
    Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* in DICH sao cho g(n*) = MIN

            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;
                        BeforeOfNode(n, node);
                    }
                    else if (!closeList.InList(n) && n.Cost > node.Cost + Edge(node, n).Value)
                    {
                        n.Cost = node.Cost + Edge(node, n).Value;
                        BeforeOfNode(n, node);
                    }
                }
                openList.Sort(SortType.ASCENDING);//sắp xếp lại để chọn đỉnh tối ưu nhất ở đỉnh Stack
            }

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

3. Ví dụ

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

Đỉ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ả

 

Chi phí là 6

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