本文围绕搜索算法在智能控制程序中的应用,进行了两项研究:智能控制Ms.Pac-Man游戏和智能控制Tetris游戏.同时本文还包括对一般符号序列的幂律现象和长程相关模型的研究,内容提要如下:　　使用实时搜索算法智能控制非确定性游戏Ms.Pac-Man.提出使用Corner Pixel的方法来快速进行图像识别,能以较快的速度和较高的准确率满足实时性的要求.提出了高效的启发式规则,使得搜索树能在有限时间内达到需要的深度.　　使用演化算法智能控制Tetris游戏.提出了两种新的演化搜索算法:空间划分法和最近邻组合方法.使用特殊的输入序列,并对估值算法进行了优化,大大缩短了演化估值的时间.　　对一般符号序列,研究了子序列幂律现象,提出了子序列偏好增长模型.总结了两类长程相关模型,给出了产生长程相关序列的条件.分析了DFA图中的分段现象,并给出了出现分段现象的条件.　　本文具体包括了如下部分的内容:　　第一章给出了搜索算法的介绍,重点讲述了NFL(No Free Lunch)定理,给出了对此定理的一个新的证明,并讨论了NFL定理对于搜索算法的指导作用:搜索空间的优解聚集性是搜索算法有效的前提条件.然后介绍了状态空间搜索算法.状态空间搜索指在状态空间中寻找从初始状态到目标状态的最优路径问题,一般是最短路问题.通过介绍可采纳性和上下界,给出了状态空间搜索算法的一般框架.　　第二章和第三章详细介绍了Slide Puzzle问题和Rubik’s Cube两个经典的状态空间搜索问题,具体包括部分状态的不可达性、对已有启发式的综述介绍、对称性的使用、通过下界求最短路和通过上界求连通图直径.目前国内关于这方面的介绍很少,希望这部分内容能对读者有所裨益.　　第四章是实时状态空间搜索算法在智能控制Ms.Pac-Man游戏中的应用.首先详细综述了前人的方法与结果.我们将游戏迷宫描述为网络,游戏中的个体用网络中的位置和运动方向来描述,这些合起来作为游戏的状态.提出了Corner Pixel的方法来快速进行游戏中的图像识别,结果表明,这个方法能以较快的速度和较高的准确率满足实时性的要求.然后使用状态空间的搜索算法评估各种走法,评估结果作为决策参数,以决定最优的走法.由于游戏的非确定性和实时性,搜索算法只需也只能搜索较小的一个深度.由于游戏的复杂性,搜索算法不能独自提供最终决策,而只是提供参数,这些参数再经过人工指定的规则形成最终决策.最终的结果表明,我们的方法效果显著好于已有的其它方法.　　第五章介绍了解空间搜索算法.解空间搜索指在参数空间中寻优问题.介绍了演化策略、遗传算法和交叉熵方法,并从优解的聚集性角度,给出了这些算法为何有效的直观说明.在优解聚集的基础上,我们提出了两种新的演化搜索算法:空间划分法和最近邻组合方法.空间划分法基于“产出/投入”的思想,在优解附近的空间重点搜索;最近邻组合方法则通过对已有优解的线性组合,完成在优解附近的空间重点搜索.　　第六章是解空间搜索算法在智能控制Tetris游戏中的应用.首先介绍了Tetris游戏及其必输的理论.然后介绍了自动控制Tetris游戏的一般方法:演化权重法,包括特征选择和演化方法,并介绍了前人已有的结果.然后介绍了自动控制Tetris游戏的困难性:对一个算法,或者说一组参数,估值的计算时间过长,结果的巨大波动性以及随之而来的过拟合问题.通过对估值算法的仔细分析,我们仔细优化了相关的算法,并使用特殊分布的积木序列来大大加速估值过程.通过使用训练集和测试集,加速了估值速度,并一定程度上减少了过拟合的影响.初步的结果表明,我们的方法能显著减少训练时间并得到更好的训练结果.　　第七章和第八章是关于一般序列的子序列幂律和长程相关模型.自然界和人类社会中的大量现象可以归结为符号序列和数字序列,幂律和长程相关是两个重要研究方向.子序列幂律是对传统幂律的推广,在DNA、语言、计算机程序甚至音乐中广泛存在.我们对包括完整的人类DNA在内的海量数据进行实证分析;提出子序列偏好增长模型,并进行理论分析推导.在长程相关模型方面,我们总结出两类通用的机制:逆傅立叶变换法和分段模型.在此基础上,讨论各个模型对应的段长分布,并对实际数据进行实证.最后讨论重复和长程相关的关系.