(54.227.48.147) 您好!臺灣時間:2018/02/18 16:20          離開系統
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
研究生:蔡明原
研究生(外文):Tsai Ming-Yuan
論文名稱:倉庫番遊戲之最少搬移演算法分析與研究
論文名稱(外文):The Design and Analysis of Minimum Moving Algorithm for Sokoban Game
指導教授:林順喜林順喜引用關係
指導教授(外文):Lin Shun-Shii
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊教育研究所
學門:教育學門
學類:專業科目教育學類
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:60
中文關鍵詞:倉庫番遊戲搬移規劃問題死結盤面偵測單一代理人搜尋法反向搜尋跳躍式串列AVL平衡樹
外文關鍵詞:Sokoban gamemotion planning problemdeadlock detectingsingle-agent searchbackward searchSkiplistAVL-tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:626
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
倉庫番遊戲是一種搬移策略規劃的有趣問題,問題的挑戰來自於對死結盤面的偵測及如何以有用的策略減少搜尋的空間,過去的研究者以單一代理人搜尋法,透過對死結盤面動態建立盤面資訊做比對,得到了一些成果,但並未能得到最少搬移步數的答案。
我們的研究採反向搜尋的方式來減少死結情況的發生及使死結的偵測工作容易實行。在實驗中我們也發現了跳躍式串列(Skiplist)比AVL平衡樹在資料插入及搜尋上有較好的表現。我們的演算法經過實際程式的執行結果,與前人的研究比起來最大的突破在於我們成功地找到了90個XSokoban倉庫番遊戲中63個盤面的最少搬移步數的解答。

Sokoban game is a motion planning problem. The main challenge of this problem is to detect deadlock states and to reduce the search space with good stratagems. Previous researchers designed single-agent search methods to solve Sokoban game. Single-agnet search methods dynamically build patterns to detect deadlock, but it can not ensure that the result of moving steps is minimal.
In this thesis, we use backward search method to decrease deadlock states and to make deadlock detecting easily. In our experiments, we also find out that Skiplist has better performance than AVL-tree in inserting and searching data. Our algorithm can solve 63 out of 90 XSokoban games and find out those games’ minimal moving steps successfully, This result is better than previous researches.

附圖及附表目錄
第一章 緒論
  第一節 問題簡介
  第二節 文獻探討
  第三節 本篇論文結構
第二章 倉庫番遊戲主要課題
  第一節 人腦解題與電腦解題的不同
  第二節 死結狀況(Deadlock)的偵測
  第三節 反向搜尋遊戲盤面
  第四節 龐大的搜尋空間
第三章 倉庫番遊戲資料結構設計
  第一節 有效率地紀錄盤面
  第二節 AVL-tree與Skiplist 的比較
  第三節 Heuristic function 的設計
第四章 倉庫番遊戲解題策略分析
  第一節 箱子與目標位置配對問題
  第二節 減少搜尋空間及時間的方法
  第三節 一些不適用的策略
第五章 實驗結果
  第一節 解題流程與執行介紹
  第二節 與過去研究者成果比較
第六章 結論與未來研究方向
  第一節 結論
  第二節 未來研究方向
附錄一 XSokoban的90個遊戲盤面
附錄二 boxworld的20個遊戲盤面
參考文獻

【1】J. Andreas, S. Jonathan, “Sokoban: Enhancing general single-agent search methods using domain knowledge”, Artificial Intelligence, Vol. 129, Issue: 1-2, pp. 219-251, June, 2001.
【2】J. Andreas, S. Jonathan, “Sokoban: improving the search with relevance cuts”, Theoretical Computer Science, Vol. 252, Issue: 1-2, pp. 151-175, February 6, 2001.
【3】B. Bonet, H. Geffner, “Planning as Heuristic Search”, Artificial Intelligence, 2001.
【4】H. Christos, K. Steiglitz, “Combinatorial Optimization: Algorithms and Complexty”, Prentice-hall. Inc. 1982, Chapter 11 : “Weight Matching”, pp.247-255.
【5】T. H. Cormen, C. L. Leiserson, R. L. Rivest, “Introduction to Algorithms”, McGraw-Hill,開發代理進口。1993。
【6】J. Culberson, “Sokoban is PSPACE-complete (draft)”, Technical Report TR 97-02, Department of Computer Science, University of Alberta, 1997. Also available from http://web.cs.ualberta.ca/.joe/Preprints/Sokoban/paper.html
【7】M. Fryers, M.T. Greene, “Sokoban”, Eureka 54, 1995.
【8】R. G. Gallager, “Variations on a Theme by Huffman” , IEEE Trans. Inf. Theory, IT-24, Vol. 6, Nov. 1978, pp.668-674.
【9】J. E. Hopcroft, J. T. Schwartz, M. Sharir, “On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the Warehouseman’s problem”, J. Robot. Res. 3. pp. 76?88, 1984.
【10】M. Klein. “A primal method for minimal cost flows”, Management Science,14:pp.205-220, 1967.
68
【11】Y. Murase, H Matsubara, Y. Hiraga, “Automatic making of SOKOBAN problem”, in: N. Foo and R. Goebel (Eds.), Proceedings of 4th Rim International Conference on Artificial Intelligence (PRCAI-96). Lecture Notes in Artificial Intelligence, Vol. 1114, Springer, Berlin, 1996, pp. 592-600.
【12】I. Parberry, “A real-time algorithm for the (n2-1)-puzzle”, Information processing, J. Symbolic Comput. 10(1990) pp.11-137.
【13】W. Pugh. “Skip lists: A probabilistic alternative to balanced trees”. Communications of the ACM, 33(6), pp. 668--676, June 1990. http://iamwww.unibe.ch/~wenger/DA/SkipList/
【14】U. K. Sarkar, “On the design of constructive algorithm to solve the multi-peg towers of Hanoi problem”, Theoretical Computer Science 237(2000), pp.407-421.
【15】R. Sedgewick. “Algorithms”, Addision Wesley. (1983). pp. 443-452.
【16】I. H. Written, R. M. Neal, and J. G. Cleary, “Arithmetic Coding for Data Compression” , Comm. of the ACM, Vol. 30, No. 6, Jun. 1987, pp. 520-540.
【17】Website : Source Code for Data Structures and Algorithm Analysis in C++ http://www.cs.fiu.edu/~weiss/dsaa_c++/Code/
【18】Website : http;//xsokoban.lcs.mit.edu/xsokoban.html
【19】Website : http://www5.cs.cornell.edu/cgi-bin/andru/xsokoban/best-scores-moves
【20】Website : http://www2.tokai.or.jp/deepgreen/sokoban/

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