簡易檢索 / 詳目顯示

研究生: 魏仲良
Chung-Liang Wei
論文名稱: 矩形棋盤上構築騎士路徑之成本最佳化演算法
Optimal Algorithms for Constructing Knight's Tours on Rectangular Chessboards
指導教授: 林順喜
Lin, Shun-Shii
學位類別: 碩士
Master
系所名稱: 資訊教育研究所
Graduate Institute of Information and Computer Education
論文出版年: 2002
畢業學年度: 90
語文別: 英文
論文頁數: 53
中文關鍵詞: 騎士路徑問題分而治之的演算法漢米爾頓環境軌跡問題平行演算法
英文關鍵詞: Knight's tour problem, Divide-and-conquer algorithm, Hamilton cycle problem, Parallel algorithm
論文種類: 學術論文
相關次數: 點閱:237下載:12
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 騎士路徑問題(knight's tour problem)已經被研究很長的一段時間,它的規則為在一棋盤上,要找出一條路徑讓騎士恰能走過棋盤上的每一個格子一次。1992年Takefuji與Lee聲明他們尚不能確定此一問題是否屬於NP-complete的範疇。在前人的研究中所提出的方法皆僅解決了部份的子集合。舉例來說,如Ian Parberry於1997年提出一個分而治之(divide-and-conquer)的演算法,利用單一個處理器能在O(n^2)的時間內求得n x n、n x (n+1)、n x (n+2) 的盤面上的封閉騎士路徑(Closed knight's tour)。而在本篇論文中,我們提出一個新的方法可以找出任意n x m大小的棋盤上的封閉騎士路徑與開放騎士路徑(Open knight's tour),至此得以完全解決騎士路徑問題並回答了Takefuji與Lee的疑問。在只利用單一處理器的狀況下,我們的演算法所花用的時間也只僅要線性時間(O(nm))。

    The knight's tour problem has been studied for a very long period of time. The main purpose of the knight's tour problem is to find out how to construct a series of moves made by a knight visiting every square of a chessboard exactly once. In 1992, Takefuji and Lee state that they are unsure whether the problem of finding a knight's tour is NP-complete. In previous works, all researchers partially solve this problem by offering algorithms for a partial subset of chessboards. For example, among the prior studies, Ian Parberry proposes a divided-and-conquer algorithm that can build a closed knight's tour on an n x n, an n x (n+1) or an n x (n+2) chessboard in O(n^2) (i.e. linear) time on a sequential processor. In this paper, we completely solve this problem and answer the question of Takefuji and Lee by presenting a new method that can construct a closed knight's tour or an open knight's tour on an arbitrary n m chessboard if they exist. Our algorithm runs in linear time (O(nm)) on a sequential processor.

    Introduction 1 Definitions and Notations 5 Closed knight's tour 5 Open knight's tour 6 Corner-missed closed knight's tour 7 Structured knight's tour 8 Stretched knight's tour 9 Double loop knight's tour 9 Ian Parberry's Algorithm 10 Our New Method 14 Finding knight's tours on smaller boards 14 Closed knight's tour (or corner-missed closed knight's tour) 16 Open knight's tour 30 Cost and Knight's Tours in Parallel 38 Conclusion 39 Appendix A 40 Closed knight's tours 40 Corner-missed closed knight's tours 41 Stretched knight's tours 41 Open knight's tours 43 Double loop knight's tour 45 Appendix B 46 References 51

    [1] Ball, W. W. R.: Mathematical Recreations and Essays, 11th Edition, MacMillan and Co.,1939.
    [2] Ball, W. W. R., Coxeter, H. S. M.: Mathematical Recreations and Essays, 12th Edition, University of Toronto Press, 1974.
    [3] Cannon, R., Dolan, S.: The knight's tour, Mathematical Gazette, 70, 91-100 (1986).
    [4] Conrad, A., Hindrichs, T., Morsy, H., Wegener, I.: Solution of the knight's Hamiltonian path problem on chessboards, Discrete Applied Mathematics, 50, 125-134 (1994).
    [5] Domoryad, A. P.: Mathematical Games and Pastimes, Pergamon Press, 1964.
    [6] Dudeney, H. E.: Amusements in Mathematics, Thomas Nelson & Sons, 1917.
    [7] Dudeney, H. E.: Amusements in Mathematics, Dover Publications, 1970.
    [8] Filler, T.: The Solution [online]. In Knight's Tour at: http://home.earthlink.net/ ~tfiller/bts.htm, Accessed January 25, 2002.
    [9] Grimaldi, R. P.: Discrete and Combinatorial Mathematics An Applied Introduction, 4th Edition, Addison-Wesley Longman, U.S.A., 1998.
    [10] Hurd, S. P., Trautman, D. A.: The knight's tour on the 15-puzzle, Mathematics Magazine 66(3), 159-166 (1993).
    [11] Kraitchik, M.: Peg solitaire, Mathematical Recreations, W. W. Norton, New York, 1942.
    [12] Parberry, I.: Scalability of a neural network for the knight's tour Problem, Neurocomputing, 12, 19-34 (1996).
    [13] Parberry, I.: An efficient algorithm for the knight's tour problem, Discrete Applied Mathematics, 73, 251-260 (1997).
    [14] Ralston, A.: Knight's tours on odd boards, J. Recreational Mathematics, 28(3), 194-200 (1996).
    [15] Rees, G. H. J. van: Knight's tours and circuits on the 3 n chessboard (classroom notes), Bulletin of ICA, 16, 81-86 (1996).
    [16] Schwenk, A.: Which rectangular chessboards have a knight's tour?, Mathematics Magazine 64(5), 325-332 (1991).
    [17] Takefuji, Y.: Neural Network Parallel Computing, Kluwer Academic Publishers, 1992.
    [18] Takefuji, Lee, Y., K. C.: Neural network computing for knight's tour problems, Neurocomputing 4(5), 249-254 (1992).
    [19] Valtorta, M., Zahid, M. I.: Warnsdorff's tours of a knight, Journal of Recreational Mathematics, 25:4, 263-275 (1993).
    [20] Willis, S.: Hamiltonian paths and cayley digraphs of algebraic groups, UCSD Honors Thesis, 2001.

    QR CODE