Bài toán và không gian trạng thái

Hãy tưởng tượng bạn đứng ở một thành phố và muốn tới một thành phố khác. Bạn có bản đồ, biết mình đang ở đâu, biết muốn tới đâu, và biết từ mỗi nơi có thể đi tiếp tới những nơi nào. Câu hỏi duy nhất còn lại là: đi theo lối nào. Rất nhiều bài toán AI, từ tìm đường, sắp xếp trò chơi ghép hình, tới lập kế hoạch cho robot, đều quy về đúng câu hỏi này: đi từ tình huống ban đầu tới tình huống đích bằng cách nào.

Con người giải những bài như vậy bằng trực giác, nhưng máy tính thì không có trực giác. Muốn máy giải được, ta phải mô tả bài toán thật rõ ràng và hình thức: liệt kê các tình huống có thể xảy ra, các bước đi hợp lệ, và điều kiện coi là đã xong. Cách mô tả đó gọi là không gian trạng thái. Khi đã có không gian trạng thái, việc giải bài toán trở thành việc dò đường trong đó, và đây là lúc các thuật toán tìm kiếm vào cuộc.

Thử ngay: dò một đường đi từ A tới G

Dưới đây là một không gian trạng thái nhỏ vẽ dưới dạng đồ thị: mỗi đỉnh là một trạng thái, mỗi cạnh là một bước đi hợp lệ. Trạng thái đầu là A, đích là G. Một lời giải là một đường đi nối A tới G.

Không gian trạng thái: đỉnh là trạng thái, cạnh là hành động

Biên (frontier)

(rỗng)

Đã thăm (explored)

(rỗng)

Trạng thái đầu là A (góc trái). Mọi tìm kiếm đều bắt đầu từ đây.

1/30.5×1×2×

đang mở rộng trong biên đã thăm đường đi

Năm thành phần của một bài toán tìm kiếm

Mọi bài toán tìm kiếm, dù là tìm đường trên bản đồ hay giải trò xếp hình, đều mô tả được bằng đúng năm thành phần dưới đây. Nắm chắc năm thành phần này là nắm được nửa bài học.

• Trạng thái đầu: nơi xuất phát, tức tình huống lúc bắt đầu (ví dụ đang đứng ở thành phố A). Mỗi bài toán chỉ có một trạng thái đầu.
• Hành động: tập các bước đi hợp lệ từ một trạng thái. Từ mỗi trạng thái, số hành động có thể khác nhau; ở ngã tư đông nhánh thì nhiều lựa chọn, ở ngõ cụt thì không có.
• Hàm chuyển (còn gọi là mô hình chuyển): cho biết một hành động đưa trạng thái hiện tại sang trạng thái mới nào. Viết gọn là Ket_qua(trang_thai, hanh_dong) = trang_thai_moi.
• Kiểm tra đích: một phép thử trả lời "trạng thái hiện tại có phải đích chưa". Có bài chỉ một đích duy nhất, có bài nhiều đích cùng thỏa (ví dụ "tới bất kỳ trạm xăng nào").
• Chi phí đường đi: tổng chi phí của các bước trên đường đi, tính bằng cách cộng chi phí từng bước. Mặc định mỗi bước tốn 1, nhưng có thể là quãng đường, thời gian, hay tiền.

Ba thành phần đầu (trạng thái đầu, hành động, hàm chuyển) định nghĩa không gian: chúng sinh ra mọi trạng thái có thể tới được. Hai thành phần sau (kiểm tra đích, chi phí) định nghĩa mục tiêu: đâu là đích và ta muốn tối ưu điều gì. Tách bạch như vậy giúp cùng một không gian trạng thái có thể phục vụ nhiều mục tiêu khác nhau: vẫn bản đồ ấy, đổi chi phí từ quãng đường sang thời gian là ta có ngay bài toán "đi nhanh nhất" thay vì "đi ngắn nhất".

Một điều dễ bỏ sót: trạng thái phải chứa đủ mọi thứ cần để quyết định bước tiếp theo, và không chứa gì thừa. Ở bài tìm đường, biết mình đang ở thành phố nào là đủ. Nhưng nếu bài toán đổi thành "đi qua đủ ba thành phố rồi mới về đích" thì trạng thái buộc phải gồm cả vị trí lẫn tập thành phố đã ghé, vì thiếu phần sau ta không biết đã xong nhiệm vụ hay chưa.

Tập hợp mọi trạng thái và các phép chuyển giữa chúng tạo thành một đồ thị: mỗi đỉnh là một trạng thái, mỗi cạnh là một hành động. Lời giải là một đường đi từ trạng thái đầu tới đích. Trong nhiều đường đi tới đích, đường có tổng chi phí nhỏ nhất gọi là lời giải tối ưu.

