Tìm kiếm ưu tiên tối ưu (best-first search)
Ưu điểm của tìm kiếm theo chiều sâu là
không phải quan tâm đến sự mở rộng của tất cả các nhánh. Ưu điểm của tìm
kiếm chiều rộng là không bị sa vào các đường dẫn bế tắc (các nhánh
cụt). Tìm kiếm ưu tiên tối ưu sẽ kết hợp 2 phương pháp trên cho phép ta
đi theo một con đường duy nhất tại một thời điểm, nhưng đồng thời vẫn
"quan sát" được những hướng khác. Nếu con đường đang đi "có vẻ" không
triển vọng bằng những con đường ta đang "quan sát" ta sẽ chuyển sang đi
theo một trong số các con đường này. Để tiện lợi ta sẽ dùng chữ viết tắt
BFS thay cho tên gọi tìm kiếm ưu tiên tối ưu.
Một cách cụ thể, tại mỗi bước của tìm
kiếm BFS, ta chọn đi theo trạng thái có khả năng cao nhất trong số các
trạng thái đã được xét cho đến thời điểm đó. (khác
với leo đồi dốc đứng là chỉ chọn trạng thái có khả năng cao nhất trong
số các trạng thái kế tiếp có thể đến được từ trạng thái hiện tại). Như
vậy, với tiếp cận này, ta sẽ ưu tiên đi vào những nhánh tìm kiếm có khả
năng nhất (giống tìm kiếm leo đồi dốc đứng), nhưng ta sẽ không bị lẩn
quẩn trong các nhánh này vì nếu càng đi sâu vào một hướng mà ta phát
hiện ra rằng hướng này càng đi thì càng tệ, đến mức nó xấu hơn cả những
hướng mà ta chưa đi, thì ta sẽ không đi tiếp hướng hiện tại nữa mà chọn
đi theo một hướng tốt nhất trong số những hướng chưa đi. Đó là tư tưởng
chủ đạo của tìm kiếm BFS. Để hiểu được tư tưởng này. Bạn hãy xem ví dụ
sau :
Hình Minh họa thuật giải Best-First Search
Khởi đầu, chỉ có một nút (trạng thái) A
nên nó sẽ được mở rộng tạo ra 3 nút mới B,C và D. Các con số dưới nút là
giá trị cho biết độ tốt của nút. Con số càng nhỏ, nút càng tốt. Do D là
nút có khả năng nhất nên nó sẽ được mở rộng tiếp sau nút A và sinh ra 2
nút kế tiếp là E và F. Đến đây, ta lại thấy nút B có vẻ có khả năng
nhất (trong các nút B,C,E,F) nên ta sẽ chọn mở rộng nút B và tạo ra 2
nút G và H. Nhưng lại một lần nữa, hai nút G, H này được đánh giá ít khả
năng hơn E, vì thế sự chú ý lại trở về E. E được mở rộng và các nút
được sinh ra từ E là I và J. Ở bước kế tiếp, J sẽ được mở rộng vì nó có
khả năng nhất. Quá trình này tiếp tục cho đến khi tìm thấy một lời giải.
Lưu ý rằng tìm kiếm này rất giống với tìm
kiếm leo đồi dốc đứng, với 2 ngoại lệ. Trong leo núi, một trạng thái
được chọn và tất cả các trạng thái khác bị loại bỏ, không bao giờ chúng
được xem xét lại. Cách xử lý dứt khoát này là một đặc trưng của leo đồi.
Trong BFS, tại một bước, cũng có một di chuyển được chọn nhưng những
cái khác vẫn được giữ lại, để ta có thể trở lại xét sau đó khi trạng
thái hiện tại trở nên kém khả năng hơn những trạng thái đã được lưu trữ.
Hơn nữa, ta chọn trạng thái tốt nhất mà không quan tâm đến nó có tốt hơn hay
không các trạng thái trước đó. Điều này tương phản với leo đồi vì leo
đồi sẽ dừng nếu không có trạng thái tiếp theo nào tốt hơn trạng thái
hiện hành.
Để cài đặt các thuật giải theo kiểu tìm kiếm BFS, người ta thường cần dùng 2 tập hợp sau :
OPEN : tập chứa các trạng thái đã được
sinh ra nhưng chưa được xét đến (vì ta đã chọn một trạng thái khác).
Thực ra, OPEN là một loại hàng đợi ưu tiên (priority queue) mà trong đó,
phần tử có độ ưu tiên cao nhất là phần tử tốt nhất.
Người ta thường cài đặt hàng đợi ưu tiên bằng Heap. Các bạn có thể tham
khảo thêm trong các tài liệu về Cấu trúc dữ liệu về loại dữ liệu này.
CLOSE : tập chứa các trạng thái đã được
xét đến. Chúng ta cần lưu trữ những trạng thái này trong bộ nhớ để đề
phòng trường hợp khi một trạng thái mới được tạo ra lại trùng với một
trạng thái mà ta đã xét đến trước đó. Trong trường hợp không gian tìm
kiếm có dạng cây thì không cần dùng tập này.
Thuật giải BEST-FIRST SEARCH
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái tốt nhất (Tmax) trong OPEN (và xóa Tmaxkhỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
Tính f(Tk); Thêm Tk vào OPEN
BFS khá đơn giản. Tuy vậy, trên thực tế,
cũng như tìm kiếm chiều sâu và chiều rộng, hiếm khi ta dùng BFS một cách
trực tiếp. Thông thường, người ta thường dùng các phiên bản của BFS là
AT, AKT và A*
Thông tin về quá khứ và tương lai
Thông thường, trong các phương án tìm
kiếm theo kiểu BFS, độ tốt f của một trạng thái được tính dựa theo 2 hai
giá trị mà ta gọi là là g và h’. h’ chúng ta đã biết, đó là một ước
lượng về chi phí từ trạng thái hiện hành cho đến trạng thái đích (thông
tin tương lai). Còn g là "chiều dài quãng đường" đã đi
từ trạng thái ban đầu cho đến trạng thái hiện tại (thông tin quá khứ).
Lưu ý rằng g là chi phí thực sự (không phải chi phí ước lượng). Để dễ
hiểu, bạn hãy quan sát hình sau :
Hình 6.14 Phân biệt khái niệm g và h’
Kết hợp g và h’ thành f’ (f’ = g + h’) sẽ
thể hiện một ước lượng về "tổng chi phí" cho con đường từ trạng thái
bắt đầu đến trạng thái kết thúc dọc theo con đường đi qua trạng thái
hiện hành. Để thuận tiện cho thuật giải, ta quy ước là g và h’ đều không
âm và càng nhỏ nghĩa là càng tốt.
Thuật giải AT
Thuật giải ATlà
một phương pháp tìm kiếm theo kiểu BFS với độ tốt của nút là giá trị hàm
g – tổng chiều dài con đường đã đi từ trạng thái bắt đầu đến trạng thái
hiện tại.
Thuật giải AT
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái (Tmax) có giá trị g nhỏ nhất trong OPEN (và xóa Tmaxkhỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Thêm Tk vào OPEN.
* Vì chỉ sử dụng hàm g (mà không dùng hàm
ước lượng h’) fsđể đánh giá độ tốt của một trạng thái nên ta cũng có
thể xem AT chỉ là một thuật toán.
Thuật giải AKT
(Algorithm for Knowlegeable Tree Search)
Thuật giải AKTmở rộng AT bằng cách sử dụng thêm thông tin ước lượng h’. Độ tốt của một trạng thái f là tổng của hai hàm g và h’.
Thuật giải AKT
1. Đặt OPEN chứa trạng thái khởi đầu.
2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :
2.a. Chọn trạng thái (Tmax) có giá trị f nhỏ nhất trong OPEN (và xóa Tmaxkhỏi OPEN)
2.b. Nếu Tmax là trạng thái kết thúc thì thoát.
2.c. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :
g(Tk) = g(Tmax) + cost(Tmax, Tk);
Tính h’(Tk)
f(Tk) = g(Tk) + h’(Tk);
Thêm Tk vào OPEN.
Không có nhận xét nào:
Đăng nhận xét