CHƯƠNG 3 –CÁC PHƯƠNG PHÁP TÌM KIẾM HEURISTIC

2. Các biến thể của giải thuật best first search

Ý tưởng của giải thuật tìm kiếm tốt nhất đầu tiên (best first search) là mở rộng cây tìm kiếm theo hướng ưu tiên các nút lá có triển vọng chứa trạng thái đích (dựa trên hàm đánh giá h). Giải thuật best-first-search có các biến thể sau: - Khi hàm h(n) là chi phí của dãy phép chuyển từ trạng thái đầu đến trạng thái n thì giải thuật best-first-search có tên gọi khác là giải thuật tìm kiếm đều (uniform search). Trong trường hợp này, cây tìm kiếm sẽ mở rộng đều về tất cả các hướng theo vết dầu loang từ trạng thái đầu. Khi hàm chi phí của dãy phép chuyển là số các đỉnh trung gian thì giải thuật uniform search trở thành giải thuật tìm kiếm theo chiều rộng. Giải thuật uniform search sẽ cho lời giải với chi phí nhỏ nhất, tuy nhiên cây tìm kiếm sinh ra trong giải thuật này thường có kích thước rất lớn. - Khi h(n) là ước lượng chi phí/khoảng cách từ n đến đích (ví dụ như khoảng cách Manhatan trong bài toán 8 số ở trên) thì giải thuật best-first-search được gọi là giải thuật tham ăn (greedy search). Giải thuật tham ăn sẽ chọn nút lá n “gần” đến đích nhất trong số các nút lá của cây tìm kiếm để mở rộng cây, và nó không quan tâm đến chi phí từ trạng thái đầu đến n. Do vậy giải thuật có xu hướng cho ra kết quả trong thời gian nhanh nhất, nhưng không phải lúc nào cũng là lời giải ngắn nhất. - Khi h(n) = f(n) + g(n), trong đó f(n) là hàm chi phí/khoảng cách từ trạng thái đầu đến n và g(n) là hàm ước lượng chi phí/khoảng cách từ n đến trạng thái đích, và nếu g(n) là ước lượng dưới của hàm chi phí/khoảng cách thực sự từ n đến trạng thái đích thì giải thuật best-first-search được gọi là giải thuật A*. Giải thuật A* là giải thuật trung hòa giữa hai giải thuật uniform và giải thuật greedy ở trên. A* cho lời giải có chi phí nhỏ nhất (bạn đọc có thể tìm hiểu chứng minh điều này ở các tài liệu khác) và cây tìm kiếm có kích thước vừa phải. Ví dụ, đối với bài toán tìm đường đi từ thành phố Arad đến thành phố Bucharest đã mô tả trong 1.b, nếu chúng ta sử dụng khoảng cách Ơclit (khoảng cách theo đường chim bay) từ mỗi thành phố đến đích (xem hình vẽ trên) thì các giải thuật uniform, greedy và A* sẽ cho các cây tìm kiếm như sau: Một phần cây tìm kiếm của giải thuật Uniform search Cây tìm kiếm của giải thuật Greedy search Cây tìm kiếm của giải thuật A*