Thuật toán leo đồi

Trong lập trình giải toán, các thuật toán tìm kiếm đóng một vai trò cực kỳ quan trọng và rất quen thuộc đối với chúng ta. Trong bài viết này, xin trình bày với bạn đọc một trong số các thuật toán tìm kiếm phổ biến: "Thuật toán leo đồi? (Hill Climbing Search).

Trước hết, ta nghiên cứu bài toán sau: Trò chơi n2-1 số (n ∈ N, n > 1).

Bài toán: Có n2-1 số mang các giá trị từ 1 tới n2-1 được sắp xếp vào một lưới các ô vuông kích thước n x n. Mỗi số đó được gọi là một quân cờ và lưới ô đó được gọi là bàn cờ. Có một vị trí của bàn cờ bỏ trống. Mỗi lần di chuyển quân, người chơi được phép chuyển một quân ở vị trí ô tiếp giáp cạnh với ô trống vào ô trống.

Yêu cầu: Từ một trạng thái ban đầu (sự sắp xếp ban đầu của các quân trên bàn cờ), hãy thực hiện các nước đi hợp lệ để thu được trạng thái kết thúc (trạng thái đích cần đạt được).

Ví dụ: với trò chơi 8 số ta minh họa trạng thái ban đầu và trạng thái kết thúc qua các hình vẽ dưới đây:



Để giải bài toán này, chúng ta sẽ nghĩ ngay tới việc xây dựng một cây tìm kiếm mà gốc của cây tương ứng với trạng thái xuất phát của bàn cờ. Các đỉnh khác của cây tương ứng với các trạng thái thu được do việc thực hiện các nước đi hợp lệ (các nước đi được phép thực hiện là: lên trên, xuống dưới, sang trái và sang phải). Với ví dụ trên, ta có cây tìm kiếm sau:



Tiếp đó, ta chỉ việc áp dụng các thuật toán thông dụng như: thuật toán tìm kiếm theo chiều rộng hoặcthuật toán tìm kiếm theo chiều sâu để tìm ra lời giải.

Việc suy nghĩ như trên xem ra có tính khả thi (đơn giản, dễ cài đặt), tuy nhiên, dễ nhận thấy rằng nếu số n lớn hơn, ta sẽ phải phát triển một số quá lớn các trạng thái trước khi phát hiện ra trạng thái đích. Những hạn chế về mặt thời gian và dung lượng bộ nhớ không cho phép thực hiện điều đó.

Trong thực tế, có nhiều bài toán mà số các trạng thái của nó là rất lớn (như cờ vua, cờ tướng...), thì việc giải bài toán chỉ có thể thực hiện nếu bằng một cách nào đó ta lược bỏ những trạng thái thừa, không cần thiết nhằm giảm số lượng trạng thái cần phát triển. Để làm được điều đó, phải sử dụng khéo léo các thông tin phản hồi nảy sinh trong quá trình tìm kiếm (các thông tin này còn gọi là thông tin cảm tính: Heuristic Information). Cách làm này được đưa ra nhằm mục đích lựa chọn được hướng tìm kiếm tốt nhất tại mỗi bước theo nghĩa: hướng đi đó nhanh dẫn tới trạng thái đích nhất và nhằm giảm công sức tìm kiếm.

Thuật toán tìm kiếm leo đồi đã đáp ứng được yêu cầu trên. Nội dung thuật toán được mô tả như sau:

Bước 1: Nếu trạng thái đầu trùng với trạng thái đích thì dừng ngay, ngược lại thì chuyển sang bước 2.

Bước 2:Sử dụng các quy tắc biến đổi để tạo ra 1 tập hợp các trạng thái từ trạng thái hiện thời (trong bài toán trên ta có 4 quy tắc biến đổi tương ứng với 4 phép di chuyển quân).

Bước 3: Với mỗi trạng thái trong tập hợp vừa tạo ra kiểm tra xem đó có phải là trạng thái đích hay không? Nếu phải thì ngừng việc tìm kiếm, nếu không phải thì ta kiểm tra xem trạng thái mới này có tốt hơn (gần trạng thái đích hơn) so với trạng thái đã có hay không? Nếu quả thật như vậy thì ghi nhận trạng thái này, ngược lại thì bỏ qua.

Bước 4: Trong các trạng thái được tạo ra (sau khi thực hiện các thao tác ở bước 3), ta ưu tiên phát triển trạng thái tốt nhất (trạng thái tốt nhất là trạng thái có tiềm năng dẫn tới đích nhanh nhất).

Bước này nhằm mục đích chuyển hướng tìm kiếm lời giải nhanh đến đích nhất.

Bước 5: Lặp lại từ bước 2.

Đến đây bạn đọc có thể nhận thấy thuật toán tìm kiếm leo đồi thực chất là thuật toán tìm kiếm theo chiều sâu, song tại mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đích nhất để phát triển trước. Vấn đề quan trọng là ở chỗ biết khai thác khéo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhanh quá trình tìm kiếm. Thông thường ta gắn mỗi trạng thái của bài toán với một số đo (1 hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó.

Như vậy: Nếu trạng thái hiện thời là u, theo bước 4 của thuật toán trên thì trạng thái v sẽ được phát triển tiếp theo nếu vẻ kề(u) và hàm đánh giá của v đạt gía trị max (hoặc min).

bạn nào siêng thì áp dụng giải thử bài toán trên nghe