Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/92637
Title: 倉庫番遊戲之最少搬移演算法分析與研究
The Design and Analysis of Minimum Moving Algorithm for Sokoban Game
Authors: 林順喜
Lin Shun-Shii
蔡明原
Tsai Ming-Yuan
Keywords: 倉庫番遊戲
搬移規劃問題
死結盤面偵測
單一代理人搜尋法
反向搜尋
跳躍式串列
AVL平衡樹
Sokoban game
motion planning problem
deadlock detecting
single-agent search
backward search
Skiplist
AVL-tree
Issue Date: 2002
Abstract: 倉庫番遊戲是一種搬移策略規劃的有趣問題,問題的挑戰來自於對死結盤面的偵測及如何以有用的策略減少搜尋的空間,過去的研究者以單一代理人搜尋法,透過對死結盤面動態建立盤面資訊做比對,得到了一些成果,但並未能得到最少搬移步數的答案。 我們的研究採反向搜尋的方式來減少死結情況的發生及使死結的偵測工作容易實行。在實驗中我們也發現了跳躍式串列(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.
URI: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=%22http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22G0068908013%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/92637
Other Identifiers: G0068908013
Appears in Collections:學位論文

Files in This Item:
File Description SizeFormat 
801301.pdf186.06 kBAdobe PDFView/Open
801302.pdf130.87 kBAdobe PDFView/Open
801303.pdf153.54 kBAdobe PDFView/Open
801304.pdf249.79 kBAdobe PDFView/Open
801305.pdf708.52 kBAdobe PDFView/Open
801306.pdf18.98 kBAdobe PDFView/Open
801307.pdf423.34 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.