Giải ngược từ đích là cách suy luận bắt đầu từ trạng thái mục tiêu và hỏi "bước ngay trước đó phải là gì?", lặp lại cho tới khi gặp trạng thái xuất phát. Với những câu đố mà từ điểm xuất phát có quá nhiều lựa chọn nhưng đích lại rất "hẹp" — như câu đố trượt trên băng, nơi chỉ vài vị trí có thể dừng đúng ở đích — đi ngược nhanh hơn đi xuôi rất nhiều. Máy tính dùng cùng ý tưởng để tính trước kết quả cho mọi thế cờ tàn, và các nhà thiết kế câu đố dùng nó để "sinh ngược" những màn đố có lời giải chắc chắn.
Vì sao đi ngược lại dễ hơn
Hãy hình dung một cái cây: từ gốc (xuất phát) mọc ra rất nhiều cành, cành nào cũng chia nhánh. Đích là một chiếc lá. Đi từ gốc lên, ở mỗi chỗ rẽ phải đoán chọn cành nào. Đi từ chiếc lá xuống, chỉ có một con đường duy nhất về gốc.
Câu đố thật không phải cây hoàn hảo, nhưng thường có tính chất tương tự: số trạng thái "dẫn tới đích" ít hơn nhiều so với số trạng thái "đi ra từ xuất phát". Đi ngược giúp thu hẹp không gian tìm kiếm.
Ví dụ kinh điển: bài toán đong nước
Có một bình 3 lít và một bình 5 lít, không có vạch chia, một vòi nước. Làm sao đong được đúng 4 lít?
Suy nghĩ ngược
- Đích: bình 5 lít chứa 4 lít.
- Ngay trước đó có thể là gì? Bình 5 lít đầy (5 lít), rót sang bình 3 lít đang chứa 2 lít cho tới khi bình 3 lít đầy — bình 5 lít còn 4 lít. Vậy cần trạng thái: bình 5 lít đầy, bình 3 lít có 2 lít.
- Làm sao có 2 lít trong bình 3 lít? Đổ đầy bình 5 lít, rót sang bình 3 lít cho đầy — bình 5 lít còn 2 lít. Đổ bỏ bình 3 lít, rót 2 lít từ bình 5 sang bình 3.
- Bây giờ đã có trạng thái cần: đổ đầy bình 5 lít, bình 3 lít có 2 lít.
Lời giải xuôi
| Bước | Thao tác | Bình 5 lít | Bình 3 lít |
|---|---|---|---|
| 1 | Đổ đầy bình 5 lít | 5 | 0 |
| 2 | Rót từ bình 5 sang bình 3 cho đầy | 2 | 3 |
| 3 | Đổ bỏ bình 3 lít | 2 | 0 |
| 4 | Rót từ bình 5 sang bình 3 | 0 | 2 |
| 5 | Đổ đầy bình 5 lít | 5 | 2 |
| 6 | Rót từ bình 5 sang bình 3 cho đầy | 4 | 3 |
Sáu bước. Có thể kiểm tra bằng tìm theo chiều rộng (bài tìm đường ngắn nhất) rằng đây là một trong những lời giải ngắn nhất theo cách đếm này. Bài toán đong nước có từ thời trung cổ châu Âu và xuất hiện trong nhiều sách câu đố; ở Việt Nam, các bài "đong dầu", "chia rượu" kiểu này quen thuộc trong sách toán vui.
Giải ngược câu đố trượt trên băng
Trong câu đố trượt, đích là một ô cố định. Hỏi ngược:
- Bước cuối: vật phải trượt vào đích từ hướng nào? Chỉ những hướng mà ngay sau đích (theo hướng trượt) có vật chặn hoặc mép bàn. Thường chỉ một hoặc hai hướng.
- Điểm xuất phát của bước cuối: phải là một ô nằm trên đường thẳng dẫn vào đích theo hướng đó, và phải là một điểm dừng được (có vật chặn phía sau nó theo hướng nào đó). Đường thẳng vào đích không được bị chặn giữa chừng.
- Lặp lại: với mỗi ô xuất phát tìm được, hỏi tiếp "vật dừng ở ô này được từ đâu?".
Lan ngược như vậy theo từng lớp chính là tìm theo chiều rộng bắt đầu từ đích. Lớp đầu tiên chứa vị trí xuất phát cho biết số bước ít nhất. Với các màn có nhiều vật cùng trượt, việc đi ngược khó hơn vì một bước "nghiêng" có thể đến từ nhiều trạng thái trước, nhưng ý tưởng vẫn giữ nguyên.
Phân tích ngược trong cờ
Trong cờ vua, các nhà lập trình đã dùng phân tích ngược để xây dựng "bảng tra thế cờ tàn": bắt đầu từ mọi thế chiếu hết, lùi một nước xem thế nào dẫn tới chiếu hết, lùi tiếp... Kết quả là biết trước, với mọi thế cờ còn ít quân, bên nào thắng và cần bao nhiêu nước. Năm 2012, nhóm nghiên cứu ở Moskva hoàn thành bảng tra cho mọi thế cờ còn bảy quân (gồm cả hai vua), một khối dữ liệu khổng lồ. Bảng tra phát hiện những thế thắng cần hơn 500 nước, điều mà không kiện tướng nào tìm ra bằng suy nghĩ thông thường.
Đây là cùng một ý tưởng với giải ngược câu đố trượt, chỉ ở quy mô hàng nghìn tỷ trạng thái.
Giải ngược trong toán và đời sống
- Bài toán "nghĩ một số": "Một số nhân 3, cộng 5, chia 2 được 10. Số ban đầu là bao nhiêu?" Đi ngược: 10 × 2 = 20, 20 − 5 = 15, 15 : 3 = 5.
- Lập kế hoạch: muốn có mặt ở sân bay lúc 7 giờ, đi ngược: mất 45 phút đi đường, 15 phút chuẩn bị, vậy phải dậy lúc 6 giờ.
- Chứng minh toán học: nhiều lời giải bắt đầu bằng "giả sử điều cần chứng minh đã đúng, nó kéo theo điều gì?", rồi tìm đường về các giả thiết đã biết.
- Sinh màn câu đố: bắt đầu từ trạng thái đích, thực hiện nhiều bước ngược ngẫu nhiên để tạo ra màn đố. Màn đố như vậy chắc chắn có lời giải (bài tự đặt câu đố hay).
Khi nào không nên đi ngược
Đi ngược không phải lúc nào cũng tốt hơn:
- Khi có rất nhiều trạng thái đích khác nhau (ví dụ "đặt mọi thùng vào bất kỳ ô đích nào"), đi ngược phải bắt đầu từ nhiều điểm.
- Khi luật chơi không dễ đảo ngược: trong câu đố trượt nhiều vật, biết trạng thái sau một lần nghiêng, khó suy ra trạng thái trước.
- Giải pháp phổ biến: tìm hai chiều — lan từ xuất phát và từ đích cùng lúc, gặp nhau ở giữa. Mỗi bên chỉ cần lan khoảng một nửa số bước, tiết kiệm rất nhiều.
Góc nhìn hôm nay: luyện tư duy ngược
- Thử bài toán đong nước với bình 4 lít và 9 lít, đích là 6 lít, bằng cách nghĩ ngược.
- Vẽ một câu đố trượt nhỏ trên giấy, đánh dấu số 0 ở ô đích, số 1 ở mọi ô có thể trượt thẳng vào đích, số 2 ở mọi ô có thể trượt vào ô số 1... cho tới khi tới ô xuất phát.
- Với trẻ nhỏ: "Mẹ có 10 cái kẹo sau khi cho con 3 cái và được bà cho 5 cái. Lúc đầu mẹ có mấy cái?" — một bài giải ngược đơn giản.
Câu hỏi thường gặp
Giải ngược từ đích là gì?
Là cách suy luận bắt đầu từ trạng thái mục tiêu, hỏi bước ngay trước đó phải là gì, rồi lặp lại cho tới khi gặp trạng thái xuất phát. Cách này hiệu quả khi số trạng thái dẫn tới đích ít hơn nhiều so với số lựa chọn từ điểm xuất phát.
Làm sao đong 4 lít bằng bình 3 lít và 5 lít?
Đổ đầy bình 5 lít, rót sang bình 3 lít cho đầy còn 2 lít, đổ bỏ bình 3 lít, rót 2 lít sang bình 3, đổ đầy bình 5 lít, rồi rót sang bình 3 lít cho đầy. Bình 5 lít còn đúng 4 lít, tổng cộng 6 bước.
Giải ngược câu đố trượt trên băng thế nào?
Xác định vật phải trượt vào đích từ hướng nào có vật chặn phía sau đích, tìm các điểm dừng trên đường thẳng dẫn vào đích, rồi hỏi tiếp vật dừng ở các điểm đó được từ đâu. Lan ngược theo từng lớp sẽ ra số bước ít nhất.
Bảng tra thế cờ tàn là gì?
Là cơ sở dữ liệu tính trước kết quả cho mọi thế cờ còn ít quân, xây dựng bằng phân tích ngược từ các thế chiếu hết. Năm 2012 người ta hoàn thành bảng tra cho mọi thế cờ còn bảy quân, phát hiện cả những thế thắng cần hơn 500 nước.
Tìm kiếm hai chiều là gì?
Là cách lan đồng thời từ trạng thái xuất phát và từ trạng thái đích cho tới khi hai bên gặp nhau ở giữa. Mỗi bên chỉ cần lan khoảng một nửa số bước nên tiết kiệm rất nhiều thời gian và bộ nhớ so với chỉ đi một chiều.