Bốn ví dụ cụ thể

Ví dụ 1: tìm đường trên bản đồ

Đây là bài toán quen thuộc nhất. Trạng thái là thành phố đang đứng; trạng thái đầu là thành phố xuất phát; hành động là đi tới một thành phố kề qua một con đường; hàm chuyển chính là bản đồ (đường nối những thành phố nào); kiểm tra đích là "đã tới thành phố cần tới chưa"; chi phí mỗi bước là độ dài con đường. Không gian trạng thái ở đây nhỏ và trực quan, đúng bằng số thành phố trên bản đồ.

Ví dụ 2: trò 8-puzzle

Trò 8-puzzle là một bảng 3x3 chứa tám ô số từ 1 tới 8 và một ô trống; mỗi bước ta trượt một ô kề ô trống vào chỗ trống, mục tiêu là đưa các số về đúng thứ tự. Ở đây trạng thái là một cách sắp xếp cụ thể của chín ô; trạng thái đầu là thế cờ ban đầu; hành động là trượt ô trống lên, xuống, trái, phải (tối đa bốn hành động, ít hơn nếu ô trống nằm ở biên); hàm chuyển đổi chỗ ô trống với ô kề; kiểm tra đích là "các số đã về đúng thứ tự chưa"; chi phí mỗi bước là 1 vì ta muốn ít nước đi nhất.

Điểm đáng chú ý: 8-puzzle có tới 9! / 2 = 181440 trạng thái hợp lệ. Ta không liệt kê sẵn từng đó trạng thái vào bộ nhớ; thay vào đó chỉ giữ trạng thái đầu và sinh dần các trạng thái kề khi cần. Đây là ý tưởng cốt lõi của tìm kiếm: khám phá không gian một cách lười biếng, chỉ mở rộng phần thật sự cần chạm tới.

Ví dụ 3: bài toán truyền tin

Một gói tin cần đi từ máy chủ nguồn tới máy chủ đích qua một mạng các nút trung chuyển. Trạng thái là nút mạng gói tin đang nằm; hành động là chuyển gói sang một nút kề; hàm chuyển là sơ đồ đấu nối của mạng; kiểm tra đích là "gói đã tới nút đích chưa".

Cái hay nằm ở chi phí. Lấy chi phí mỗi bước bằng 1, ta tìm đường qua ít chặng nhất. Lấy chi phí là độ trễ của liên kết, ta tìm đường nhanh nhất, và đường ấy hoàn toàn có thể dài hơn về số chặng. Vẫn một không gian, hai mục tiêu, hai lời giải tối ưu khác nhau.

Ví dụ 4: xếp lịch

Cần xếp năm môn học vào các ca trong tuần, sao cho hai môn chung giảng viên thì không trùng ca. Trạng thái ở đây không phải một vị trí, mà là một phép gán từng phần: những môn đã xếp và ca đã chọn cho mỗi môn; trạng thái đầu là phép gán rỗng. Hành động là gán một ca hợp lệ cho môn chưa xếp tiếp theo; kiểm tra đích là "đã xếp đủ năm môn mà không vi phạm ràng buộc nào chưa". Chi phí là 1 mỗi bước nếu chỉ cần một lịch hợp lệ, hoặc là mức phạt (số tiết vào ca tối) nếu ta muốn lịch đẹp nhất chứ không chỉ chạy được.

Ví dụ này cho thấy sức khái quát của khuôn khổ: nhiều bài toán trông chẳng liên quan gì tới "đi lại" vẫn quy về đúng một câu hỏi dò đường trong không gian trạng thái.

Cây tìm kiếm và đồ thị trạng thái

Cần phân biệt hai khái niệm dễ nhầm. Đồ thị trạng thái là bản đồ toàn bộ bài toán: mỗi trạng thái xuất hiện đúng một lần. Cây tìm kiếm là những đường đi mà thuật toán thực sự dò trong lúc chạy: gốc là trạng thái đầu, mỗi nhánh là một lần mở rộng. Một trạng thái có thể tới được bằng nhiều đường khác nhau, nên nó có thể xuất hiện nhiều lần trong cây tìm kiếm dù chỉ là một đỉnh trong đồ thị.

Ví dụ sắc nhất: nếu A nối với B và B nối lại với A, cây tìm kiếm sẽ có nhánh A rồi B rồi A rồi B, kéo dài mãi. Đồ thị chỉ hai đỉnh, nhưng cây tìm kiếm vô hạn. Ngay cả khi không có chu trình, cây vẫn phình vô ích: trạng thái nào tới được bằng ba đường khác nhau sẽ bị mở rộng ba lần, và cả cây con bên dưới nó cũng bị dựng lại ba lần.

