利用電腦探討中國古代益智遊戲

dc.contributor.author魏仲良zh_tw
dc.contributor.author林順喜zh_tw
dc.contributor.authorChun-Ling Wei and Shun-Shii Linen_US
dc.date.accessioned2014-10-27T15:25:33Z
dc.date.available2014-10-27T15:25:33Z
dc.date.issued1999-10-??-zh_TW
dc.description.abstract在本文中,我們嘗試設計演算法,利用電腦找出中國古代流傳下來的益智遊戲-「華容道」的最少步數,以驗證前人資料上所記載的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步,因此不能直接用暴力法搜尋,目前文獻上尚未見到電腦之解法,只有一些人為的解法有記錄,也有一些程式將這些人為的、不是最佳的解法作展示。因此我們構思如何解決此困難之問題。在此論文中,我們發展了一些技術,目標是求出完全的最佳解,並實際撰寫程式測試,要求在可容忍的時間內解出。程式的執行結果與先前得到的前人資料有所出入,有些與資料記載吻合,有的則較記錄為多,還有一些比資料上的少上三至五步之多。驗證了一下程式輸入到檔案的最佳解,發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較資料為多的部分,可能是前人的文獻資料有誤,因為資料上只記載著各盤面最少步數的解題記錄,並無參考的解法。zh_tw
dc.description.abstractIn this paper, we will design algorithms to derive the solutions for the Chinese game "Hua Rong Daw". In addition, we want to verify and compare these results with the previous literatures. Since many initial configurations of this game need more than 100 steps to reach the final configurations, we could not search the entire game tree with the "brute force" approach. Previously, there are no computer solutions for this hard problem, but there are many manual trials that are found in many documents. In this paper, we explore some techniques for totally solving this game. The results show that some previous results are not the optimal solutions. We also list our optimal solutions in this paper.en_US
dc.identifierACA85DB9-9639-7D39-4A3A-5199B24D8A24zh_TW
dc.identifier.urihttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/17535
dc.language中文zh_TW
dc.publisher國立臺灣師範大學研究發展處zh_tw
dc.publisherOffice of Research and Developmenten_US
dc.relation44(1&2),43-61zh_TW
dc.relation.ispartof師大學報:數理與科技類zh_tw
dc.subject.other遊戲樹zh_tw
dc.subject.other二元搜尋樹zh_tw
dc.subject.other暴力法zh_tw
dc.subject.otherGame treeen_US
dc.subject.otherBinary search treeen_US
dc.subject.otherBrute force approachen_US
dc.title利用電腦探討中國古代益智遊戲zh-tw
dc.title.alternativeUse Computers to Study the Solutions of the Chinese Game "Hua Rong Daw"zh_tw

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
ntnulib_ja_L0803_4401_043.pdf
Size:
807.77 KB
Format:
Adobe Portable Document Format

Collections