簡易檢索 / 詳目顯示
| 研究生： |
梁聖彥 Liang Sheng Yan |
|---|---|
| 論文名稱： |
智慧盤問題之改良演算法 An Improved Algorithm for the (n2-1)-puzzle |
| 指導教授： | 林順喜 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
資訊教育研究所 Graduate Institute of Information and Computer Education |
| 論文出版年： | 2002 |
| 畢業學年度： | 90 |
| 語文別： | 中文 |
| 論文頁數： | 40 |
| 中文關鍵詞： | (n2-1)智慧盤問題 、15智慧盤問題 、分而治之演算法 、貪婪演算法 、曼哈頓距離 、問題解決 |
| 英文關鍵詞： | (n2-1)-puzzle, 15 puzzle, divide and conquer algorithm, greedy algorithm, Manhattan distance, problem solving |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：202 下載：4 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
自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).
【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.