Áp dụng tìm kiếm mù giải bài toán đố chở thuyền

Bài toán: Người và sói

Trên một vùng đất nọ, có 3 người và 3 con sói cùng sinh sống. Bỗng một hôm, vì nơi đây gặp thiên tai, họ phải di chuyển đến vùng đất khác nằm ở bên kia con sông. Chỉ có một chiếc thuyền trên sông, và mỗi thuyền chứa tối đa 2 người, tối thiểu là 1 người. Có một điều nguy hiểm rằng ở vùng đất cũ khi mà số lượng sói lớn hơn số lượng người thì người sẽ bị ăn thịt. Bạn hãy đưa ra một cách mà có thể đưa người và sói sang sông một cách an toàn mà không gặp bất kì trở ngại nào.

Giải:

Ta chọn biến đổi bài toán về không gian trạng thái:

-        Dạng biểu diễn trạng thái: Cây tìm kiếm – cụ thể: Tìm kiếm mù

-        Trạng thái: Một bộ ba (a,b,k) trong đó

o   Hệ số a: Số lượng người ở vùng đất cũ

o   Hệ số b: Số lượng sói ở vùng đất cũ

o   Hệ số k: Trạng thái của chiếc thuyền (1 khi có thuyền để đi, 0 khi không có thuyền để đi)

ð  Trạng thái ban đầu (3,3,1)

ð  Trạng thái kết thúc (0,0,0)

-        Toán tử: Chiếc thuyền chở người qua

o   Cụ thể: Giả sử tại trang thái ban đầu thuyền chở 1 người 1 sói qua. Khi đó: (3, 3, 1) (1,1)à (2,2,0); Sau đó người chèo thuyền về, khi đó (2,2,0) (1,0)-> (3,2,1)

ð  Toán tử là một bộ số (a,b) đại diện cho số lượng người và sói ở trên thuyền, còn hành động đi hay về dựa vào hệ số k.

Chuyển đổi không gian tìm kiếm trạng thái về cây tìm kiếm:

Ví dụ với độ sâu d = 2

Lựa chọn loại tìm kiếm:

Ta chọn tìm kiếm theo chiều rộng hoặc tìm kiếu sâu lặp.

Ta không thể chọn tìm kiếm theo chiều sâu. Lí do: Sẽ có trường hợp lặp vô hạn. Đó là trường hợp một đối tượng đi thuyền qua bên kia, rồi đi thuyền quay trở lại chỗ cũ

ð  Ta lựa chọn tìm kiếm theo chiều rộng

*Thuật toán

Nhắc lại về tìm kiếm theo chiều rộng: Ta sẽ ưu tiên phát triển trạng thái nào sinh ra trước

Ta sử dụng phương pháp hàng đợi (queue) để xử lí bài toán

Cho một tập L chứa các đỉnh (trạng thái) của cây tìm kiếm. L = {(3, 1, 1)}

Trạng thái ở vị trí đầu tiên danh sách L gọi là u₀

Bước 1: for do

               Bước 1.1: if (L = {}) then Trả kết quả không tìm thấy; Kết thúc;

Bước 1.2: Kiểm tra u₀:

Bước 1.2.1: if (u₀ có dạng (0, 0, 0)) then Trả kết quả; Kết thúc;

Bước 1.2.2: if (u₀ có b>a) then xóa u0 và continue;

Bước 1.3: Phát triển u₀ ra tập V gồm các trạng thái {v₀, v₁, …, v_n-1}

Bước 1.4: Xóa trạng thái u₀ ra khỏi danh sách L

Bước 1.5: Thêm tập V vào cuối danh sách L

Phân tích quá trình phát triển trạng thái u tại bước 1.3:

Xét ví dụ trên, trích:

o   “Cụ thể: Giả sử tại trang thái ban đầu thuyền chở 1 người 1 sói qua. Khi đó: (3, 3, 1) (1,1)à (2,2,0); Sau đó người chèo thuyền về, khi đó (2,2,0) (1,0)-> (3,2,1)”

Với (a, b, k) là trạng thái, và (x, y) là toán tử. Ta thấy rằng

