簡易檢索 / 詳目顯示

回結果列表
研究生： 蔡明原
Tsai Ming-Yuan
論文名稱： 倉庫番遊戲之最少搬移演算法分析與研究
The Design and Analysis of Minimum Moving Algorithm for Sokoban Game
指導教授： 林順喜
Lin, Shun-Shii
學位類別： 碩士
Master
系所名稱： 資訊教育研究所
Graduate Institute of Information and Computer Education
論文出版年： 2002
畢業學年度： 90
語文別： 中文
論文頁數： ６０
中文關鍵詞： 倉庫番遊戲 、搬移規劃問題 、死結盤面偵測 、單一代理人搜尋法 、反向搜尋 、跳躍式串列 、AVL平衡樹
英文關鍵詞： Sokoban game, motion planning problem, deadlock detecting, single-agent search, backward search, Skiplist, AVL-tree
論文種類： 學術論文
相關次數： 點閱：274  下載：33 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 倉庫番遊戲是一種搬移策略規劃的有趣問題，問題的挑戰來自於對死結盤面的偵測及如何以有用的策略減少搜尋的空間，過去的研究者以單一代理人搜尋法，透過對死結盤面動態建立盤面資訊做比對，得到了一些成果，但並未能得到最少搬移步數的答案。
    我們的研究採反向搜尋的方式來減少死結情況的發生及使死結的偵測工作容易實行。在實驗中我們也發現了跳躍式串列(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/

    QR CODE