1.6 Lập trình cấu trúc dữ liệu và giải thuật  (Page 15/46)

h’(Craiova)  160

g(Craiova)  g(R.Vilcea)+ cost(R.Vilcea, Craiova)

 220+146 366

f’(Craiova)  g(Fagaras)+h’(Fagaras)

 366+160 526

h’(Pitesti)  98

g(Pitesti)  g(R.Vilcea)+ cost(R.Vilcea, Pitesti)

 220+97  317

f’(Pitesti)  g(Oradea)+h’(Oradea)

 317+98  415

Sibiu đã có trong tập CLOSE. Tuy nhiên, do g’(Sibiu) mới (có giá trị là 553) lớn hơn g’(Sibiu) (có giá trị là 393) nên ta sẽ không cập nhật lại các giá trị của Sibiu được lưu trong CLOSE. Còn lại 2 thành phố là Pitesti và Craiova đều không có trong cả OPEN và CLOSE nên ta sẽ đưa nó vào OPEN và đặt cha của chúng là R.Vilcea.

OPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad)

(Zerind,g 75,h’ 374,f’ 449,Cha Arad) (Fagaras,g 239,h’ 178,f’ 417,Cha Sibiu)

(Oradea,g 291,h’ 380,f’ 617,Cha Sibiu) (Craiova,g 366,h’ 160,f’ 526,Cha R.Vilcea)

(Pitesti,g 317,h’ 98,f’ 415,Cha R.Vilcea) }

CLOSE  {(Arad,g 0,h’ 0,f’ 0)

(Sibiu,g 140,h’ 253,f’ 393,Cha Arad)

(R.Vilcea,g 220,h’ 193,f’ 413,Cha Sibiu)   }

Đến đây, trong tập OPEN, nút tốt nhất là Pitesti, từ Pitesti ta có thể đi đến được R.Vilcea, Bucharest và Craiova. Lấy Pitesti ra khỏi OPEN và đặt nó vào CLOSE. Thực hiện tiếp theo tương tự như trên, ta sẽ không cập nhật giá trị f’, g của R.Vilcea và Craiova lưu trong CLOSE. Sau khi tính toán f’, g của Bucharest, ta sẽ đưa Bucharest vào tập OPEN, đặt Cha(Bucharest)  Pitesti.

h’(Bucharest)  0

g(Bucharest)  g(Pitesti)+cost(Pitesti, Bucharest)

 317+100 418

f’(Bucharest)  g(Fagaras)+h’(Fagaras)

 417+0 417

Ở bước kế tiếp, ta sẽ chọn được Tmax  Bucharest. Và như vậy thuật toán kết thúc (thực ra thì tại bước này, có hai ứng cử viên là Bucharest và Fagaras vì đều cùng có f’ 417 , nhưng vì Bucharest là đích nên ta sẽ ưu tiên chọn hơn).

Để xây dựng lại con đường đi từ Arad đến Bucharest ta lần theo giá trị Cha được lưu trữ kèm với f’, g và h’ cho đến lúc đến Arad.

Cha(Bucharest)  Pitesti

Cha(R.Vilcea)  Sibiu

Cha(Sibiu)  Arad

Vậy con đường đi ngắn nhất từ Arad đến Bucharest là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest.

Trong ví dụ minh họa này, hàm h’ có chất lượng khá tốt và cấu trúc đồ thị khá đơn giản nên ta gần như đi thẳng đến đích mà ít phải khảo sát các con đường khác. Đây là một trường hợp đơn giản, trong trường hợp này, thuật giải có dáng dấp của tìm kiếm chiều sâu.

Đến đây, để minh họa một trường hợp phức tạp hơn của thuật giải. Ta thử sửa đổi lại cấu trúc đồ thị và quan sát hoạt động của thuật giải. Giả sử ta có thêm một thành phố tạm gọi là TP và con đường giữa Sibiu và TP có chiều dài 100, con đường giữa TP và Pitesti có chiều dài 60. Và khoảng cách đường chim bay từ TP đến Bucharest là 174. Như vậy rõ ràng, con đường tối ưu đến Bucharest không còn là Arad, Sibiu, R.Vilcea, Pitesti, Bucharest nữa mà là Arad, Sibiu, TP, Pitesti, Bucharest.

Trong trường hợp này, chúng ta vẫn tiến hành bước 1 như ở trên. Sau khi thực hiện hiện bước 2 (mở rộng Sibiu), chúng ta có cây tìm kiếm như hình sau. Lưu ý là có thêm nhánh TP.

R.Vilcea vẫn có giá trị f’ thấp nhất. Nên ta mở rộng R.Vilcea như trường hợp đầu tiên.