(a, b, k) (x, y)-> (a-x, b-y, !k) khi k = 1

(a, b, k) (x, y)-> (a+x, b+y, !k) khi k = 0

ð  Đây là công thức toán tử cho quá trình phát triển trạng thái

Các toán tử sử dụng: 5 toán tử

(0, 1)(1, 0)(1, 1)(2, 0)(0, 2)

Tuy nhiên không phải lúc nào một trạng thái cũng có thể sử dụng cả 5 toán tử:

VD: (2, 1, 1) thì toán tử sử dụng là (0, 1)(1, 0)(1, 1)(2, 0)

        (2, 1, 0) thì toán tử sử dụng là (0, 1)(1,0)(1, 1)(0,2)

Dựa vào công thức toán tử cho quá trình phát triển trạng thái, ta rút ra được

(x,y) nhận khi

               x <= a và y <= b khi k = 1

               x <= (3 – a) và y <= (3 – b) khi k = 0;

Output: Kết quả ta tìm kiếm không phải là trạng thái cuối cùng, mà là một chuỗi trạng thái nối liền nhau bắt nguồn từ trạng thái đầu tiên đến trạng thái cuối cùng

Khi đã tới trạng thái cuối cùng, để biết được các trạng thái từ trạng thái đầu tiên đến trạng thái cuối cùng:

1>    Ta phải giữ lại danh sách trạng thái đã phát triển (Tạo một danh sách Q chứa các trạng thái đã phát triển)

2>    Ta phải đánh dấu được với mỗi trạng thái v nào đó sẽ có một trạng thái cha là u tương ứng

Ta sẽ sửa lại thuật toán như sau:

Bước 1.4: Chuyển trạng thái u₀ vào trong tập T (thêm vào cuối tập T)

Bước 1.3: Định nghĩa lại một node nào đó là một đối tượng gồm 2 trường:

               + Trường 1 (me): Lưu trữ trạng thái hiện tại v_i

+ Trường 2 (parent): Lưu trữ trạng thái cha, là trạng thái phát sinh ra trạng thái v_i

               (Với trạng thái ban đầu, thì trường parent sẽ là null)

Như vậy, “Trả kết quả” ở đây sẽ trả về một chuỗi các trạng thái từ trạng thái bắt đầu đến trạng thái kết thúc, và sẽ được tạo như sau

Cho v_final là trạng thái cuối cùng tìm được, với tập T = {q₀, q₁, …, q _n-1}

Cho một danh sách R với giá trị ban đầu là {v_final}, danh sách R là kết quả của bài toán

               Bước 1: Đặt t = v_final

Bước 2: for tập T dò từ dưới lên trên

                              Bước 2.1: If t.parent == q_i.me nào đó then

                                             Bước 2.1.1: Ghi lại q_i.me vào R theo hướng chèn vào đầu danh sách

                                             Bước 2.1.2: Gán t = q_i

Hoàn thiện bài toán!

Tổng kết lại các bước giải bài toán:

Một đỉnh (node) của cây tìm kiếm là một đối tượng xác định bởi 2 trạng thái

               + Trường 1 (me): Lưu trữ trạng thái hiện tại v_i

+ Trường 2 (parent): Lưu trữ trạng thái cha, là trạng thái phát sinh ra trạng thái v_i

Các bước giải bài toán:

Bước 1: for do

               Bước 1.1: if (L = {}) then Trả kết quả không tìm thấy; Kết thúc;

Bước 1.2: Kiểm tra u₀:

Bước 1.2.1: if (u₀ có dạng (0, 0, 0)) then Trả kết quả(u₀); Kết thúc;

Bước 1.2.2: if (u₀ có b>a) then xóa u0 và continue;

Bước 1.3: Phát triển u₀ ra tập V gồm các trạng thái {v₀, v₁, …, v_n-1}

Bước 1.4: Chuyển trạng thái u₀ vào trong tập T (thêm vào cuối tập T)

Bước 1.5: Thêm tập V vào cuối danh sách L

Hàm trả kết quả như đã ghi ở trên.
Code mô tả bài toán:

Nội dung bài viết được tạo bởi Lê Công Diễn.

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn