Chiến lược tìm kiếm xâu lặp

Chiến lược tìm kiếm xâu lặp
Đinh Quang Huy - Đỗ Đức Đông
Khi chúng ta muốn giải quyết một vấn đề nào đó bằng tìm kiếm, đầu tiên ta phải xác định không gian tìm kiếm. Không gian tìm kiếm bao gồm tất cả các đối tượng mà ta cần quan tâm tìm kiếm. Nó có thể là không gian liên tục hoặc nó cũng có thể là không gian các đối tượng rời rạc. 
Muốn biểu diễn một vấn đề trong không gian trạng thái ta cần xác định các yếu tố sau: 
* Trạng thái ban đầu. 
* Một tập hợp các toán tử. Trong đó mỗi toán tử mô tả một hành động hoặc một phép biến đổi có thể đưa một trạng thái tới một trạng thái khác. Tập hợp tất cả các trạng thái có thể đạt tới từ trạng thái ban đầu bằng cách áp dụng dãy toán tử lập thành không gian trạng thái của vấn đề. 
Ta sẽ ký hiệu không gian trạng thái là U, trạng thái ban đầu là u0 (u0 thuộc U). Mỗi toán tử R có thể xem như một ánh xạ R:U õ†’ U. Nói chung R là một ánh xạ không xác định khắp nơi trên U. 
* Một tập hợp T các trạng thái kết thúc (trạng thái đích). T là tập con của không gian U. Các trạng thái đích có thể được mô tả là các trạng thái thỏa mãn một số điều kiện nào đó. 
Khi chúng ta biểu diễn một vấn đề thông qua các trạng thái và các toán tử, thì việc tìm nghiệm của bài toán được quy về việc tìm đường đi từ trạng thái ban đầu tới trạng thái đích. (Một đường đi trong không gian trạng thái là một dãy toán tử dẫn một trạng thái tới một trạng thái khác). 
Sau khi xác định xong không gian tìm kiếm, ta cần chọn chiến lược tìm kiếm. Có hai chiến lược tìm kiếm mù: Tìm kiếm theo bề rộng và tìm kiếm theo bề sâu. 
1. Tìm kiếm theo bề rộng. Tư tưởng trong tìm kiếm theo bề rộng là tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái được sinh ra trước các trạng thái chờ phát triển khác. 
Chúng ta sử dụng danh sách L để lưu các trạng thái đã được sinh ra và chờ được phát triển. Muc tiêu của tìm kiếm trong không gian trạng thái là tìm đường đi từ trạng thái ban đầu tới trạng thái đích, do đó trong quá trình tìm kiếm ta cần lưu lại vết của đường đi. Ta có thể sử dụng mảng father để lưu lại vết của đường đi, father[v]=u nếu cha của đỉnh v là u. 
Thủ tục tìm kiếm theo bề rộng viết theo ngôn ngữ giả PASCAL 
Procedure Breadth_First_Search; 
Begin 
1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu 
2. Lặp 
2.1. if L rỗng then 
begin 
thông báo tìm kiếm thất bại; exit; 
end ; 
2.2. loại trạng thái u ở đầu danh sách L; 
2.3. if u là trạng thái kết thúc then 
begin 
thông báo tìm kiếm thành công; exit; 
end; 
2.4. for mỗi trạng thái v kề u do 
begin 
đặt v vào cuối danh sách L; 
father[v]=u; 
end; 
End; 
Nhận xét: 
Trong tìm kiếm bề rộng, trạng thái nào sinh ra trước sẽ được phát triển trước (theo nguyên tắc FIFO), do đó danh sách L được xử lý như hằng đợi (Queue). 
Nếu bài toán có nghiệm (tồn tại đường đi từ trạng thái ban đầu đến trạng thái đích), thì thuật toán tìm kiếm theo bề rộng sẽ tìm ra nghiệm, đồng thời đường đi tìm được là ngắn nhất. Trong trường hợp bài toán vô nghiệm và không gian trạng thái là hữu hạn, thuật toán sẽ dừng và cho thông báo vô nghiệm. 
Đánh giá độ phức tạp: Giả sử rằng, mỗi trạng thái khi được phát triển sẽ sinh ra b trạng thái kề. Ta gọi b là nhân tố nhánh. Giả sử rằng, nghiệm của bài toán là đường đi có độ dài d. Bởi vì nghiệm có thể được tìm ra tại một đỉnh bất kỳ ở mức d của cây tìm kiếm, do đó số đỉnh cần xem xét để tìm ra nghiệm là: 1 + b + b2 + ... + bd-1 + k. 
Trong đó k có thể là 1,2,...,bd. Do đó số đỉnh lớn nhất cần xem xét là: 
1 + b + b2 +...+ bd. 
Như vậy độ phức tạp thời gian của thuật toán tìm kiếm theo bề rộng là: O(bd) 
Độ phức tạp không gian cũng là O(bd), bởi vì ở đây cần lưu vào danh sách L tất cả các đỉnh của cây tìm kiếm ở mức d, số các đỉnh này là bd. 
2. Tìm kiếm theo độ sâu. 
Tư tưởng trong tìm kiếm theo độ sâu là tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái được sinh ra sau cùng trong số các trạng thái chờ phát triển. 
Cũng như trong tìm kiếm theo bề rộng, chúng ta cũng sử dụng danh sách L để lưu các trạng thái đã được sinh ra và chờ được phát triển và sử dụng mảng father để lưu lại vết của đường đi, father[v]=u nếu cha của đỉnh v là u. 
Thủ tục tìm kiếm theo độ sâu viết theo ngôn ngữ giả PASCAL 
Procedure Depth_First_Search; 
Begin 
2. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu 
2. Lặp 
2.1. if L rỗng then 
begin 
thông báo tìm kiếm thất bại; exit; 
end; 
2.2. loại trạng thái u ở đầu danh sách L; 
2.3. if u là trạng thái kết thúc then 
begin 
thông báo tìm kiếm thành công; exit; 
end; 
2.4. for mỗi trạng thái v kề u do 
begin 
đặt v vào đầu danh sách L; 
father[v]=u; 
end; 
End; 
Nhận xét: 
Trong tìm kiếm độ, trạng thái nào sinh ra sau sẽ được phát triển trước (theo nguyên tắc LIFO), do đó danh sách L được xử lý như ngăn xếp (Stack). 
Thuật toán tìm kiếm theo bề rộng luôn tìm ra nghiệm nếu bài toán có nghiệm. Song không phải với bất kỳ bài toán có nghiệm nào thuật toán tìm kiếm theo chiều sâu cũng tìm ra nghiệm. Nếu bài toán có nghiệm và không gian trạng thái hữu hạn, thì thuật toán tìm kiếm theo độ sâu sẽ tìm ra nghiệm. Tuy nhiên, trong trường hợp không gian trạng thái vô hạn, thì có thể không tìm ra nghiệm, lý do là ta luôn đi xuống theo độ sâu, nếu ta đi theo một nhánh vô hạn mà nghiệm không nằm trong nhánh đó thì thuật toán sẽ không dừng, Do vậy không nên áp dụng tìm kiếm theo độ sâu cho các bài toán có cây tìm kiếm chứa các nhánh vô hạn. 
Đánh giá độ phức tạp:
Giả sử rằng, nghiệm của bài toán là đường đi có độ dài d, cây tìm kiếm có nhân tố nhánh là b và có chiều cao là d. Có thể xảy ra, nghiệm là đỉnh ngoài cùng bên phải trên mức d của cây tìm kiếm, do đó độ phức tạp thời gian của cây tìm kiếm theo độ sâu trong trường hợp xấu nhất là O(bd), tức là cũng như tìm kiếm theo bề rộng. Tuy nhiên trên thực tế đối với nhiều bài toán tìm kiếm theo độ sâu thực sự nhanh hơn tìm kiếm theo bề rộng. Lý do là tìm kiếm theo bề rộng phải xem xét toàn bộ cây tìm kiếm tới mức (d-1), rồi mới xem xét các đỉnh ở mức d. Còn trong tìm kiếm theo độ sâu, có thể ta chỉ cần xem xét một bộ phận nhỏ của cây tìm kiếm thì đã tìm ra nghiệm. 
Để đánh giá độ phức tạp không gian của tìm kiếm theo độ sâu ta có nhận xét rằng, khi phát triển một đỉnh u trên cây tìm kiếm theo độ sâu, ta chỉ cần lưu các đỉnh chưa được phát triển mà chúng là các đỉnh con của các đỉnh nằm trên đường đi từ gốc tới đỉnh u. Như vậy đối với cây tìm kiếm có nhân tố nhánh b và độ sâu lớn nhất là d, ta chỉ cần lưu ít hơn db đỉnh. Do đó độ phức tạp không gian của tìm kiếm theo độ sâu là O(db), trong khi đó tìm kiếm theo bề rộng đòi hỏi không gian bộ nhớ O(bd). 
Đó là hai chiến lược tìm kiếm mù rất phổ biến và thông dụng, song điều tôi muốn thảo luận với bạn đọc là sự kết hợp hai chiến lược này để tận dụng được các thế mạnh của mỗi chiến lược. Đó là chiến lược tìm kiếm sâu lặp. 
3. Tìm kiếm sâu lặp. 
Nếu cây tìm kiếm chứa nhánh vô hạn, khi sử dụng tìm kiếm theo độ sâu, ta có thể mắc kẹt ở nhánh đó và không tìm ra nghiệm. Để khắc phục hoàn cảnh đó, ta chỉ tìm kiếm độ sâu ở mức d nào đó. Nếu không tìm ra nghiệm, ta tăng độ sâu lên d+1. Quá trình trên được lặp lại lại với d lần lượt là: 1, 2,... đến một độ sâu max nào đó. Như vậy thuật toán tìm kiếm sâu lặp sẽ sử dụng thủ tục tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo độ sâu d nào đó rồi quay lên. 
Trong thủ tục tìm kiếm sâu hạn chế, d là tham số độ sâu, mảng depth ghi lại độ sâu của mỗi đỉnh. 
Procedure Depth_Limited_Search(d); 
Begin 
1. khởi tạo danh sách L chỉ chứa trạng thái u0; 
depth[u0]=0; 
2. Lặp 
1.1. if L rỗng then 
begin 
thông báo thất bại; exit; 
end; 
1.2. loại trạng thái u ở đầu danh sách L; 
1.3. if u là trạng thái kết thúc then 
begin 
thông báo thành công; exit; 
end; 
1.4. if depth[u]<=d then 
for mỗi trạng thái v kề u do 
begin 
đặt v vào đầu danh sách L; 
depth[v]:=depth[u]+1; 
end; 
End ; 
Procedure Depth_Deepening_Search; 
Begin 
For d:=0 to max do 
begin 
Depth_Limited_Search(d); 
if thành công then exit; 
end; 
End; 
Nhận xét: Kỹ thuật tìm kiếm sâu lặp kết hợp được các ưu điển của tìm kiếm theo bề rộng và tìm kiếm theo độ sâu. Chúng ta có một số nhận xét sau: 
- Cũng như tìm kiếm theo bề rộng, tìm kiếm sâu lặp luôn tìm ra nghiệm (nếu bài toán có nghiệm), miễn là ta chọn độ sâu max đủ lớn. 
- Trong tìm kiếm sâu lặp chỉ cần không gian nhớ như tìm kiếm theo độ sâu. 
- Trong tìm kiếm sâu lặp, ta phải phát triển lặp lại nhiều lần cùng một trạng thái. Điều đó làm cho ta có cảm giác rằng, tìm kiếm sâu lặp lãng phí nhiều thời gian. Thực ra thời gian cho phát triển lặp lại các trạng thái là không đáng kể so với thời gian tìm kiếm theo bề rộng. Thật vậy, mỗi lần gọi thủ tục tìm kiếm sâu hạn chế tới mức d, nếu cây tìm kiếm có nhân tố nhánh là b, thì số đỉnh cần phát triển là: 1 + b + b2 + ...+ bd. 
Nếu nghiệm ở độ sâu d, thì trong tìm kiếm sâu lặp, ta phải gọi thủ tục tìm kiếm sâu hạn chế với độ sâu lần lượt là: 0, 1, 2, ..., d. Do đó các đỉnh ở mức 1 phải phải phát triển lặp d lần, các đỉnh ở mức 2 lặp d-1 lần, ... , các đỉnh ở mức d lặp 1 lần. Như vậy tổng số đỉnh cần phát triển trong tìm kiếm sâu lặp là: (d+1)1 + db + (d-1)b2 + ...+ 2bd-1 + 1bd. 
Do đó thời gian tìm kiếm sâu lặp là O(bd). 
Tóm lại, thời gian tìm kiếm sâu lặp có độ phức tạp thời gian là O(bd) - như trong tìm kiếm theo bề rộng, và có độ phức tạp không gian là O(bd) - như tìm kiếm theo độ sâu. Nói chung, chúng ta nên áp dụng tìm kiếm sâu lặp cho các vấn đề có không gian trạng thái lớn và độ sâu của nghiệm không biết trước. Có thể nói rằng, đây là chiến lược tốt nhất trong các chiến lược tìm kiếm mù. 
4. Các trạng thái lặp. 
Bạn đọc sẽ thắc mắc là trong quá trình phát triển các trạng thái có thể sinh ra các trạng thái lặp. Đúng là như vậy, trong cả ba chiến lược trên: Tìm kiếm theo bề rộng, tìm kiếm theo chiều sâu và cả tìm kiếm sâu lặp đều có khả năng sinh ra các trạng thái đã được phát triển. Điều này sẽ làm lãng phí rất nhiều thời gian để phát triển lại các trạng thái. Để giải quyết vấn đề này ta có các giải pháp như sau: 
- Khi phát triển đỉnh u, không sinh ra các đỉnh trùng với cha của đỉnh u. 
- Khi phát triển đỉnh u, không sinh ra các đỉnh trùng với một đỉnh nào đó nằm trên đường đi dẫn tới u. 
- Không sinh ra các đỉnh mà nó đã được sinh ra, tức là chỉ sinh ra các đỉnh mới. 
Hai giải pháp đầu dễ cài đặt và không tốn nhiều thời gian và không gian nhớ, tuy nhiên các giải pháp này không tránh được hết các trạng thái lặp (song cũng khá tốt). Để thực hiện giải pháp thứ ba ta cần xác định một hàm f ánh xạ (hàm không quá phức tạp) các trạng thái vào tập số nguyên tương ứng 1 - 1 (thường là từ 0 trở đi) lưu lại các trạng thái đã phát triển bằng cách lưu lại ánh xạ của nó và kiểm tra xem một trạng thái có phải lần đầu sinh ra không. Chúng ta có thể cài đặt bằng bảng băm đối với tập ánh xạ rời rạc và sử dụng mảng để đánh dấu (sử dụng kỹ thuật nén bít!) nếu tập ánh xạ là liên tục và hữu hạn. 
Ta sẽ thử nhiệm với một bài toán cụ thể sau: 
Đề bài: 
Chúng ta có bảng NxN (N<=5), trong đó có một ô chứa số 0 và các ô còn lại chứa các số nguyên dương. 
Ví dụ ta có bảng sau: 
Ta có thể đổi chỗ 2 ô cho nhau, ô kề cạnh ô số 0 và ô số 0 để được bảng mới. Ví dụ ta đổi chỗ ô (2,3) với ô (3,3) để được bảng sau: 
Bài toán đặt ra là: Cho trước trạng xuất phát và trạng thái đích. Hãy tìm cách biến đổi để đưa trạng thái xuất phát về trạng thái đích với số lần đổi chỗ là ít nhất. 
Trạng thái đích: 
Giải: 
Bước 1: Xác định không gian trạng thái. 
- Trạng thái ban đầu là bảng xuất phát. 
- Tương ứng với qui tắc đổi chỗ với ô số 0, ta có bốn toán tử: Đổi chỗ với ô ở trên, đổi chỗ với ô ở dưới, đổi chỗ với ô bên trái, đổi chỗ với ô bên phải. 
- Trạng thái kết thúc là bảng đích. 
Bước 2: Chọn chiến lược tìm kiếm sâu lặp để giải. Để đơn giản chương trình sử dụng giải pháp một tránh trạng thái lặp, không sinh các đỉnh trùng với cha của u. 
Với chiến lược tìm kiếm sâu lặp rất dễ cài đặt và ngắn gọn.. Với bộ test mà số bước biến đổi ít nhất cần dùng mà lớn thì thuật toán bế tắc (độ phức tạp thời gian quá lớn), song xin nhắc lại đây là chiến lược tìm kiếm mù tốt nhất. 
Một số test thử nhiệm: