矩形棋盤上構築騎士路徑之成本最佳化演算法
dc.contributor | 林順喜 | zh_TW |
dc.contributor | Shun-Shii Lin | en_US |
dc.contributor.author | 魏仲良 | zh_TW |
dc.contributor.author | Chung-Liang Wei | en_US |
dc.date.accessioned | 2019-08-29T07:44:27Z | |
dc.date.available | 2003-07-01 | |
dc.date.available | 2019-08-29T07:44:27Z | |
dc.date.issued | 2002 | |
dc.description.abstract | 騎士路徑問題(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))。 | zh_TW |
dc.description.abstract | 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. | en_US |
dc.description.sponsorship | 資訊教育研究所 | zh_TW |
dc.identifier | G000DREAMER | |
dc.identifier.uri | http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22G000DREAMER%22.&%22.id.& | |
dc.identifier.uri | http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/92628 | |
dc.language | 英文 | |
dc.subject | 騎士路徑問題 | zh_TW |
dc.subject | 分而治之的演算法 | zh_TW |
dc.subject | 漢米爾頓環境軌跡問題 | zh_TW |
dc.subject | 平行演算法 | zh_TW |
dc.subject | Knight's tour problem | en_US |
dc.subject | Divide-and-conquer algorithm | en_US |
dc.subject | Hamilton cycle problem | en_US |
dc.subject | Parallel algorithm | en_US |
dc.title | 矩形棋盤上構築騎士路徑之成本最佳化演算法 | zh_TW |
dc.title | Optimal Algorithms for Constructing Knight's Tours on Rectangular Chessboards | en_US |
Files
Original bundle
1 - 5 of 7