Tài liệu Một số công thức truy hồi trong bài toán tháp hà nội tổng quát

-1- ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------- VŨ THU TRANG MỘT SỐ CÔNG THỨC TRUY HỒI TRONG 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 – 2015 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- MỤC LỤC Trang Mục lục……………………………………………………………..……... 1 Lời nói đầu………………………………………………………..….…… 2 Chƣơng 1 BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT………………… 4 1.1 Lịch sử bài toán Tháp Hà Nội ………………………………………… 4 1.1.1 Truyền thuyết....................................................................................... 4 1.1.2 Lịch sử.................................................................................................. 4 1.2 Bài toán Tháp Hà Nội tổng quát.............................................................. 7 1.2.1 Bài toán Tháp Hà Nội cổ điển.............................................................. 7 1.2.2 Bài toán Tháp Hà Nội tổng quát........................................................... 9 Chƣơng 2 MỘT SỐ CÔNG THỨC TRUY HỒI TRONG BÀI TOÁN THÁP HÀ NỘI DỰA TRÊN PHÁT BIỂU QUI HOẠCH ĐỘNG…….. 17 2.1 Công thức qui hoạch động trong bài toán Tháp Hà Nội ……………… 17 2. T 4 cọc …..…......… 30 2.3 Công thức truy hồi trong T ............. 39 Kết luận…………………………………..............................................….. 54 Tài liệu tham khảo………………………….......................................…… 55 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- LỜI NÓI ĐẦU Tháp Hà Nội là một từ tiếng Việt đựợc biết đến nhiều trên thế giới, bởi vì nó gắn liền với Trò chơi (hoặc Bài toán) Tháp Hà Nội. Bài toán này được giới thiệu và phổ biến rộng rãi ở Paris từ năm 1883 bởi nhà toán học Edouard Lucas. Mặc dù trong khoảng 10 năm (từ năm 1883 đến 1891), trong các báo và sách, E. Lucas đã chỉ ra sự thú vị và quan trọng của bài toán này cũng như mối quan hệ của nó với các lĩnh vực khác (Dãy truy hồi, lí thuyết đồ thị, hệ đếm cơ số 2, trò chơi tháo vòng Trung Hoa,…), bài toán Tháp Hà Nội vẫn thường được coi là một trò chơi toán học nhiều hơn là một bài toán có nội dung toán học. Với sự bùng nổ của công nghệ thông tin, bài toán Tháp Hà Nội được quan tâm trở lại như là một bài toán thú vị của Toán-Tin học vào những năm 1970. Bài toán Tháp Hà Nội được đưa vào hầu hết các giáo trình tin học như một ví dụ điển hình về thuật giải đệ qui, lập trình căn bản và độ phức tạp tính toán. Trò chơi Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của Việt Nam. Bài toán Tháp Hà Nội hấp dẫn các nhà nghiên cứu Toán học và Tin học bởi nó liên quan đến nhiều vấn đề của Toán-Tin học như giải thuật đệ qui, hệ đếm và mã Gray, tam giác Pascal, thảm Sierpinski và Fractal, dãy Stern, 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 mới trong nhiều lĩnh vực khác nhau. Hiện nay bài toán này đang được nghiên cứu và phát triển 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. Một trong những bài toán tổng quát trực tiếp và quan trọng nhất của bài toán Tháp Hà Nội là bài toán Tháp Hà Nội với nhiều cọc. Để nghiên cứu bài toán này, các nhà toán học đã đưa ra các thuật toán, chứng minh các công thức truy hồi và áp dụ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- nhiều phương pháp, trong đó có công thức qui hoạch động, để chứng minh hoặc đánh giá thuật toán tối ưu. Luận văn Một số công thức truy hồi trong 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ề bài toán Tháp Hà Nội với nhiều cọc (bài toán Tháp Hà Nội tổng quát). Luận văn cũng trình bày chứng minh một số công thức truy hồi tính số lần chuyển tối ưu trong trò chơi Tháp Hà Nội tổng quát. Đặc biệt, luận văn quan tâm tới công thức qui hoạch động giải bài toán Tháp Hà Nội. Luận văn gồm Phần mở đầu, hai Chương và Tài liệu tham khảo. Chƣơng 1 Bài toán Tháp Hà Nội tổng quát Chương 1 giới thiệu tổng quan về bài toán tháp Tháp Hà Nội tổng quát. Chƣơng 2 Một số công thức truy hồi trong trò chơi Tháp Hà Nội tổng quát Chương 2 trình bày cách tính số lần chuyển tối ưu thông qua việc chứng minh một số công thức truy hồi. 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, Viện Toán học. Em xin được bày tỏ lòng biết ơn chân thành và sâu sắc nhất đối với Thầy. 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-Tin, trường Đại học Khoa học-Đại học Thái Nguyên, trường Trung học phổ thông Hòn Gai đã 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 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 học cao học và làm luận văn. Thái Nguyên, 10.4.2015 Vũ Thu Trang 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- CHƢƠNG 1 BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT 1.1 Lịch sử bài toán tháp Hà Nội 1.1.1 Truyền thuyết Éduard Lucas, tác giả của trò chơi Tháp Hà Nội, đã viết như sau: Dưới vòm của tòa tháp thờ thần Brahma (thần sáng tạo) trong thành Bernares (Ấn độ), tại vị trí được coi là trung tâm thế giới, khi bắt đầu sáng tạo vũ trụ, thần Brahma đã đặt 64 chiếc đĩa bằng vàng ròng có khoét lỗ ở giữa trên một trong ba chiếc cọc kim cương. Các đĩa này có đường kính nhỏ dần từ dưới lên trên và tạo thành một hình nón. Các nhà tu hành trong tòa tháp liên tục suốt ngày đêm, không mệt mỏi, chuyển 64 đĩa từ cọc đầu tiên sang cọc thứ ba của tòa tháp. Khi di chuyển các đĩa phải tuân theo hai qui tắc: 1) Mỗi lần chỉ được chuyển một đĩa trên cùng của một cọc nào đó. 2) Đĩa trên cùng được chuyển từ một cọc sang một trong hai cọc khác. Đĩa lớn không được đặt lên trên đĩa nhỏ vì nó có tính dễ vỡ. Công việc hoàn thành thì 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! Không rõ truyền thuyết này đúng tới đâu nhưng Lucas đã chỉ ra, các nhà tu hành cần 18.446.744.073.709.551.615 lần di chuyển mới có thể hoàn thành công việc. Nếu họ làm cả ngày lẫn đêm, mỗi lần chuyển đĩa mất 1 giây thì phải mất tới 580 tỷ năm mới có thể hoàn thành công việc này! 1.1.2 Lịch sử Trò chơi Tháp Hà Nội được Éduard Lucas (1842-1891) phổ biến ở Paris năm 1883 dưới ẩn danh (under the nickname) là giáo sư N. Claus. Trò chơi này đã được 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/ -6- nhà toán-tin học quan tâm nghiên cứu, và trở thành ví dụ về thuật giải giải đệ quy kinh điển trong dạy học và trong tin học (solving problem, lập trình cơ bản, giải thuật đệ qui, độ phức tạp tính toán,..). Ngoài ra bài toán Tháp Hà Nội còn được ứng dụng cả trong nghiên cứu tâm lý và phương pháp giảng dạy về cách giải quyết vấn đề (problem solving). Tháp Luân Đôn là một biến thể khác, dùng trong chẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành. Có lẽ đây là điều mà ngay chính tác giả cũng khó có thể hình dung ra mức phổ biến đến vậy của trò chơi, cả trong nghiên cứu thực tiễn lẫn trong giải trí. 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 (Số học vui), xuất bản tại Paris năm 1895 (sau khi Ông mất), chính Édouard Lucas đã viết ([21], trang 179): “…la Tour d’Hanoi, véritable casse-tê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 và tại sao lại là trò chơi trí tuệ của người Annam thì chưa có câu trả lời thật rõ rà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/ -7- Một giả thuyết nữa là Cột cờ Hà Nội đã gợi ý cho E. Lucas đặt tên trò chơi của mình là trò chơi 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. Cột cờ Hà Nội xây năm 1805-1812, hơn 70 năm trước khi trò chơi tháp Hà Nội được phổ biến. Cột cờ Hà Nội thế kỉ 19 Năm 1882 Pháp tấn công đánh chiếm thành Hà Nội lần thứ hai. Đề tài Hà Nội và Đông Dương là thời sự và tràn ngập trên các báo ở Paris vào những năm 18821883 (xem [12], trang 6). Phải chăng điều này đã gợi ý E. Lucas đặt tên cho trò chơi của mình là trò chơi Tháp Hà Nội? Trên tờ 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 có hình tháp 10 tầng, cây tre, người Annam và dòng chữ: La Tour d’Hanoϊ, Veritable casse-téte Annamite Jeu, rapporté du Tonkin par le professeur N. Claus (de Siam) du college Mandarin Li-Sou-Stian - Tháp Hà Nội, Trò chơi trí tuệ của người Annam, được mang về từ Bắc Kì bởi giáo sư N. Claus (ở Siam), trường trung học Li-Sou-Stian. (N. Claus de Siam là đảo từ của E. Lucas d’Amiens, Amiens là quê của E. Lucas. Li-Sou-Sian là đảo từ của Sant Louis, trường trung học ở Paris, nơi Ông dạy học vào những năm đó). Phần dịch nghĩa của tờ hướng dẫn thứ nhất giới thiệu trò chơi Tháp Hà Nội được tóm tắt như sau: Trò chơi này lần đầu được tìm thấy trong cuốn sách có minh họa tiếng Quan thoại FER-FER-TAM-TAM, sẽ được xuất bản trong tương lai gần, bởi chính phủ bảo hộ. 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ỗ, 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- có lỗ ở giữa. Ở Nhật Bản, Trung Quốc, và ở Đông Kinh (Tonkin-Bắc Kì), 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ọc 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). Trò chơi Tháp Hà Nội vừa được phổ biến tại Paris năm 1883 đã được đón nhận rộng rãi vì sự đơn giản và hấp dẫn của nó. E. Lucas đã tỏ ra rất khôn khéo khi Ông cho sản xuất trò chơi Tháp Hà Nội với 8 đĩa, số đĩa vừa đủ để trò chơi không quá đơn giản (để chuyển hết 8 đĩa từ cọc nguồn sang cọc đích, không nhầm lẫn, cần 255 bước), cũng như không quá phức tạp (như trong trường hợp 64 đĩa, phải mất 5 tỉ năm). Ngày nay, trên mạng Internet có rất nhiều chương trình viết trên nhiều ngôn ngữ khác nhau và rất nhiều phần mềm hiển thị hướng dẫn trò chơi Tháp Hà Nội (với ba cọc hoặc nhiều hơn, trò chơi Tháp Hà Nội cải biên,...). Tại Việt Nam đã có rất nhiều lập trình viên, những sinh viên đại học đưa ra các phiên bản ứng dụng của trò chơi, giúp nó trở thành một trò chơi điện tử hấp dẫn và rất sinh động. Một số hãng điện thoại nước ngoài đã đưa trò chơi tháp Hà Nội vào điện thoại di động. 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í. 1.2 Bài toán Tháp Hà Nội tổng quát 1.2.1 Bài toán Tháp Hà Nội cổ điển n T đặt Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ), các đĩa http://www.lrc-tnu.edu.vn/ -9- n . Ta thực hiện chuyển đĩa số 1 từ cọc A sang cọc C; chuyển đĩa số 2 sang cọc B; chuyển đĩa số 1 từ cọc C sang cọc B. Khi ấy đĩa số 1 nằm trên đĩa số 2. Vậy ta hiện đã có hai đĩa nằm trên cọc B, cọc C hiện thời trống. Chuyển đĩa số 3 từ cọc A sang cọc C. Lặp lại ba bước trên để giải bài toán cho hai đĩa: chuyển đĩa số 1 và đĩa số 2 cho nằm lên trên đĩa số 3 trên cọc C. Tiếp tục làm như vậy cho bốn, năm,…đĩa. Mỗi lần dựng xong tháp từ đĩa thứ l đến đĩa thứ nhất (trên cọc B hoặc cọc C, một trong hai cọc đó trống), ta chuyển đĩa thứ l 1 từ cọc A sang cọc trống (cọc C hoặc cọc B), rồi lại di chuyển tháp đã dựng từ cọc B (hoặc cọc C) lên đĩa thứ l 1 để được tháp với l 1 đĩa. Như vậy, khi đã xây dựng xong tháp thứ l thì ta cũng dễ dàng xây dựng được tháp thứ l 1, sau khi chuyển đĩa thứ l 1 sang cọc trống. Phương pháp trên được gọi là thuật giải đệ qui: Để tiến hành giải bài toán với n 1 đĩa, ta áp dụng lại thuật giải bài toán với n đĩa. Toàn bộ quá trình là một số hữu hạn các bước, vì vậy đến một lúc nào đó thuật giải sẽ được áp dụng cho n 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc C. Kí hiệu L ( n) là số lần chuyển đĩa tối ưu trong bài toán tháp Hà Nội với n đĩa và ba cọc. Khi ấy, để chuyển n đĩa từ cọc A sang cọc C, trước tiên ta phải chuyển n 1 đĩa trên cùng (các đĩa nhỏ) từ cọc A sang cọc B, sau đó chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, lại chuyển n 1 đĩa từ cọc B sang cọc C. Ta có: L1 1, L 2 3, L(n) L(n 1) L(1) L(n 1) 2 L( n 1) 1. Theo qui nạp, ta có L(n 1) 2 L n 1 2. 2n 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 2n 1 1. http://www.lrc-tnu.edu.vn/ - 10 - Vậy công thức L(n) 2n 1 được chứng minh với mọi n . Công thức trên cho thấy, thuật toán đệ qui giải bài toán Tháp Hà Nội là thuật toán có thời gian mũ. 1.2.2 Bài toán Tháp Hà Nội tổng quát Một mở rộng tự nhiên của bài toán Tháp Hà Nội cổ điển là Bài toán Tháp Hà Nội với bốn (hoặc nhiều) cọc. 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 Bài toán Tháp Hà Nội với bốn cọc 1889 (xem [12], trang 211). Năm 1902-1903 Henry Ernest Dudeney đã viết hai bài báo về bài toán Tháp Hà Nội với bốn cọc. Trong hai trang đầu tiên của cuốn sách nổi tiếng The Canterbury Puzzles and Other Curious Problems xuất bản tại London năm 1907 và tại New York năm 1908 (xem [9] và bìa cuốn sách trong hình bên), Ông đã viết về bài toán này trò chơi tháp Hà Nội với bốn cọc (dưới dạng các quân cờ) và số đĩa là 8, 10 hoặc 21 và gọi là The Reve's puzzle-câu đố của Reve). 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 - Dưới đây là trang 1 và trang 2 trong cuốn sách của H. E. Dudeney nói về The Reve's puzzle. Trong hình vẽ có bốn chiếc ghế (4 cọc), trên một ghế có 8 quân cờ xếp chồng lên nhau. 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 - Dưới đây là lời giải bài toán The Reve’s Puzzle của H. E. Dudeney. 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 - 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 k (k 1) , k 1,2,... Giả sử tk 2 k (k 1) là số tam giác thứ k và giả sử M (n) 2 là số lần chuyển tối thiểu cần thiết để chuyển xong n đĩa. Dudeney tuyên bố mà không chứng minh rằng M 4 tk 2 M 4 tk 1 2k 1, M 4 1 1. Từ đây ta có M4 3 5 ; M4 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 [19]). Lời giải của bài toán này đã được Stewart [20] và Frame [11] 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. 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. Kí hiệu S p (n) là số lần chuyển ít nhất giải bài toán Tháp Hà Nội với p cọc và n đĩa theo thuật toán Frame-Stewart. Ta có thuật toán Frame-Stewart cho bài toán với số cọc bất kì như sau: Nếu số cọc p 3 thì sử dụng thuật toán tối ưu cho bài toán Tháp Hà Nội với ba cọc, như đã nêu ở trên. 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 - Với p 3 và n 0 chọn số 0 l n làm cực tiểu số lần chuyển các đĩa theo qui tắc (thuật toán Frame-Stewart) sau: • Chuyển l đĩa nhỏ trên cùng từ cọc nguồn sang cọc 1 ( n l đĩa dưới cùng vẫn ở trên cọc nguồn). Trong quá trình chuyển sử dụng tất cả các cọc. Điều này có thể làm được với số lần chuyển ít nhất được kí hiệu là S p (l ) . • Chuyển n l đĩa dưới cùng từ cọc nguồn sang cọc đích mất S p 1 (n l ) lần chuyển (vì cọc 1 đang được sử dụng chứa các đĩa nhỏ nên chỉ còn sử dụng được p 1 cọc). • Chuyển l đĩa từ cọc 1 sang cọc đích. Trong quá trình chuyển sử dụng tất cả các cọc. Để làm được điều này cần S p (l ) lần chuyển. Công thức truy hồi cho lời giải bài toán Tháp Hà Nội dựa trên thuật toán FrameStewart là: S p ( n) 0, khi n 0; 2n 1, khi p 3, n 0; n l , khi p 3, n 0. min 2 S p l 0 l n Sp 1 Khi đó, bài toán Tháp Hà Nội với nhiều cọc trở thành bài toán tối ưu rời rạc: Tìm S p (n) min 2S p (l ) S p 1 (n l ) . 0 l n 1 Như vậy, B. M. Stewart và J. S. Frame đã đề xuất một thuật toán giải cho bài toán Tháp Hà Nội với số cọc bất kì. Thuật toán Frame-Stewart trùng với lời giải của H. E. Dudeney trong các trường hợp riêng nêu trên. Ta cũng lưu ý 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. 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 - Tuy nhiên, Otto Dunkel [10], tổng biên tập của tạp chí The Americal Mathematical Montly khi cho đăng hai lời giải của Frame và Stewart đã 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 được rằng: trong số tất cả các giá trị có thể của l (theo thuật 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. Hai ông chưa chứng minh rằng mọi 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ì vậy 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. 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-Stewart, 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 vấn đề mới (sự tồn tại, tính duy nhất, tính tối ưu của nghiệm, độ phức tạp tính toán,…). Việc chưa chứng minh được tính tối ưu của thuật toán Frame-Stewart 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 khẳng định được số lần chuyển đĩa tối ưu, nhưng thuật toán FrameStewart 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) cho phép lập trình giải bài toán tháp Hà Nội với số cọc bất kì. Tính tối ưu của thuật toán Frame-Stewart đã được kiểm tra trên máy tính cho số đĩa nhỏ hơn 30 (xem [12], trang 179). Chủ yếu dựa theo các tài liệu [12], [13], [14]-[18], khác với [7] (chủ yếu trình bày thuật toán Frame-Stewart theo [12]), Chương 2 trình bày chứng minh một số cô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/ - 17 - thức truy hồi tính số lần chuyển tối ưu trong trò chơi tháp Hà Nội tổng quát. Đặc biệt quan tâm tới phương pháp chia để trị (the divide and conquer), mô tả qui hoạch động (the dynamic programming formulation) giải bài toán (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/ - 18 - CHƢƠNG 2 MỘT SỐ CÔNG THỨC TRUY HỒI TRONG BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT 2.1 Công thức qui hoạch động giải bài toán Tháp Hà Nội : Cho p cọc P1, P2 , , Pp n đặt n 1, được ọc. Ba các đĩa này ọc P1 ọc ọc . ừ cọc nguồn P1 sang cọc :D Pp . Gọi M n, p là số lần di chuyển tối thiểu hợp lệ cần để giải quyết bài toán Tháp Hà Nội gồm p cọc và n đĩa. M n, p , ọc P1 sang cọc Pp Bƣớc 1 (0 k k p cọc, Bƣớc 2 ba bước sau. n k M n k, p 1 n 1) sẽ ọc P1 ọc M k, p . ọc P1 sang cọc Pp . 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/ p 1 cọc - 19 - Bƣớc 3 từ cọc trung gian sang cọc Pp k cọc, M k, p k 0 k n 1 . , phương trình tối ưu mà M n, p phải M n, p min 2M k , p 0 k n 1 M n k , p 1 , n 1, p 4. (2.1.1) Khi n 0 thì không có đĩa nào để chuyển, còn khi n 1 thì ta chỉ cần một lần chuyển từ một cọc sang cọc bất kì khác. Do đó ta có M 0, p 0, M 1, p 1, với mọi p. Khi p 3 (bài toán ba cọc), để M n k , p 1 có thể bằng 1, hay k (2.1.2) M n k ,2 có nghĩa thì n k chỉ n 1. Hệ thức (2.1.1) trở thành M n,3 2M n –1,3 1. Qui nạp theo n ta được: M n,3 2n 1, n 1. (2.1.3) Công thức này cũng đã được nói đến trong Mục 1.2.1. Có thể dễ dàng tính được: M 2, p 3 với p 3, M 3, p 5 với p 4. (2.1.4) Thật vậy, bài toán tháp Hà Nội với hai cọc là không giải được trong trường hợp số đĩa lớn hơn 1. Do đó số cọc p phải không nhỏ hơn 3. Bài toán hai đĩa ba cọc cho M 2,3 3. Do đó M 2, p 3 với mọi p 3 (nếu p 3 thì số cọc là thừa, chỉ cần dùng ba cọc). Giải bài toán ba đĩa bốn cọc với tháp đĩa nằm trên cọc 1 như sau: Bước 1: Chuyển đĩa nhỏ nhất số 1 từ cọc 1 sang cọc 2. 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/ - 20 - Bước 2: Chuyển đĩa số 2 từ cọc 1 sang cọc 3. Bước 3: Chuyển đĩa số 3 từ cọc 1 sang cọc 4. Bước 4: Chuyển đĩa số 2 từ cọc 3 sang cọc 4. Bước 5: Chuyển đĩa số 1 từ cọc 2 sang cọc 4. Tháp đã xây xong. Như vậy, để giải bài toán 3 cọc 4 đĩa ta cần 5 bước. Số cọc nhiều hơn 4 là thừa. Vậy công thức (2.1.4) được chứng minh. Để tiện sử dụng về sau, ta đưa vào kí hiệu F n, k , p 2M k , p M n k, p 1 , 0 k Khi ấy phương trình tối ưu (2.1.1 M n, p Cho n 1 và p n 1, n 1, p 4. (2.1.5) : min F n, k , p , 0 k n 1 n 1, p 4 cố định. Kí hiệu k n, p 4. (2.1.6) K n, p , tức là k mà M n, p k n, p min k : 0 k n 1, M n, p F n, k , p , n 1, p 4; (2.1.7) K n, p max k : 0 k n 1, M n, p = F n, k , p , n 1, p 4. (2.1.8) Các số k n, p và K n, p được gọi là các số chia tối ưu (optimal partition number) với cặp n, p đã cho. Nhận xét rằng, với n 2 và p nếu k n, p 4 , F n, k , p là giá trị cực tiểu duy nhất nếu và chỉ K n, p . Ta có thể kiểm tra rằng: k 0, p K 0, p k 1, p K 1, p 0, với mọi p 4. 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.1.9)