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

Một cách kết hợp khác là dùng tìm kiếm chiều sâu tại đỉnh không gian tìm kiếm và BFS được dùng tại đáy. Chúng ta áp dụng tìm kiếm chiều sâu cho tới khi gặp một trạng thái Tk mà độ sâu (số trạng thái trung gian) của nó vượt quá một ngưỡng d0 nào đó. Tại điểm này, thay vì lần ngược trở lại, ta áp dụng kiểu tìm kiếm BFS cho phần không gian phía "dưới" bắt đầu từ Tk cho tới khi nó trả về một giải pháp hoặc không tìm thấy. Nếu nó không tìm thấy kết quả, chúng ta lần ngược trở lại và lại dùng BFS khi đạt độ sâu d0. Tham số d0 sẽ được chọn sao cho bộ nhớ dùng cho tìm kiếm BFS trên không gian "dưới" mức d0 sẽ không vượt quá một hằng số cho trước. Rõ ràng ta ta không dễ gì xác định được d0 (vì nói chung, ta khó đánh giá được không gian bài toán rộng đến mức nào). Tuy nhiên, kiểu kết hợp này lại có một thuận lợi. Phần đáy không gian tìm kiếm thường chứa nhiều thông tin "bổ ích" hơn là phần đỉnh. (Chẳng hạn, tìm đường đi đến khu trung tâm của thành phố, khi càng đến gần khu trung tâm – đáy đồ thị – bạn càng dễ dàng tiến đến trung tâm hơn vì có nhiều "dấu hiệu" của trung tâm xuất hiện xung quanh bạn!). Nghĩa là, càng tiến về phía đáy của không gian tìm kiếm, ước lượng h’ thường càng trở nên chính xác hơn và do đó, càng dễ dẫn ta đến kết quả hơn.

Hình : Chiến lược lai BFS-MC trong đó, MC áp dụng tại đỉnh và BFS tại đáy.

Còn một kiểu kết hợp phức tạp hơn nữa. Trong đó, BFS được thực hiện cục bộ và chiều sâu được thực hiện toàn cục. Ta bắt đầu tìm kiếm theo BFS cho tới khi một sự lượng bộ nhớ xác định M0 được dùng hết. Tại điểm này, chúng ta xem tất cả những trạng thái trong OPEN như những trạng thái con trực tiếp của trạng thái ban đầu và chuyển giao chúng cho tìm kiếm chiều sâu. Tìm kiếm chiều sâu sẽ chọn trạng thái tốt nhất trong những trạng thái con này và "bành trướng" nó dùng BFS, nghĩa là nó chuyển trạng thái đã chọn cho tìm kiếm BFS cục bộ cho đến khi một lượng bộ nhớ M0 lại được dùng hết và trạng thái con mới trong OPEN lại tiếp tục được xem như nút con của nút "bành trướng"...Nếu việc "bành trướng" bằng BFS thất bại thì ta quay lui lại và chọn nút con tốt thứ hai của tập OPEN trước đó, rồi lại tiếp tục bành trướng bằng BFS...

Hình : Chiến lược lai BFS-MC trong đó, BFS được áp dụng cục bộ và chiều sâu được áp dụng toàn cục.

Có một cách phối hợp nổi tiếng khác được gọi là tìm kiếm theo giai đoạn được thực hiện như sau. Thay vì lưu trữ trong bộ nhớ toàn bộ cây tìm kiếm được sinh ra bởi BFS, ta chỉ giữ lại cây con có triển vọng nhất. Khi một lượng bộ nhớ M0 được dùng hết, ta sẽ đánh dấu một tập con các trạng thái trong OPEN (những trạng thái có giá trị hàm f thấp nhất) để giữ lại; những đường đi tốt nhất qua những trạng thái này cũng sẽ được ghi nhớ và tất cả phần còn lại của cây bị loại bỏ. Quá trình tìm kiếm sau đó sẽ tiếp tục theo BFS cho tới khi một lượng bộ nhớ M0 lại được dùng hết và cứ thế. Chiến lược này có thể được xem như là một sự lai ghép giữa BF và leo đèo. Trong đó, leo đèo thuần túy loại bỏ tất cả nhưng chỉ giữ lại phương án tốt nhất còn tìm kiếm theo giai đoạn loại bỏ tất cả nhưng chỉ giữ lại tập các phương án tốt nhất.