THUẬT TOÁN TÌM KIẾM HEURISTIC

Tìm kiếm leo núi (Hill climbing – Pearl 1984)

Cách đơn giản nhất để thực hiện tìm kiếm heuristic là tìm kiếm “leo núi”. Chiến lược leo núi phát triển trạng thái con tốt nhất sẽ được chọn cho bước tiếp theo, không lưu giữ lại bất kỳ thông tin nào về các nút anh em lẫn cha mẹ của nó. Quá trình tìm kiếm sẽ dừng lại khi tiếp cận trạng thái tốt hơn so với mọi trạng thái con của nó. Hình dung một người leo núi hăm hở nhưng mù quáng luôn luôn chọn leo lên đỉnh theo con đường dốc nhất có thể có cho đến khi không còn leo tiếp được nữa. Vì không ghi lại thông tin của quá trình đã xảy ra nên thuật toán này không thể phục hồi lại từ những thất bại trong chiến lược của nó.

Hạn chế chủ yếu của chiến lược leo núi là có xu hướng rơi vào “một cực đại cục bộ”. Khi đến được một trạng thái tốt hơn so với mọi trạng thái con của nó, thuật toán dừng lại. Nếu trạng thái này không phải là đích mà chỉ là một điểm cực đại cục bộ, thuật toán sẽ thất bại trong việc tìm lời giải. Như vậy hiệu quả hoạt động chỉ có thể được cải thiện trong một phạm vi giới hạn nào đó, nhưng trong toàn bộ không gian có thể không bao giờ đạt được sự tối ưu tổng thể.

Tìm kiếm tốt nhất đầu tiên (Best – first – search)

Xét đồ thị không gian tìm kiếm như hình dưới đây (con số cạnh mỗi nút cho biết giá trị ước lượng độ tốt của nút đó trong không gian, giá trị thấp nhất là tốt nhất). Giả sử nút đích cần tìm kiếm là P.

Hình 4.4 – Đồ thị cho giải thuật tìm kiếm tốt nhất đầu tiên

Câu hỏi :

Trình bày danh sách các nút được duyệt dùng thuật toán leo núi cho đồ thị trong hình 4.4 ?

Giống như các thuật toán tìm kiếm sâu và rộng, tìm kiếm tốt nhất cũng dùng các danh sách để lưu giữ trạng thái: danh sách open chứa các nút được triển khai trong quá trình tìm kiếm và danh sách closed chứa các nút đã xét. Một bước mới được bổ sung vào thuật toán là sắp xếp các trạng thái trong danh sách open phù hợp với giá trị heuristic ước lượng “độ tốt” của chúng so với đích. Như vậy mỗi bước lặp của vòng lặp sẽ xem xét trạng thái “có hứa hẹn nhất” trong danh sách open và loại bỏ trạng thái này ra khỏi open. Nếu gặp trạng thái đích, thuật toán này sẽ cung cấp con đường lời giải đã dẫn đến đích đó. Nếu ngược lại, phần tử đầu tiên của open không phải là đích, thuật toán sẽ áp dụng các luật phù hợp để phát sinh con cháu. Trường hợp một trạng thái con nào đó đã có sẵn trong open hoặc closed, thuật toán cũng sẽ kiểm tra để chắc chắn rằng sẽ chọn được nút cung cấp con đường lời giải ngắn hơn. Các trạng thái lặp hai lần sẽ không được giữ lại. Nhờ cập nhật kịp thời nguồn gốc của các nút trong open và closed nên thuật toán này có nhiều khả năng tìm được đường đi ngắn nhất dẫn đến đích. Khi open được duy trì dưới dạng một danh sách có sắp xếp, nó thường được tổ chức như là một hàng ưu tiên (Priority queue). Dưới đây trình bày các bước áp dụng thuật toán tìm kiếm cho đồ thị trong hình trên.

1. open = [A5]; closed = []2. Đánh giá A5; open = [B4,C4,D6]; closed = [A5]3. Đánh giá B4; open = [C4,E5,F5,D6]; closed = [B4,A5]4. Đánh giá C4; open = [H3,G4,E5,F5,D6]; closed = [C4,B4,A5]5. Đánh giá H3; open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5]6. Đánh giá O2; open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5]7. Đánh giá P3; Tìm được lời giải!

Cài đặt hàm đánh giá heuristic (heuristic evaluation function)

Bây giờ ta đánh giá hiệu quả của vài heuristic khác nhau được dùng để giải trò đố 8 ô. Hình dưới đây trình bày trạng thái xuất phát và trạng thái đích của trò chơi cùng với ba trạng thái đầu tiên trong quá trình tìm kiếm.

Heuristic đơn giản nhất sẽ đếm số ô sai khác so với trạng thái đích trong từng trạng thái. Trạng thái có số ô sai khác ít nhất sẽ gần đích hơn và là trạng thái tốt nhất để kiếm tra kế tiếp.

