智能搜索算法设计和分析

THE DESIGN AND ANALYSIS OF INTELLIGNET SEARCH ALGORITHMS

提出了人工智能博弈树搜索ＳＳＳ＊算法的两种改进算法ＢＳ＊和ＤＳ＊算法，给出了ＢＳ＊和ＤＳ＊搜索博弈树端结点的充分必要条件，由此证明了，如果能估计一个合适的上界，则ＢＳ＊算法优于ＳＳＳ＊算法．同时还证明了ＤＳ＊算法优于α－β算法．论述了ＤＳ＊算法搜索深度为奇数的博弈树时，在一般情况下也优于ＳＳＳ＊算法，且这两种算法都降低了存储开销．

Two improved versions for the intelligent game tree search SSS' algorithm arepresented,they are called BS' and DS. respectively. This paper gives the'necessary andsufficient conditions for BS' and DS' to search a terminal node of a game tree,and proves that DS' is superior over SSS' if a proper upper bound can be estimated.Simultaneously,this paper proves DS' algorithm is superior over α-β algorithm and DS'is generally superior over SSS' when searching a game tree with odd depth. These twoalgorithms decrease the storage requirement.