師大學報：數理與科技類

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

Browse

Author: search.filters.author.林順喜

Search Results

Now showing 1 - 4 of 4
  • No Thumbnail Available
    Item
    梅姬之環（Rings of the Magi）遊戲的電腦解法研究
    (國立臺灣師範大學研究發展處, 2002-04-??) 賴信全; 林順喜; Hsin-Chuan Lai and Shun-Shii Lin
    在本文中，我們嘗試利用電腦的高速運算能力及龐大的記憶空間，配合資料結構及適當的演算法來求出梅姬之環(Rings of the Magi)遊戲各種盤面的可行解。一般人在玩此遊戲時並無一定的規則可循，大多以直覺、本能判斷及經驗來求解，大多數人類的專注力及推理力很難判斷下一步所有的狀況並記憶所有走過的盤面，而且也無法週詳的考慮如何走對盤面的影響會有解或無解。而且此遊戲有許多盤面的解法步數極大，且盤面狀態總數極為龐大，不能以暴力法或尋常方法搜尋求解，因此我們構思如何解決此困難的問題。在此論文中，我們發展了一些有用的技術，目標是能求出一些矩形無障礙盤面的解答，並實際撰寫程式測試，要求在可忍受的時間內求得可行解。希望拋磚引玉，藉此論文引起大家對此問題進一步研究的興趣。
  • No Thumbnail Available
    Item
    Constant-Time Algorithms for Dominating Problem on Circular-Arc Graphs
    (國立臺灣師範大學研究發展處, 1999-10-??) 林順喜; 李青芳; Shun -Shii Lin and Ching-Fung Lee
    在本篇論文中，我們利用可重組態匯流排之處理器陣列（PARBS, processor arrays with reconfigurable bus systems）具有在O(1)時間中動態連結內部不同的匯排流之特性，在常數時間內解決在環弧圖(circular-arc graphs)上的支配問題(the dominating problem)。關於環弧圖上的支配問題，以前尚未有人在常數時間內解決，即使是在理想的PRAM模型上也是如此，在本論文中，我們改良Yu[14][15]中提到的相關演算法，然後再自行發展出一套理論，並且將之推廣至可重組態匯流排之處理器陣列模型上。我們以O(n2)個處理器之可重組態匯流排處理器陣列作為主要的計算模型，使得我們能在常數時間內解決支配問題。
  • No Thumbnail Available
    Item
    利用電腦探討中國古代益智遊戲
    (國立臺灣師範大學研究發展處, 1999-10-??) 魏仲良; 林順喜; Chun-Ling Wei and Shun-Shii Lin
    在本文中，我們嘗試設計演算法，利用電腦找出中國古代流傳下來的益智遊戲-「華容道」的最少步數，以驗證前人資料上所記載的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步，因此不能直接用暴力法搜尋，目前文獻上尚未見到電腦之解法，只有一些人為的解法有記錄，也有一些程式將這些人為的、不是最佳的解法作展示。因此我們構思如何解決此困難之問題。在此論文中，我們發展了一些技術，目標是求出完全的最佳解，並實際撰寫程式測試，要求在可容忍的時間內解出。程式的執行結果與先前得到的前人資料有所出入，有些與資料記載吻合，有的則較記錄為多，還有一些比資料上的少上三至五步之多。驗證了一下程式輸入到檔案的最佳解，發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較資料為多的部分，可能是前人的文獻資料有誤，因為資料上只記載著各盤面最少步數的解題記錄，並無參考的解法。
  • No Thumbnail Available
    Item
    完全圖上最大權重配對問題之自我穩定演算法的設計及分析
    (國立臺灣師範大學研究發展處, 2000-04-??) 陳瑞宜; 林順喜; Rue-Yi Chen and Shun-Shii Lin
    在1974年，Dijkstra提出了自我穩定的概念。一個分散式系統不論其初始狀態為何，最後都會收斂至正確的系統狀態稱之為自我穩定系統。近年來，自我穩定演算法不用初始化的特性受到許多研究者的重視。Hsu和Huang針對分散式網路中「最大配對」問題提出了自我穩定演算法，並利用變數函數分析法，證明了此演算法需耗用的時間複雜度為O(n3)，然而Tel針對此一演算法提出不同的變數函數，證明最多需要O(n2)的時間複雜度。在本論文中，我們將自我穩定系統的理論應用在完全圖上的「最大權重配對」問題，設計出包含五個規則的自我穩定演算法，並針對此自我穩定演算法的正確性進行證明分析。最大權重問題是指當節點兩兩配對之後，其線段權重兩兩交換並不會找到更大的值，也就是除了希望在圖中找到最大配對之外，更進一步能夠使配對的權重達到最大。因此我們結合了Hsu-Huang最大配對自我穩定演算法，以及嶄新的交換配對規則，保留自我穩定系統容錯及自我穩定的特性，設計了時間複雜度為O(n2+nk)的一個最大權重配對問題之自我穩定演算法。