Hình 4.5 – Trạng thái bắt đầu và kết thúc trong trò đố 8 ô

Tuy nhiên heuristic này không sử dụng hết các thông tin trong một cấu hình bàn cờ vì nó không đưa vào khoảng cách mà các ô sai khác. Một heuristic “tốt hơn” là sẽ cộng tất cả các khoảng cách đó lại thành tổng số ô mà một ô phải di chuyển về vị trí đúng của nó trong trạng thái đích (khoảng cách Manhattan).

Cả hai heuristic này đều có hạn chế là không thể biết rõ những khó khăn khi đổi chỗ hai ô. Đó là trường hợp hai ô nằm cạnh nhau và vị trí đúng của chúng là phải đổi chỗ cho nhau, ta phải mất nhiều (chứ không phải hai) nước đi mới đặt chúng lại được đúng vị trí. Một heuristic muốn tính toán điều này phải nhân ít nhất là gấp đôi khoảng cách đối với mỗi trường hợp có hai ô đổi chỗ trực tiếp.

Heuristic “khoảng cách Manhattan” cho chúng ta một dự đoán có vẻ chính xác hơn so với heuristic số ô sai khác so với trạng thái đích. Mục đích của chúng ta là dùng những thông tin hạn chế có sẵn trong một mô tả trạng thái để đưa ra những chọn lựa thông minh. Việc thiết kế các heuristic tốt là một vấn đề mang tính kinh nghiệm, óc phán đoán và trực giác, nhưng giá trị cuối cùng của một heuristic phải được đo bằng hiệu quả thực sự của nó trong từng tình huống bài toán.

Vì heuristic có thể sai lầm nên có khả năng thuật toán tìm kiếm sẽ dẫn đến một con đường không đưa đến đích. Vấn đề này đã xuất hiện trong tìm kiếm sâu, ở đó một giới hạn độ sâu đã được sử dụng để phát hiện những con đường thất bại. Ý tưởng này cũng có thể áp dụng cho tìm kiếm heuristic. Nếu hai trạng thái có giá trị heuristic bằng nhau thì nên kiểm tra trạng thái nào gần trạng thái gốc của đồ thị hơn. Trạng thái gần gốc hơn sẽ có nhiều khả năng là con đường ngắn nhất dẫn đến đích. Khoảng cách từ trạng thái xuất phát có thể đo được bằng cách duy trì một số đếm chiều sâu cho từng trạng thái đếm. Số đếm này bằng 0 đối với trạng thái xuất phát và tăng lên một đơn vị sau mỗi mức tìm kiếm. Nó ghi lại độ dời thực tế phải thực hiện để đi từ trạng thái xuất phát đến từng trạng thái. Số đếm này có thể cộng thêm vào giá trị heuristic của từng trạng thái để hướng việc tìm kiếm theo khuynh hướng chọn những trạng thái gần trạng thái xuất phát hơn trong đồ thị.

Do đó hàm đánh giá f sẽ bao gồm tổng của hai phần:

f(n) = g(n) + h(n)

trong đó g(n) đo chiều dài thực từ trạng thái n bất kỳ về trạng thái xuất phát và h(n) là ước lượng heuristic cho khoảng cách từ trạng thái n đến trạng thái đích.

Chẳng hạn, trong bài toán trò đố 8 ô trên, chúng ta có thể gọi h(n) là số ô cần phải dời chỗ. Khi hàm đánh giá này được áp dụng cho từng trạng thái con (A), (B), (C) trong hình 4.5, các giá trị cho hàm f lần lượt là 6, 4 và 6.

Một heuristic dùng hàm đánh giá f(n) như trên kết hợp với thuật toán tìm kiếm tốt nhất đầu tiên best-first-search, được gọi là thuật toán A (algorithm A)

Câu hỏi :

Mật mã Caesar là một cách mã hóa đơn giản dựa vào phép hoán vị vòng

tròn các chữ trong bảng chữ cái, với chữ cái thứ i được thay thế bởi chữ cái

thứ (i + 1). Ví dụ, trong mật mã Caesar dịch 4 bậc, từ “Ceasar” sẽ được mã

hóa thành “Geiwev”. Nêu một heuristic mà bạn nghĩ có thể dùng để giải các

mật mã Ceasar ?

Tính khả chấp, tính đơn nhất và khả năng cung cấp thông tin của heuristic

Có thể chúng ta phải đánh giá cách hành xử của các heuristic trên một số phương diện. Ví dụ, có thể chúng ta không chỉ cần một giải pháp mà còn cần thuật toán để tìm con đường ngắn nhất dẫn đến đích. Một số tính chất dưới đây là cần xem xét đối với việc đánh giá hiệu quả của một heuristic :