查詢結果分析
來源資料
頁籤選單縮合
題 名 | 利用電腦探討中國古代益智遊戲--「華容道」之解法=Use Computers to Study the Solutions of the Chinese Game "Hua Rong Daw" |
---|---|
作 者 | 魏仲良; 林順喜; | 書刊名 | 師大學報. 數理與科技類 |
卷 期 | 44:1 1999.04[民88.04] |
頁 次 | 頁43-61 |
分類號 | 997.1 |
關鍵詞 | 遊戲樹; 二元搜尋樹; 暴力法; Game tree; Binary search tree; Brute force approach; |
語 文 | 中文(Chinese) |
中文摘要 | 在本文中,我們嘗試設計演算法,利用電腦找出中國古代流傳下來的益智遊戲--「華容道」的最少步數,以驗證前人資料上所記載各盤面的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100 步,因此不能直接用暴力法搜尋,目前文獻上尚未見到電腦之解法,只有一些人為的解答有記錄,也有一些程式將這些人為的、不是最佳的解答直接記錄下來作展示。因此我們構思如何解決此困難之問題。在此論文中,我們發展了一些技術,目標是求出完全的最佳解,並實際撰寫程式測試,要求在可忍受的時間內解出。程式的執行結果與先前得到的前人資料有所出入,有些與資料記載的吻合,有的則較記錄為多,還有一些比資料上的少上三至五步之多。驗證了一下程式輸出到檔案的最佳解,發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較前人資料為多的部份,可能是前人的文獻資料有誤,因為資料上只記載著各盤面最少步數的解題記錄,並無參考的解法。 |
英文摘要 | In 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. |
本系統中英文摘要資訊取自各篇刊載內容。