學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
1 results
Search Results
Item 較高維度演繹競局問題最佳演算法之設計與分析(2009) 黃立德; Li-Te Huang隨著眾多領域中最佳化問題的逐步探索，發現許多重要的問題都能被轉換成演繹競局問題(deductive game)的模型，例如編碼理論(coding theory)、電路測試(circuit testing)、密碼系統破解(differential cryptanalysis)、附加條件搜尋(additive search problem)等問題。換言之，在演繹競局問題上的研究將使其他相關領域問題的求解露出希望曙光，因此發展有效解決演繹競局問題的方法變得不容遲緩。 在過去數十年間，有許多針對演繹競局問題的研究產生。Mastermind與AB game(或稱為Bulls and Cow)是最有名的兩種演繹競局問題，知名的電腦科學家Donald E. Knuth在1976年於論文中介紹此二者並針對Mastermind做相關研究。在本論文中，我們提出一系列理論剪裁(theoretical-pruning)的最佳化方法與數學證明來解決這兩種問題。 在運用這些新方法到欲解決的問題後，我們得到下列新的成果： (1)我們提出一個適用於各種演繹競局問題的admissible heuristic。同時，我們根據此admissible heuristic，提出一個更有效率的演算法來解決Mastermind，最後亦得到Mastermind在平均狀況下的最佳策略。 (2)針對AB game，我們提出一個更精緻的剪裁演算法(pruning algorithm)來處理它。很幸運地，最後我們得到AB game在平均狀況下的最佳策略且其平均猜測次數為5.213。 (3)我們針對在最差狀況下3×n AB games的最佳策略做理論性的分析。最後我們成功地導出一個計算最差狀況下的最佳猜測次數之公式。 (4)我們研究一個AB game的變型，稱為容許一次錯誤回應之AB game。最終我們求得其最佳猜測次數為8。