Browsing by Author "Chung-Liang Wei"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    矩形棋盤上構築騎士路徑之成本最佳化演算法
    (2002) 魏仲良; Chung-Liang Wei
    騎士路徑問題(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))。