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

2.6 Chuyển danh sách Lvào ngăn xếp S; End; Ví dụ : Với ví dụ đồ thị không gian trạng thái như hình 2.2 thì cây tìm kiếm leo đồi tương ứng như hình 2.4 : A 2015 C E76 D10 FI 80 BG5Cây tìm kiếm leo đồi Hạn chế của thuật toán : - Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ: + Lời giải tìm được không tối ưu + Không tìm được lời giải mặc dù có tồn tại lời giải - Giải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin về các trạng thái đã duyệt. * Tìm kiếm Beam Để hạn chế không gian tìm kiếm, người ta đưa ra phương pháp tìm kiếm Beam. Đây là phương pháp tìm kiếm theo chiều rộng nhưng có hạn chế số đỉnh phát triển ở mỗi mức. Trong tìm kiếm theo chiều rộng, tại mỗi mức ta phát triển tất cả các đỉnh, còn tìm kiếm Beam thì chọn k đỉnh tốt nhất để phát triển. Các đỉnh này được xác định bởi hàm đánh giá. Ví dụ, với đồ thì không gian trạng thái như hình 2.2 và lấy k=2 thì cây tìm kiếm Beam như hình 2.5. Các đỉnh được chọn ở mỗi mức là các đỉnh được tô màu đỏ:

A 20

15

C

E

6

D

7

K

12

10

F

I

8

G

5

0

B

5

G

H

B

3

0

Cây tìm kiếm Beam* Tìm kiếm nhánh cận Ý tưởng : thuật toán tìm kiếm leo đồi kết hợp với hàm đánh giá f(u). Tại mỗi bước, khi phát triển trạng thái u, chọn trạng thái con v tốt nhất (f(v) nhỏ nhất) của u để phát triển ở bước sau. Quá trình tiếp tục như vậy cho đến khi gặp trạng thái w là đích, hoặc w không có đỉnh kề, hoặc w có f(w) lớn hơn độ dài đường đi tối ưu tạm thời (đường đi đầy đủ ngắn nhất trong số những đường đi đầy đủ đã tìm được). Trong các trường hợp này, chúng ta không phát triển đỉnh w nữa, tức là cắt bỏ những nhánh xuất phát từ w, và quay lên cha của w để tiếp tục đi xuống trạng thái tốt nhất trong số những trạng thái còn lại chưa được phát triển. Procedure Branch-and-Bound; Begin