臺灣博碩士論文加值系統

自1870年Sam Loyd提出了「14-15益智問題」之後，(n2-1)智慧盤問題也就隨之產生。問題的主要目標是有一個n x n大小的棋盤，上面只有(n2-1)顆次序錯亂的棋子，利用唯一的空格滑動四周的棋子，使這(n2-1)顆棋子能夠依照預期的順序歸回原位，找出以最少的次數完成的走法。
在本論文中，我們進一步改良了Ian Parrery的方法，利用分而治之（divide-and-conquer）和貪婪（greedy）演算法的技巧，使得能夠在最多13/3n3-59/4n2+263/12n-17次的移動中，將(n2-1)智慧盤問題解決。根據分析，在最壞情況的盤面時，至少需要n3-O(n2)次移動，因此我們的方法不會比這個數值多於13/3倍。此外，若以亂數產生的盤面而言，根據分析至少需2/3n3-2/3n2次移動，相較之下，我們的方法也不會超過其13/2倍。

The (n2-1)-puzzle has been studied by many researchers since Sam Loyd introduced the “14-15 puzzle” and its variants in 1870. Given an N x N chessboard with (n2-1) random-numbered tiles (leaving one blank block), the goal of the (n2-1)-puzzle is to rearrange all tiles in row-major order by sliding one tile adjacent to the blank repeatedly.
In this paper, we improve the method proposed by Ian Parberry. Using divide- and-conquer and greedy techniques, we solve the (n2-1)-puzzle in at most 13/3n3-59/4n2+263/12n-17 moves. It has been known that the problem requires at least n3-O(n2) moves in the worst case, so our algorithm makes no more than 13/3 times more moves than necessary. Besides, our solution makes no more than 13/2 time more than the numbers it needs in the average case (at least 2/3n3-2/3n2 moves).

目錄
附圖目錄…………………………………………………………………ii
第一章 緒論……………………………………………………………1
第一節 簡介…………………………………………………………1
第二節 文獻探討……………………………………………………2
第三節 論文架構……………………………………………………2
第二章 Ian Parberry的演算法………………………………………4
第一節 　座標系統定義………………………………………………4
第二節 　Ian Parberry的演算法……………………………………5
第三章 改良的演算法…………………………………………………8
第一節 　可以改進的構想……………………………………………8
第二節 　改良的演算法………………………………………………9
第三節 　最壞情況下的複雜度分析…………………………………13
第四章 相關定理與成果比較…………………………………………31
第一節 　拼盤問題存在一盤面的至少移動次數……………………31
第二節 　平均盤面至少需要的步數…………………………………32
第三節 　判斷某盤面能否排成正確排列……………………………33
第五章 結論與未來的方向……………………………………………36
參考文獻…………………………………………………………………39

【1】 J. C. Culberson and J. Schaeffer, Efficiently searching the 15-puzzle, Technical report, Department of Computer Science, University of Alberta, 1994.
【2】 M. Gardner, The Mathematical Puzzles of Sam Loyd (Dover, New York, 1959).
【3】 L. E. Horden, Sliding Piece Puzzles (Oxford University Press, Oxford, 1986).
【4】 R. E. Korf, Depth-first iterative deepening: An optimal admissible tree search, Artificial Intelligence 27 (1985), 97-109.
【5】 R. Korf and L. Taylor, Finding optimal solutions to the twenty-four puzzle, in Proceedings of AAAI-96 (1996), 1202-1207.
【6】 D. Kornhauser, G. Miller and P. Spirakis, Coordinating pebble motion on graphs, the diameter of permutation groups and applications, in Proc. 25th Ann. Symp. on Foundations of Computer Science (IEEE Computer Society Press, Silver Spring, MD, 1984), 241-250.
【7】 D. Michie, J. G. Fleming and J. V. Oldfied, A comparison of heuristic, interactive and unaided methods of solving a shortest-route problem, Machine Intelligence, Vol. 3 (1968), 245-255.
【8】 I. Parberry, A real-time algorithm for the (n2－1)-puzzle, Information Processing Letters, Vol. 56, (1995), 23-28.
【9】 D. Ratner and M.K. Warmuth, The (n2－1)-puzzle and related relocation problems, J. Symbolic Comput. 10 (1990), 11-137.
【10】 A. Reinefeld, Complete solution of the eight-puzzle and the benefit of node ordering in IDA*, in Proceedings of the International Joint Conference on Artificial Intelligence (1993), 248-253.
【11】 J. Schaeffer, The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence (1989), 1203-1212.
【12】 P. D. A. Schofield, Complete solution of the eight puzzle, Machine Intelligence, Vol. 1 (1967), 125-133.
【13】 S. Singh著,薛密譯, Fermat’s last theorem, 台灣商務印書館(1998), 122-125.
【14】 W. W. Storey and W. E. Storey, Notes on the 15 puzzle, American Journal of Mathematics 2 (1879), 399-404.
【15】 http://www.cut-the-knot.com/pythagoras/history15.html.