Bài viết sưu tầm

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ừ n₀®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 f⁰(n)=g⁰(n)+h⁰(n): dự đoán chi phí cực tiểu của đường đi từ n₀®DICH có đi qua đỉnh n.

     g⁰(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. h⁰(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ỉ h⁰(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.

Tuy nhiên, người ta cũng chứng minh được 2 kết quả như sau:

Kết quả 1: Nếu h⁰(n) có tính chất:  và   thì thủ tục TKCT sử dụng hàm f⁰(n) để chọn phần tử trong MO ra xét (thay g(n)) sẽ cho đường đi từ n₀®n_*ÎDICH  sao cho

Kết quả 2:Giả sử dùng 2 hàm ước lượng  và  thoả tính chất: (giá cực tiểu của đường đi từ m®n) và . Khi đó #DONG₂ £#DONG₁

Nhận xét:

 phương án tốt nhất

phương án tồi nhất

Thuật toán A^*

Input:

     Đồ thị G = (V,E), Đỉnh xuất phát n₀

     Hàm chi phí c: E ®R⁺

c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j) ÎE

     h: V  ®  R⁺; h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích. (ký hiệu h thay cho h⁰, (tương tự g)) 

Tập các đỉnh đích DICH

Output:

Đường đi từ đỉnh n₀ đến đỉnh n_* ÎDICH     

Procedure  A^* ;

Begin

     g(n₀):= 0;

     push(MO, n₀);

     while MO<>null do

                 begin

                             if nÎDICH then

                                         exit {xay dung duong di cuc tieu}

                             push(DONG, n);

                             if T(n) <>null then

                                         for  mÎT(n) do

                                                     if mÏMO+DONG then

                                                                 begin

                                                                             push(MO,m);

                                                                             tính f(m);

                                                                             cha(m):=n;

end

                                                     else

                                                                 if f_mới(m) > f_cũ(n) then

begin

                                                                                         f(m):= f_mới(m);

                                                                                         cha(m):=n;

end;

                 end;

                 writeln(‘khong co duong di’);

End;