Bài toán tháp Hà Nội

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.

Chủ đề : Thuật Toán, Vui - Giải Trí and tagged . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

8 Comments

  1. npson
    Posted 14/06/2007 at 12:52 pm | Permalink

    No la Hanoi tower chu khong phai thap Ha Noi dau. Cai thap nay hinh nhu o ben An Do, khong phai o Ha Noi dau

  2. Posted 14/06/2007 at 1:17 pm | Permalink

    Tôi thì tin rằng chữ Hanoi trong “Tower of Hanoi” đúng là Hà Nội, Việt Nam. Tuy nhiên, npson nói đúng là Lucas lấy cảm hứng từ một truyền thuyết về Tower of Brahma ở Ấn Độ, cho nên bài toán này cũng được gọi là bài “Tower of Brahma”.

    Tôi không rõ lắm là tên nào có trước. Brahma hay Hà Nội dùng để chỉ một nơi xa xôi bí hiểm.

  3. Posted 26/02/2008 at 5:16 am | Permalink

    ha noi tower chinh xac la thap ha noi cua viet nam,day la bai toan kho va la games tri tue rat hay,no xuat hien tu truoc the ki 19,nguoi viet nam ta da sang tao ra tro nay,cac ban hay tim hiu ki thong tin nhe

  4. dinhhungonline
    Posted 16/06/2008 at 9:05 pm | Permalink

    Tôi nghĩ là tại hình giáng của tháp hà nội cũng tương tự như hình những chiếc đĩa to nhỏ chồng lên nhau trong trò chơi này lên mới lấy tên là trò chơi Tower of hanoi còn về nguồn gốc thì đúng là lấy cảm hứng từ truyền thuyết về Tower of Brahma

  5. Thái
    Posted 24/02/2009 at 6:49 pm | Permalink

    Các anh ơi cho em hỏi liệu bài toán “Tháp Hà Nội-Tower of Hanoi” thức sự là do người Việt Nam sáng tạo ra không vậy?Hi

  6. Posted 25/02/2009 at 7:32 am | Permalink

    @Thái:

    Xem câu trả lời ở đây

  7. thai quyen
    Posted 23/02/2012 at 9:11 am | Permalink

    cho e hoi bai toan nay that ra la o thoi vua nao vay?

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>