Cách khắc phục là giữ một tập đã thăm (còn gọi là danh sách đóng): trước khi mở rộng một trạng thái, kiểm tra xem nó đã từng được mở rộng chưa; nếu rồi thì bỏ qua. Kỹ thuật này biến tìm kiếm trên cây thành tìm kiếm trên đồ thị và sẽ dùng lại xuyên suốt các bài sau. Cái giá phải trả là bộ nhớ: tập đã thăm có thể lớn bằng cả không gian trạng thái. Đây là một đánh đổi kinh điển, đổi bộ nhớ lấy thời gian.

Độ phức tạp: vì sao không gian phình nhanh

Gọi b là hệ số phân nhánh (số hành động trung bình tại mỗi trạng thái) và d là độ sâu của lời giải. Từ trạng thái đầu sinh b trạng thái, mỗi trạng thái đó lại sinh b trạng thái nữa, nên tới độ sâu d số trạng thái cỡ b^d. Đây là tăng theo hàm mũ: với b = 10 và d = 8, ta đã có 10^8, tức trăm triệu trạng thái. Vì lẽ đó, một thuật toán tìm kiếm tốt phải khéo léo chọn thứ tự mở rộng để chạm tới đích trước khi không gian nổ tung, chứ không phải liệt kê mù toàn bộ.

Cho cụ thể: với 8-puzzle, b xấp xỉ 3. Một lời giải sâu 20 nước ứng với cỡ 3^20, khoảng 3,5 tỉ nút, dù toàn bộ không gian chỉ có 181440 trạng thái tới được. Chênh lệch khổng lồ ấy chính là hình phạt cho việc không loại trạng thái lặp.

Cần nhớ b và d giữ hai vai trò khác nhau trong công thức b^d: b là cơ số, còn d nằm ở số mũ. Mỗi bậc sâu thêm nhân số nút với b, nên chi phí không cộng thêm mà nhân lên sau mỗi bước. Cờ vua có b cỡ 35 và một ván cỡ 80 nước đi; không máy nào duyệt hết 35^80, nên mọi chương trình chơi cờ đều phải cắt tỉa chứ không thể duyệt cạn.

Đánh giá một thuật toán tìm kiếm

Từ bài sau ta sẽ gặp nhiều thuật toán (BFS, DFS, UCS, A-sao). Muốn so sánh chúng cho có cơ sở, hãy tập hỏi đủ bốn câu này với mọi thuật toán:

• Tính đầy đủ (completeness): nếu bài toán có lời giải, thuật toán có chắc chắn tìm ra không? Một thuật toán không đầy đủ có thể chạy mãi hoặc bỏ sót lời giải dù nó tồn tại.
• Tính tối ưu (optimality): lời giải tìm được có phải là lời giải rẻ nhất không? Tìm ra một đường đi là một chuyện; tìm ra đường đi tốt nhất là chuyện khó hơn hẳn.
• Độ phức tạp thời gian: cần mở rộng bao nhiêu nút trước khi tới đích, tính theo b và d.
• Độ phức tạp bộ nhớ: cùng lúc phải giữ bao nhiêu nút. Tiêu chí này hay bị xem nhẹ, nhưng thực tế bộ nhớ mới là thứ vỡ trước: máy hết RAM từ lâu trước khi ta hết kiên nhẫn chờ.

Bốn tiêu chí thường xung đột, và không thuật toán nào thắng cả bốn. Đầy đủ và tối ưu thường đổi bằng bộ nhớ; tiết kiệm bộ nhớ thường đổi bằng việc mất tính tối ưu. Chọn thuật toán, do đó, là chọn đánh đổi nào chấp nhận được cho bài toán trước mắt.

Biểu diễn đồ thị bằng Python

Cách gọn nhất là dùng một dict: mỗi trạng thái ánh xạ tới danh sách các trạng thái kề.

# do_thi[X] = danh sach trang thai di toi duoc tu X
do_thi = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["G"],
    "F": ["G"],
    "G": [],
}

bat_dau, dich = "A", "G"

Bài tập thực hành

Bài tập 1: liệt kê mọi đường đi

Với đồ thị ở trên, hãy liệt kê tất cả các đường đi từ A tới G (không lặp đỉnh).

Gợi ý

Lần theo các cạnh từ A: nhánh qua B dẫn tới E rồi G, nhánh qua C dẫn tới F rồi G. Có đúng hai đường: A → B → E → G và A → C → F → G, cả hai đều dài 3 bước.

Bài tập 2: mô hình hóa một bài toán quen thuộc

Mô tả bài toán "đi từ nhà tới trường qua các ngã tư" dưới dạng năm thành phần của một bài toán tìm kiếm.

