Theo tôi đây có lẽ là bài toán gắn với một từ tiếng Việt đựợc biết nhiều nhất. Bài toán này như sau: Cho ba cái cọc với 2 cọc trống và 1 cọc cón đĩa với cỡ khác nhau được xếp từ thấp lên cao, chuyển hết đĩa qua một cọc trống với điều kiện không bao giờ được xếp một đĩa lên một đĩa khác nhỏ hơn. Một tên khác ít được gọi hơn là Tháp Brahma (do đó tôi vẫn chưa hiểu tại sao từ Hanoi lại được dùng với bài toán này).
Mặc dù bài toán này được giới thiệu bởi nhà toán học Edouard Lucas vào năm 1883 và thuật toán tìm ra cách giải tối ưu được tìm ra rất sớm, tháp Hà Nội vẫn được dùng thường xuyên trong các quyển sách toán và tin học như một ví dụ điển hình. Ngoài ra, vẫn có nhiều nhà toán học tìm cách giải các vấn đề liên quan tới bài tóan này, và tháng 9 năm nay sẽ có môt hội nghị đầu tiên về tháp Hanoi và các vấn đề liên quan. Một số điểm thú vị về bài toán tháp Hanoi:
1. Đây là một ví dụ rất tốt trong việc giới thiệu thuật tóan đệ quy (recursive algorithm) vì thuật toán đệ quy giải bài này tương đối đơn giản (và đã được chứng minh là cho lời giải tối ưu). Nó cũng là một ví dụ tốt cho các thuật toán có thời gian mũ (exponential time algorithm) vì mặc dù thuật toán để giải bài này đơn giản, lời giải cho n đĩa sẽ cần tới 2^n lần chuyển đĩa. Do vậy, dù với số lượng đĩa không lớn, máy tính sẽ cần một lượng thời gian rất lớn để có thể cho câu trả lời cuối cùng. Không có cách gì để làm tốt hơn, kể cả có nhiều processors để chạy song song cùng giải bài toán này.
2. Mặc dù đã chứng minh được số lượng chuyển tối thiểu cho ba cột, những biến thể của bài toán này với số cột bằng 4 hoặc hơn lại chưa chứng minh được. Mặc dù chưa chứng minh được, thuật toán được cho rằng sẽ đưa ra số lượng chuyển nhỏ nhất cho 4 cột đã được kiểm tra bằng máy tính đến 21 đĩa dùng những thuật toán tìm kiếm (search) mới nhất. Con số 21 mới nhìn thật nhỏ, điều đó càng cho thấy sự khối lượng tính toán khổng lồ liên quan tới bài toán này.
Trên web có vô khối trang webs dành cho bài toán này, tôi thấy mấy trang sau có vẻ hay Wikipedia, Mathworld, Hanoimania, và đây.
Không có nhận xét nào:
Đăng nhận xét