智慧盤問題之改良演算法

An Improved Algorithm for the (n2-1)-puzzle

梁聖彥(Liang Sheng Yan)

指導教授 ： 林順喜

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2001年)

摘要

自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倍。

關鍵字

(n2-1)智慧盤問題 ； 15智慧盤問題 ； 分而治之演算法 ； 貪婪演算法 ； 曼哈頓距離 ； 問題解決

並列摘要

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).

並列關鍵字

(n2-1)-puzzle ； 15 puzzle ； divide and conquer algorithm ； greedy algorithm ； Manhattan distance ； problem solving

參考文獻

【4】 R. E. Korf, Depth-first iterative deepening: An optimal admissible tree search, Artificial Intelligence 27 (1985), 97-109.

【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.

【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.