Gợi ý

Trạng thái = vị trí đang đứng (một ngã tư); trạng thái đầu = nhà; hành động = rẽ sang ngã tư kề; hàm chuyển = bản đồ đường; kiểm tra đích = đã tới trường chưa; chi phí = quãng đường (hoặc thời gian) mỗi đoạn.

Tự kiểm tra

Đồ thị trạng thái của một bài toán có đúng 12 đỉnh. Cây tìm kiếm của nó có thể có bao nhiêu nút?

Có thể là vô hạn. Đây là chỗ hay nhầm nhất: 12 là số trạng thái phân biệt trong đồ thị, còn cây tìm kiếm đếm số đường đi mà thuật toán dò qua. Chỉ cần đồ thị có một chu trình, thuật toán không loại trạng thái lặp sẽ đi vòng mãi. Ngay cả khi không có chu trình, một trạng thái tới được bằng nhiều đường vẫn xuất hiện nhiều lần trong cây. Giữ tập đã thăm là cách kéo cây tìm kiếm về lại kích thước của đồ thị.

Vì sao trong bài toán truyền tin, đường đi qua ít chặng nhất chưa chắc là đường nhanh nhất?

Vì "ít chặng nhất" tối ưu theo chi phí mỗi bước bằng 1, còn "nhanh nhất" tối ưu theo chi phí là độ trễ. Hai hàm chi phí khác nhau thì hai lời giải tối ưu khác nhau: một đường 2 chặng qua hai liên kết vệ tinh chậm hoàn toàn có thể tốn nhiều thời gian hơn một đường 5 chặng toàn cáp quang. Bài học: lời giải tối ưu chỉ có nghĩa khi đã nói rõ tối ưu theo chi phí nào, và chọn nhầm hàm chi phí thì thuật toán vẫn chạy đúng nhưng trả về đáp án sai mục tiêu.

Câu hỏi tự kiểm

Kiểm tra nhanh: không gian trạng thái0/4 đúngchưa trả lời

1. 1Năm thành phần của một bài toán tìm kiếm gồm những gì?
2. 2Đồ thị trạng thái của một bài toán có đúng 12 đỉnh. Cây tìm kiếm của nó có thể có bao nhiêu nút?
3. 3Trò 8-puzzle có bao nhiêu trạng thái tới được?
4. 4Trong công thức b^d, vai trò của b và d khác nhau ra sao?

Tóm tắt

• Mô hình hóa một bài toán là mô tả đủ năm thành phần: trạng thái đầu, hành động, hàm chuyển, kiểm tra đích, chi phí. Ba phần đầu định nghĩa không gian, hai phần sau định nghĩa mục tiêu.
• Trạng thái phải chứa đủ và chỉ đủ thông tin để quyết định bước tiếp theo.
• Khuôn khổ này bao được cả tìm đường, 8-puzzle, truyền tin lẫn xếp lịch.
• Đồ thị trạng thái chứa mỗi trạng thái đúng một lần; cây tìm kiếm là những đường đi thuật toán thực sự dò, nên có thể lớn hơn nhiều, thậm chí vô hạn. Giữ tập đã thăm để chặn việc lặp trạng thái.
• Không gian phình theo hàm mũ b^d, và d mới là kẻ nguy hiểm.
• So sánh thuật toán bằng bốn tiêu chí: đầy đủ, tối ưu, thời gian, bộ nhớ. Không thuật toán nào thắng cả bốn.

Nhầm lẫn thường gặp

Có ba lỗi hay mắc khi mô hình hóa bài toán. Thứ nhất, lẫn trạng thái với hành động: trạng thái là "đang ở đâu", hành động là "làm gì để đi tiếp"; ở bài bản đồ, thành phố là trạng thái còn con đường là hành động. Thứ hai, tưởng phải liệt kê hết mọi trạng thái trước khi tìm: thực tế ta chỉ giữ trạng thái đầu và sinh dần các trạng thái kề khi cần, nếu không thì 8-puzzle với 181440 trạng thái đã quá tải. Thứ ba, quên chi phí không phải lúc nào cũng bằng 1: khi các cạnh có chi phí khác nhau thì "đường ít bước nhất" và "đường rẻ nhất" là hai thứ khác nhau, chọn nhầm sẽ ra lời giải sai mục tiêu.

Ghi nhớ

Mọi bài toán tìm kiếm gồm năm phần: trạng thái đầu, hành động, hàm chuyển, kiểm tra đích, chi phí. Không gian trạng thái là một đồ thị; lời giải là một đường đi tới đích. Việc còn lại là chọn thuật toán dò đường, bắt đầu từ BFS ở bài sau.