Tài liệu Thuật toán frame – stewart giải bài toán tháp hà nội tổng quát

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC SƢ PHẠM NGUYỄN THỊ HỒNG PHƢỢNG THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC SƢ PHẠM NGUYỄN THỊ HỒNG PHƢỢNG THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Giải tích Mã số: 60 46 01 Người hướng dẫn khoa học: PGS. TS. TẠ DUY PHƢỢNG THÁI NGUYÊN - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỤC LỤC Trang MỤC LỤC LỜI NÓI ĐẦU ............................................................................................... 2 Chƣơng 1 ....................................................................................................... 4 TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI .......................................... 4 §1. Lịch sử trò chơi Tháp Hà Nội ............................................................ 4 §2. Sơ lược về bài toán tháp Hà Nội tổng quát, các bài toán cải biên và các vấn đề toán học liên quan ................................................................ 15 Chƣơng 2: TRÒ CHƠI THÁP HÀ NỘI..................................................... 21 §1 Trò chơi tháp Hà Nội và thuật giải đệ qui.......................................... 21 §2 Giải bài toán tháp Hà Nội bằng biểu diễn trong hệ đếm cơ số 2 ........ 26 §3 Đồ thị Hà Nội.................................................................................... 34 §4 Giải bài toán Tháp Hà Nội trên máy tính ........................................... 38 Chƣơng 3: BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơi Reve-The Reve’s Puzzle) ............................................................................. 39 §1 Trò chơi Tháp Hà Nội với bốn cọc.................................................... 39 §2 Tính số bước chuyển tối ưu trong trò chơi Tháp Hà Nội với bốn cọc...... 43 Chƣơng 4: BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT............................. 52 §1 Tính số S p (n) trong thuật toán Frame-Stewart cho trò chơi Tháp Hà Nội tổng quát ................................................................................... 52 §2 Đánh giá S p (n) ............................................................................... 68 §3 Sự tương đương của một số thuật toán giải bài toán Tháp Hà Nội tổng quát................................................................................................ 70 KẾT LUẬN .................................................................................................. 78 TÀI LIỆU THAM KHẢO........................................................................... 79 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 LỜI NÓI ĐẦU Trò chơi (Bài toán) Tháp Hà Nội được phổ biến rộng rãi ở Paris năm 1883 bởi nhà toán học Edouard Lucas, là một bài toán nổi tiếng thế giới, hiện nay đang được nghiên cứu bởi rất nhiều nhà toán học và khoa học máy tính, các chuyên gia giáo dục và y học, được đưa vào nhiều giáo trình tin học và sách về trò chơi toán học như một ví dụ điển hình về thuật toán đệ qui và lập trình căn bản, nhưng hình như chưa được chú ý nghiên cứu ở Việt Nam. Mặc dù trò chơi Tháp Hà Nội có mặt trên khá nhiều trang WEB và giáo trình tiếng Việt, số lượng bài viết tiếng Việt giới thiệu về trò chơi và bài toán Tháp Hà Nội trên các tạp chí là rất ít và còn rất sơ lược (xem [1]-[6]), hình như chưa có bài nghiên cứu tiếng Việt nào về bài toán Tháp Hà Nội, trong khi đó chỉ tính riêng số bài báo nghiên cứu về bài toán Tháp Hà Nội trong lĩnh vực Toán-Tin học đã có đến hơn 450 bài với khoảng 250 bài với đầu đề có cụm từ "The Tower of Hanoi", đăng trên hơn 100 tạp chí khoa học uy tín (trong [5] thống kê số lượng bài báo khoa học viết về Tháp Hà Nội là 464 bài). Đó là chưa kể đến những bài viết về sử dụng bài toán Tháp Hà Nội trong khoa học giáo dục và y học. Trò chơi Tháp Hà Nội thú vị đến mức nó đã được dùng làm đề tài của một số luận án Tiến sĩ và luận văn cao học. Một hội thảo khoa học quốc tế [21] với tên gọi Workshop on the Tower of Hanoi and Related Problems đã được tổ chức năm 2005. Bài toán Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của Việt nam, mà nó hấp dẫn các nhà Toán-Tin học bởi nó liên quan đến nhiều vấn đề như giải thuật đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski, lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính toán,.... Bài toán Tháp Hà Nội gợi ý cho nhiều nghiên cứu trong khoa học máy tính và toán học. Luận văn Thuật toán Frame-Stewart giải bài toán Tháp Hà Nội tổng quát có mục đích trình bày tổng quan về một thuật toán quan trọng giải bài toán Tháp Hà Nội với số cọc bất kì. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Luận văn gồm phần mở đầu, bốn Chương và phần tài liệu tham khảo. Chương 1. Tổng quan về trò chơi Tháp Hà Nội. Chương 2. Bài toán Tháp Hà Nội cổ điển. Chương 3. Bài toán Tháp Hà Nội với bốn cọc. Chương 4. Bài toán Tháp Hà Nội tổng quát. Chương 1 giới thiệu tổng quan về Trò chơi Tháp Hà Nội. Lời giải Bài toán Tháp Hà Nội cho ba cọc được trình bày trong Chương 2. Sau hơn 100 năm, trò chơi Tháp Hà Nội đã có những cải biên và tổng quát hoá (trò chơi Tháp Hà Nội xoay vòng, trò chơi Tháp Hà Nội song song, trò chơi Tháp Hà Nội với nhiều cọc,...). Những cải biên và tổng quát hóa này dẫn đến những vấn đề toán học thú vị, thậm chí dẫn tới nhiều bài toán hiện nay chưa có lời giải. Trong luận văn này, chúng tôi tập trung trình bày trong Chương 3 và Chương 4 lời giải của bài toán Tháp Hà Nội, đó là Thuật toán đệ qui dạng Frame-Stewart giải bài toán Tháp Hà Nội tổng quát. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS Tạ Duy Phượng. Em xin bầy tỏ lòng biết ơn sâu sắc nhất đối với Thầy và xin được cảm ơn Thầy đã cung cấp nhiều tài liệu đồng thời cho phép sử dụng Bản thảo cuốn sách của Thầy về Tháp Hà Nội. Em xin cảm ơn các Thầy Cô của Đại học Thái Nguyên và Viện Toán học đã tận tình giảng dạy em trong suốt quá trình học cao học. Tôi xin cảm ơn khoa Toán trường ĐHSP Thái Nguyên, khoa Sau Đại học trường ĐHSP Thái Nguyên đã quan tâm giúp đỡ, tạo điều kiện thuận lợi cho tôi thực hiện kế hoạch học tập của mình. Xin cảm ơn người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tôi trong suốt quá trình làm luận văn. Thái Nguyên, 19.8.2010 Nguyễn Thị Hồng Phượng Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chƣơng 1 TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI §1. Lịch sử trò chơi Tháp Hà Nội Bìa cuốn sách của E. Lucas xuất bản tại Paris năm 1895, trong đó có 4 trang (179-183) viết về trò chơi Tháp Hà Nội. 1.1 Truyền thuyết Theo một truyền thuyết, liên tục suốt ngày đêm, các nhà tu hành của tòa tháp Brahma trong thành Bernares (Ấn Độ) phải chuyển 64 đĩa vàng từ một cọc này sang cọc khác của tòa tháp. Các đĩa có kích thước khác nhau và lúc Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 đầu được đặt trên một trong ba cọc của tòa tháp theo thứ tự đĩa nhỏ ở trên, đĩa lớn ở dưới. Đĩa trên cùng được chuyển sang cọc khác, mỗi lần chỉ di chuyển một đĩa. Do tính dễ vỡ, đĩa lớn không được đặt lên trên đĩa nhỏ. Trong quá trình di chuyển, có thể đặt đĩa lên một cọc trung gian. Khi công việc hoàn thành, tòa tháp sẽ đổ, và lúc đó cũng là thời điểm kết thúc của vũ trụ với một tiếng nổ khủng khiếp! 1.2 Lịch sử Dựa trên truyền thuyết về tháp Brahma, và có thể, theo truyền thuyết về sự tồn tại những ngôi tháp cổ đồng dạng với tháp Brahma trong vùng đất phật giáo linh thiêng gần Hà Nội (Bắc Ninh?, Vĩnh Phúc?), Việt Nam, nhà toán học người Pháp Edouard Lucas (quê ở Amiens) đã phổ biến Trò chơi Tháp Hà Nội ở Paris năm 1883 với tên giả là giáo sư N. Claus. Năm 1884, Parvile trong [14] đã trình bày lời giải bài toán Tháp Hà Nội và tiết lộ giáo sư N. Claus chính là tên giả của nhà nghiên cứu lí thuyết số nổi tiếng Eduard Lucas. Trên bìa của hộp đựng trò chơi sản xuất năm 1883 và trong cuốn sách L’Arithméique Amusante, xuất bản tại Paris năm 1895 (sau khi Ông mất), chính Edouard Lucas đã viết ([12], trang 179): “…la Tour d’Hanoi, véritable cassetête annamite…” (Tháp Hà Nội, một trò chơi trí tuệ của người Annam), nhưng tại sao ông lại gọi trò chơi này là trò chơi Tháp Hà Nội thì chưa có câu trả lời thật rõ ràng. Rất có thể (theo Edouard Lucas), trò chơi Tháp Hà Nội “đã xuất hiện ở Đông Á từ thế kỷ 19 hoặc trước đó. Các đĩa được làm bằng sứ ở Trung Quốc, Nhật Bản và Đông Kinh (Bắc Kì, Việt Nam)”. Tuy nhiên, cho tới nay, các nhà lịch sử có lẽ vẫn chưa tìm thấy các đĩa sứ của trò chơi tháp Hà Nội tại châu Á. Những hộp đựng trò chơi cũ nhất vẫn là hộp đựng các đĩa sản xuất tại Pháp năm 1883. Theo David G. Pool [15], trích dẫn theo P. J. Hilton [10], sự tồn tại những ngôi tháp gần Hà Nội (Việt Nam) là lí do để E. Lucas đã đặt tên cho trò chơi của mình là Trò chơi Tháp Hà Nội. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Có một giả định rằng: “nhà toán học đến thăm Việt Nam, ngắm cảnh Hồ Gươm và bị quyến rũ bởi vẻ đẹp của Tháp Rùa nên đã đặt tên là Bài toán Tháp Hà Nội”. Nếu có tư liệu khẳng định nhà toán học nổi tiếng E. Lucas đã đến Hà Nội từ trước năm 1883 (Pháp chiếm Hà Nội năm 1882) thì thật là thú vị. Tuy nhiên, lúc đó E. Lucas đã ra khỏi quân đội và đang dạy học, vì vậy ít có khả năng ông đã đến Hà Nội. Cũng có lẽ Cột cờ Hà Nội đã gợi ý cho E. Lucas đặt tên trò chơi của mình là Tháp Hà Nội: “The Flag Tower of Hanoi may have served as the inspiration for the name”. Cột cờ Hà Nội có đáy gồm ba khối vuông xây chồng lên nhau. Trò chơi Tháp Hà Nội đơn giản nhất cũng gồm ba đĩa tròn xếp chồng lên nhau. Cột cờ Hà Nội xây năm 1805-1812, Tháp Rùa xây năm 1886, trò chơi Tháp Hà Nội xuất hiện ở Paris 1883. Có thể Pháp chiếm Hà Nội là đề tài thời sự ở Paris vào những năm 1882-1883, và điều này gợi ý E. Lucas đặt tên cho trò chơi của mình là Tháp Hà Nội? Trò chơi Tháp Hà Nội vừa được phổ biến đã được đón nhận rộng rãi vì sự đơn giản và hấp dẫn của nó. Mặc dù chưa có câu trả lời rõ ràng về lí do E. Lucas đặt tên cho trò chơi của mình là trò chơi Tháp Hà Nội, người Việt Nam vẫn có thể tự hào và cần quan tâm về trò chơi này. Dưới đây là bìa của hộp đựng trò chơi Tháp Hà Nội sản xuất lần đầu tiên tại Paris năm 1883 và hai tờ hướng dẫn qui tắc chơi. Đây là những tư liệu quí về lịch sử trò chơi. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Bìa của hộp đựng trò chơi Tháp Hà Nội đƣợc bán lần đầu tại Paris năm 1883. Trên tờ bìa này có một hình tháp 10 tầng, cây tre, người Annam (Việt Nam) và ghi rõ: La Tour d’Hanoϊ, Veritable casse-téte Annamite Jeu, rapporté du Tonkin par le professeur N. Claus (de Siam) du college Mandarin Li-SouSian (Tháp Hà Nội, Trò chơi trí tuệ của người Annam, được giới thiệu bởi giáo sư N. Claus (ở Siam), trường trung học Li-Sou-Sian). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Bản dịch tờ hướng dẫn thứ nhất giới thiệu trò chơi Tháp Hà Nội được sản xuất lần đầu tiên tại Paris: THÁP HÀ NỘI Trò chơi trí tuệ của người Annam Trò chơi được đem về từ Đông Kinh bởi Giáo sư N. CLAUS (DE SIAM) Trường Cao đẳng Li-Sou-Stian! Trò chơi này được tìm thấy, lần đầu, trong cuốn sách được minh họa Quan thoại FER-FER-TAM-TAM, đang được xuất bản, trong tương lai gần, bởi chính phủ Trung Hoa. Tháp Hà Nội có các đĩa, nhỏ dần, có số lượng thay đổi, mà chúng tôi làm bằng gỗ, có lỗ ở giữa. Ở Nhật Bản, Trung Quốc, và ở Đông Kinh, chúng được làm bằng sứ. Trò chơi có mục đích là dỡ bỏ từng đĩa, và đặt vào cột bên cạnh, theo các quy tắc nhất định. Vui và bổ ích, dễ học và dễ chơi trong thành phố, ngoài nông thôn, trên chuyến du lịch, nó được tạo ra để mang đến kiến thức khoa học, giống mọi trò chơi kỳ thú và mới lạ của giáo sư N. CLAUS (của SIAM). Chúng tôi trao giải thưởng 1000 franc, 100 nghìn franc, một triệu franc, và nhiều hơn, cho ai hoàn thành, bằng việc dùng tay di chuyển tháp Hà Nội với 64 đĩa, theo quy tắc của trò chơi. Chúng tôi nói ngay là cần số lần di chuyển là: 18 446 744 073 709 551 615, nhiều hơn năm tỷ thế kỷ! Theo một truyền thuyết Ấn Độ, những người Brahmin đã tiếp nối nhau trong một thời gian dài để thay đổi Đền Bernares, di chuyển 64 đĩa vàng của Tòa tháp Brahma. Khi công việc hoàn thành, Tòa tháp và Brahmin sẽ đổ, và lúc đó là thời điểm kết thúc của vũ trụ! PARIS, BẮC KINH, TOKYO và SÀI GÒN Trong các hiệu sách và tiểu thuyết 1883 Bản quyền đã giữ. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Bản dịch tờ hướng dẫn trò chơi Tháp Hà Nội được sản xuất lần đầu tại Paris: Luật chơi và cách chơi trò chơi THÁP HÀ NỘI Đế đặt nằm ngang; các cọc thẳng đứng. Các đĩa đặt theo thứ tự từ lớn đến nhỏ từ thấp lên cao, tạo nên một Tòa tháp. Trò chơi đòi hỏi di chuyển các đĩa, bằng cách đặt chúng vào cọc bên cạnh, mỗi lần chuyển một đĩa, theo luật sau: I. Sau mỗi lần chuyển, các đĩa đều nằm trên một, hai, hoặc ba cọc, theo thứ tự từ lớn đến nhỏ từ thấp đến cao. II. Đĩa trên cùng của một trong ba cọc được đặt vào cọc trống. III. Đĩa trên cùng của một trong ba cọc đĩa được đặt lên một trong hai cọc khác, nếu đĩa này nhỏ hơn các đĩa của cọc đó. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Trò chơi có thể dễ dàng tự khám phá, bằng việc giải quyết dần từ 3, 4, và 5 đĩa. Trò chơi luôn giải được và đòi hỏi thời gian chơi lâu khoảng gấp đôi mỗi khi cho thêm một đĩa vào Tòa tháp. Bất kì ai giải được cho tám đĩa, ví dụ, chuyển các đĩa từ cọc 1 sang cọc 2, cũng sẽ biết cách giải cho chín đĩa. Chỉ cần chuyển tám đĩa sang cọc 3, rồi chuyển đĩa thứ chín sang cọc 2, và mang tám đĩa từ cọc 3 về cọc 2. Bây giờ, khi thêm một đĩa vào trò chơi, tổng số di chuyển tăng gấp đôi, cộng với một, so với trước. Với tháp hai đĩa ba lần chuyển là đủ Số đĩa Số lần chuyển Ba đĩa 7 lần 6 đĩa 63 lần Bốn đĩa 15 lần 7 đĩa 127 lần Năm đĩa 31 lần 8 đĩa 255 lần Với tốc độ một di chuyển mất một giây, cần bốn phút để chuyển tám đĩa. Các biến thể của trò chơi: Có thể thay đổi đến vô cùng điều kiện của bài toán tháp Hà Nội như sau. Khi bắt đầu, xếp các đĩa theo thứ tự bất kỳ lên một, hai, hay cả ba cọc. Sau đó cần xây dựng lại tòa tháp trên một cọc định trước. Với 64 đĩa, số lần di chuyển là khổng lồ, số này dài 50 chữ số. Xem thêm chi tiết trong chương nói về Baguenaudier (trò chơi tháo vòng) ở: TOÁN HỌC GIẢI TRÍ bởi Mr. Édouard Lucas giáo sư toán học cao cấp tại Lycée Saint-Louis Hai tập nhỏ, trong hai màu Paris, 1883, bởi GAUTHER-VILLARS, máy in của Académie des Sciences và Ecole Polytechnique Trên mạng Internet có rất nhiều chương trình hiển thị minh họa và hướng dẫn trò chơi Tháp Hà Nội (với ba cọc). Ngoài ra, có thể tìm mua trò chơi Tháp Hà Nội làm bằng gỗ hoặc sứ tại các cửa hàng Việt Nam hoặc nước ngoài để giải trí. Dưới đây chúng tôi chụp lại bốn trang (179-183) viết về Tháp Hà Nội trong cuốn sách Số học vui của E.Lucas xuất bản năm 1895 (sau khi Ông mất) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 §2. Sơ lƣợc về bài toán tháp Hà Nội tổng quát, các bài toán cải biên và các vấn đề toán học liên quan Trò chơi Tháp Hà Nội ngày càng được các nhà toán học quan tâm, Với sự phát triển của tin học, bài toán tháp Hà Nội lại càng thu hút sự chú ý của các nhà toán-tin học. Nó trở thành ví dụ điển hình về phương pháp giải đệ qui và lập trình căn bản. 2.1 Bài toán Tháp Hà Nội tổng quát Bài toán Tháp Hà Nội với ba cọc và n đĩa có thể giải được dễ dàng theo thuật giải đệ qui (xem Chương 2). Hơn nữa, có thể biết chính xác số lần cần chuyển tối ưu cho bài toán với n đĩa là 2n  1 lần. Vì vậy nó thường được dùng làm thí dụ kinh điển về lập trình căn bản và thuật giải đệ qui cũng như minh họa về độ phức tạp tính toán (thời gian mũ) của bài toán với thuật giải đơn giản và tối ưu. Một mở rộng tự nhiên của bài toán Tháp Hà Nội với ba cọc là Bài toán Tháp Hà Nội với bốn (hoặc nhiều) cọc. Theo một số tài liệu, chính tác giả của bài toán Tháp Hà Nội, E. Lucas cũng là người đầu tiên xét bài toán với nhiều cọc vào năm 1899. Năm 19021903 Henry Ernest Dudeney đã viết về bài toán Tháp Hà Nội với bốn cọc trong hai bài báo. Trong hai trang đầu tiên của cuốn sách nổi tiếng của Ông The Canterbury Puzzles (xem [7]) ông đã viết về bài toán này (và gọi là Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Reve's puzzle) với số cọc là 4 và số đĩa là 8, 10 hoặc 21, chỉ có khác là Ông đã thay các đĩa bằng các quân cờ. Trong phần lời giải (trang 131-132), Dudeney đã khẳng định (không chứng minh) rằng số lần chuyển cần thiết tương ứng với 8, 10 hoặc 21 đĩa là 33, 49 hoặc 321. Hơn nữa, Ông còn xét trường hợp với số đĩa là số tam giác, tức là các số tk  tk  cần k (k  1) , k  1,2,... Giả sử 2 k (k  1) là số tam giác thứ k và giả sử M (n) là số lần chuyển tối thiểu 2 thiết để chuyển xong M 4  tk   2M 4  tk 1   2k  1 , n M 4 1  1 . đĩa. Từ Dudeney đây ta tuyên có bố rằng M 4  3  5 ; M 4  6  17 , M 4 10  49 ,… Tuy nhiên Dudeney không cho một thuật toán nào cho phép tìm ra các số này, và cũng không có một gợi ý nào cho trường hợp số đĩa không phải là số tam giác, thí dụ khi n  8 . Bài toán tổng quát với p  3 cọc, p là số bất kì với số đĩa n bất kì được B. M. Stewart đề xuất năm 1939 (Problem 3918 trong tạp chí The Americal Mathematical Montly [17]). Lời giải của bài toán này đã được Stewart [19] và Frame [9] trình bày cũng trong tạp chí này năm 1941. Các thuật toán của Stewart và Frame cùng với một số thuật toán cải biên khác đã được chứng minh là tương đương theo nghĩa số lần chuyển đĩa là bằng nhau (xem [11]). Vì vậy người ta thường gọi thuật toán của hai ông hoặc các thuật toán cải biên tương tự là thuật toán Frame- Stewart. Thuật toán Frame-Stewart cùng các thuật toán tương đương sẽ được trình bày trong Chương 3 và Chương 4. Thuật toán Stewart (1941) Thuật toán truy hồi do Stewart đề xuất 1941, được coi là presumablyoptimal solution (lời giải giả định là tối ưu) cho bài toán bốn cọc (hoặc nhiều hơn). Giả sử n là số đĩa và p là số cọc. Để giải bài toán tháp Hà Nội với p cọc, ta thực hiện các bước sau. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 Bước 1. Với số l , 1  l  n , chuyển l đĩa trên cùng tới cọc 1, mất S p (l ) lần chuyển. Sử dụng tất cả các cọc trong khi chuyển. Bước 2. Giữ nguyên cọc 1 chứa l đĩa trên cùng. Chuyển n  l đĩa tới cọc đích, sử dụng p  1 cọc còn lại (vì cọc 1 đang được dùng để chứa l đĩa nhỏ nhất), mất S p1 (n  l ) lần chuyển. Bước 3. Cuối cùng, chuyển l đĩa trên cùng từ cọc 1 tới cọc đích, mất S p (l ) lần chuyển nữa. Được phép sử dụng tất cả các cọc. Như vậy, tổng cộng cần 2S p (l )  S p1 (n  l ) lần chuyển. Bài toán đặt ra là, cần tính số l để tổng này là nhỏ nhất. Thuật toán Stewart nói trên (với cách chọn l như trên) cho phép tìm ra một (một vài) giá trị i sao cho 2S p (i)  S p 1 (n  i)  min 2S p (l )  S p 1 (n  l ) . 1l  n (1.1) Nói cách khác, các giá trị i thỏa mãn (1.1) là số bước chuyển tối ưu trong lớp các thuật toán đề nghị. Stewart và Frame cũng đã chứng minh rằng, nếu n là số tam giác n  tk , thì cách chọn tối ưu nhất cho l là l  k , trong khi đó nếu tk 1  n  tk thì cả hai giá trị k  1 và k đều là cách chọn tối ưu cho l . Như vậy, Stewart và Frame đã đề xuất thuật toán hiển cho bài toán Tháp Hà Nội với bốn cọc. Thuật toán này trùng với lời giải của Dudeney trong các trường hợp riêng nêu trên. Từ đây ta cũng có nhận xét rằng, khác với trường hợp bài toán với ba cọc, lời giải cho bài toán với bốn cọc có thể là không duy nhất. Otto Dunkel, tổng biên tập của tạp chí The Americal Mathematical Montly khi cho đăng hai lời giải trên đã chỉ ra rằng chứng minh tính tối ưu của Frame và Stewart chỉ áp dụng được cho các thuật toán của một lược đồ chung mô tả bởi Frame và Stewart mà thôi. Nói cách khác, Frame và Stewart mới chỉ chứng minh rằng trong số tất cả các giá trị có thể của l theo thuật Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 18 toán của hai ông phải có ít nhất một giá trị i làm cực tiểu số lần chuyển. Tuy nhiên hai ông chưa chứng minh rằng thuật toán tối ưu bắt buộc phải có dạng trên. Và điều này cho tới nay vẫn chưa chứng minh được. Và lời giải của Frame và Stewart cần phải coi một cách đúng đắn là “lời giải giả định là tối ưu” (presumed optimal solution), chứ chưa chứng minh được là lời giải tối ưu. Từ 1941 đến nay, rất nhiều người khác đã nghiên cứu thuật toán này (xem trích dẫn đầy đủ trong [5]). Gần đây một số tác giả đề nghị một số thuật toán hồi qui tương đương với thuật toán Frame và Stewart (xem [11]). Nhưng tính tối ưu của thuật toán vẫn chưa được chứng minh. Đây là một ví dụ tiêu biểu cho thấy từ một bài toán đơn giản, có thể giải được, nhưng bằng cách nới lỏng một số ràng buộc của nó thì lại trở thành khó hơn rất nhiều do xuất hiện những bài toán mới. Việc chưa chứng minh được lời giải cho bài toán với bốn hoặc nhiều cọc là tối ưu không suy ra rằng không tồn tại thuật toán tìm (tất cả) các nghiệm tối ưu. Mặc dù chưa chứng minh được số lần chuyển đĩa tối ưu chính xác là bao nhiêu, nhưng thuật toán Frame-Stewart và các cải biên của nó cũng đã cho "lời giải được giả định là tối ưu" (presumed-optimal solution). Giả thuyết Frame-Stewart (chưa được chứng minh) nói rằng thuật toán Frame-Stewart luôn cho lời giải tối ưu. Tính tối ưu của thuật toán FrameStewart đã được kiểm tra trên máy tính cho số đĩa nhỏ hơn 30. Theo Donald Knuth, nhà tin học nổi tiếng thế giới đã gọi giả thuyết này là “giả thuyết Frame” và Ông đã viết: “Tôi nghi ngờ rằng ai đó đã giải được giả thuyết này. Nó thật sự khó”. 2.2. Bài toán Tháp Hà Nội cải biên Bài toán Tháp Hà Nội có khá nhiều cải biên rất thú vị. Mỗi qui tắc chơi mới lại làm trò chơi Tháp Hà Nội thêm phong phú và lại xuất hiện thêm nhiều vấn đề toán học mới. Dứới đây chúng tôi sơ lược liệt kê một số cải biên của trò chơi Tháp Hà Nội. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn