學位論文

Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912

Browse

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    以線性時間在10 × n及其衍生之矩形棋盤上建構(1, 4)-開放騎士路徑之演算法
    (2010) 陳冠明
    騎士路徑問題(knight’s tour problem)已經被研究很長的一段時間，它的目的為在一棋盤上要找出一條路徑讓騎士能走過棋盤上的每一個格子恰好一次。2005年，此問題被林順喜教授和研究生魏仲良完全破解。2005年，Chia和Ong提出一般化的(a, b)-騎士路徑問題。2009年，Huang和Bai將一般化的(a, b)-騎士路徑問題簡化為 (1, k)-騎士路徑問題，並且找出了部份盤面的(1, k)-開放騎士路徑。而在本篇論文中，我們提出一個新的方法可以找出盤面的某一邊長為10，另一邊長為任意大小或者盤面某一邊長為10r，另一邊長為8s+10t的(1, k)-開放騎士路徑。而且此演算法在建構(1, k)-開放騎士路徑所需的執行時間為線性的，可以達到成本最佳化。