學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
1 results
Search Results
Item 容許多次錯誤回應之演繹競局問題之研究(2005) 黃立德; Li-Te Huang今日的資訊科學領域日新月異、發展迅速，許多相關應用領域的重要關鍵技術，如：容錯通信（fault-tolerant communication）、電路測試（circuit testing）、附加條件搜尋（additive search problem胝）以及密碼學中的差分密碼分析(differential cryptanalysis)等組合計算最佳化問題皆與演繹競局最佳化問題相關。 在本論文中，我們提出嶄新且有系統的演算法解決著名的Mastermind和AB game等兩個演繹競局問題之變形“容許e次錯誤回應的Mastermind演繹競局問題”與“容許e次錯誤回應的AB game演繹競局問題”。首先我們使用k分支演算法（KWB）針對不同的e值求得此類問題所需猜測次數的上限。藉由分群技巧，KWB演算法能有效且有效率的求得接近最佳的結果。另一方面，我們根據鴿籠原理的觀念，發展出一個以鴿籠原理為基礎的快速式回溯驗證演算法（PPBFB）來求出所需猜測次數的下限。這是一種電腦輔助驗證演算法，在搜尋過程中它能估計競局樹的高度，且當高度超過我們欲驗證的值時，就回溯並繼續驗證其他分支。此外我們更進一步提出「容量更新」和「預先處理」二種創新的技術，能更有效的提升下限估計的準確度和搜尋的速度。 我們提出的KWB演算法與PPBFB演算法可推廣到任意次數錯誤回應之演繹競局問題，而且若使用KWB演算法時，在空間與時間允許的情況下，我們可以增加k值，以求出更好的策略。目前我們使用KWB演算法和PPBFB演算法得到以下的成果： (1) 對容許一次錯誤回應的Mastermind，我們求得此問題所需的猜測次數之上限和下限皆為7。因此我們完整的解決此問題而且求出在最差情況下最佳的猜測次數為7。 (2) 對容許一次錯誤回應的AB game，我們得到此問題所需的猜測次數之上限為9、下限為8。 (3) 對容許二次錯誤回應的Mastermind，我們求得上限與下限分別為10和7，而對容許二次錯誤回應的AB game，得到的上限與下限分別為15和8。 此外，針對容許一次錯誤回應的Mastermind與容許一次錯誤回應的AB game，我們將找到的競局策略表示成遞迴表示法，並實作成線上對局系統，供作後續驗證及研究之用。