四柱河內塔問題是河內塔問題的一個延伸，在此問題中，藉由增加一個柱子，使得碟子的搬移更有彈性，也因此增加尋找最佳搬移方法的困難度。Frame 與 Stewart 在1941 年分別提出四(多)柱河內塔問題的解法。此法稱為presumed optimal solution，是目前已知最好的方法，但至今尚未被證明最佳。河內塔問題可化簡成河內塔起點s 至c1, c2, …cn/2 中最近點問題，由於目前尚未有人能提出四柱河內塔最短路徑演算法，本計劃預計利用河內圖上圖形的特性與最短路徑性質，推導出最短路徑的遞迴關係，並提出計算最短路徑長度演算法與最短路徑的演算法，並利用所提演算法進行presumed optimal solution 之驗證。本計劃為二年計畫，在第一年計畫中，我們已經證明同構關係、遞迴關係、結構內最短路徑性質與最短路徑不會經過子結構H2 與H3。並預計完成證明兩相鄰邊節點最短路徑性質、兩對邊節點最短路徑性質並推導最短路徑遞迴關係。在第二年計畫中，我們預計依據第一年計畫所得之最短路徑遞迴關係提出計算最短路徑長度遞迴演算法與最短路徑演算法、並分析所提出各演算法之時間與空間複雜度、以及利用圖形處理器將所提出演算法平行化進行presumed optimal solution 之驗證。
The Tower of Hanoi problem with four pegs was proposed by Henry Dudeney in 1907. In 1941, Frame and Stewart each gave a solution to solve the problem. The Frame-Stewart algorithm or "presumed optimal solution" is the best known for the problem, but has not been proved to be optimal. A graph call Hanoi graph which is used to model the multi-peg tower of Hanoi problem. In the first-year project, we try to study the graph properties of the Hanoi graph. Then we plan to derive the recursive relation between the shortest paths in different size Hanoi graph. In the second-year project, an algorithm will be proposed to calculate the distance of shortest paths in the tower of Hanoi problem with four pegs. Besides, we will verify presumed optimal solution by using proposed algorithm.
