模式搜索算法（精选7篇）
模式搜索算法 篇1
1 引言
视频编码标准H.264/AVC的压缩效率比MPEG-2、MPEG-4提高了近1倍[1],与此同时也造成了运算量的大幅增加,因此高效快速的运动估计算法成为H.264实时编码器实现的关键。由于运动是视频序列固有的根本特征,所以有效利用和适应运动特征的运动估计算法可以显著提高搜索速度和编码效率。
目前,典型的快速搜索算法有三步搜索法、四步搜索法、菱形搜索法、六边形搜索法、预测运动矢量场自适应搜索算法(PMVFAST)、具有匹配预判的自适应不规则模板搜索算法(AIPS-MP)等。此外,我国研究人员还提出了非对称十字型多层次六边形网格搜索算法(UMHexagonS)[2,3],这种算法采用整数像素运动估值,在高码率、大运动图像序列编码中能保持较好率失真性能,运算量很低,已被H.264标准采纳。
2 PAFME算法
实验发现,UMHexagonS算法的搜索策略也存在一些缺点和不足,如:对于不同的运动序列都采用固定的搜索模板和相同的搜索策略,这样虽能保证较高的搜索精度,但由于没有充分利用不同序列及不同块的特征,不能自适应地结束搜索,因此存在较多的冗余搜索点,造成搜索开销增大。笔者结合H.264标准采用的可变块尺寸运动估计技术的特点,提出了一种搜索模式自适应的快速运动估计算法(Search Pattern Adaptive Fast Motion Estimation,PAFME),并通过实验测试了算法性能。PAFME算法主要采用以下核心技术:初始搜索点预测,多搜索模式选择,利用经验阈值调整搜索模式的使用。
该算法的主要思想是在保证图像质量的前提下,减少算法中的冗余搜索点,从而加快运行速度。在该算法中使用由经验得到的整数型常数作为基值;对不同尺寸的块类型,采用对基值进行简单的移位操作,以作为不同的判断阈值。
在搜索的过程中,首先对初始预测点集中的部分预测点(中值预测点及原点)进行搜索,包括小菱形四点搜索和可能的密集搜索步骤;仍不满意,再搜索上层块类型预测点,而后按当前最佳点进行小菱形搜索或可延伸的六边形和小菱形搜索步骤。算法流程如图1所示。
3 实验结果与分析
把新算法嵌入到H.264的标准参考软件JM12.4中进行测试比较,以验证其有效性。测试条件:在基本框架下,采用SATD和RDO指标,搜索范围为所有编码模式,1/4像素精度,参考帧数为1,第一帧为I帧,其余为P帧。测试序列有:Forman(QCIF,10 f/s(帧/秒)),Paris(CIF,15 f/s),Football(SIF,30 f/s),各100帧。之所以选用纹理和运动复杂度各不相同的3种测试序列,格式、帧率均有差异,是为了充分测试算法对不同内容的视频序列在不同目标下的应用性能,并且选用4种量化参数以测试算法在不同码率下的性能。
采用亮度信号的峰值信噪比(PSNRY)、比特率、整数像素精度运动估计总时间(t)等指标对PAFME算法与JM12.4参考软件采用的快速算法(JM12.4FME)的性能进行比较,实验结果详见表1。可见,PAFME算法具有以下特点:1)PSNRY平均损失0.018 d B,最大不超过0.088 dB,所以新算法对视频重建质量的影响可忽略;2)比特率的增加未超过0.7%,所以新算法对编码效率影响很小;3)运算量有较大降低,整像素精度运动估计速度提升明显,耗时平均减少33%。
对上述测试序列,在不同量化参数下,PAFME算法与JM12.4FME相比,其整像素精度运动估计的耗时百分比(tPAFME/tJM12.4FME)见图2。由图可见,在不同量化参数下,PAFME算法性能稳定,即新算法的有效性受量化参数影响较小。对不同特征的信号序列,算法性能有所差异,对运动一致性较好的序列,整像素精度运动估计的耗时可减少35%以上,搜索速度较快。
4 小结
笔者针对现有算法的不足,提出搜索模式自适应的快速运动估计算法PAFME,结合H.264标准采用的可变块尺寸运动估计算法的特点,利用运动矢量在时空域及不同编码模式间的相关性,设计了初始搜索中心的预测方法。通过测试发现:自适应的搜索模式选择规则可以显著地加快运算速度,并保持了视频质量和码率基本不变,为高速的运动估计提供了一种新的方向。
摘要：提出了一种搜索模式自适应快速运动估计算法(PAFME),首先利用变块尺寸运动估计的特点与运动矢量的时空域相关性,预测初始搜索中心;采用多种搜索模式以适应不同运动特征,提出了搜索模式自适应的选择机制,以节省不必要的搜索点加快搜索速度;又能避免陷入局部极小。实验结果表明,与H.264/AVC的参考软件JM12.4相比,该算法使整像素精度运动估计的速度提高了30%～40%,同时保持了图像质量和码率基本不变。
关键词：运动估计,搜索模式自适应,H.264
参考文献
[1]OSTERMANN J,BORMANS J,LIST P,et al.Video coding with H.264/AVC:tools,performance,and complexity[J].IEEE Circuits and Systems Magazine,2004,4(1):7-28.
[2]CHEN Zhibo,ZHOU Peng,HE Yun.Fast motion estimation for JVT,Doc.JVT-G016[C]//Proc.7th JVT Meeting,2003.Pattaya,Thailand:JVT,2003.
[3]CHEN Zhibo,ZHOU Peng,HE Yun,et al.Fast integer pel and fractional pel motion estimation in for JVT,Doc.JVT-F017[C]//Proc.6th JVT Meeting,2002.Awaji,Island,JP:JVT,2002.
模式搜索算法 篇2
关键词：对等网络,混合P2P模式,资源搜索
0 引言
最近几年, 点对点 (P2P) 网络迅速成为计算机界关注的热门话题之一, 财富杂志将P2P列为影响Internet未来的四项科技之一。P2P是一种网络模型, 在这种网络中所有的节点是对等的, 各节点具有相同的责任与能力并协同完成任务, 对等点之间通过直接互连共享信息资源、处理器资源甚至高速缓存资源等。
实现P2P技术的关键是在网络环境不断变化的情况下, 如何快速定位节点位置、确定合适路径并建立连接。目前常见的P2P网络结构有以下三种: (1) 集中式的P2P模式:在这种模式中, 一台或多台中央目录服务器连接若干个对等节点, 为其提供目录服务。对等节点向目录服务器注册自身的信息, 通过对目录服务器的访问, 进行节点信息的查询, 从而定位其它对等点。这种结构采用快速搜索算法, 排队响应时间短, 具有高性能和高弹性;但一旦中央控制点出现故障便会中断服务, 灵活性不够好。 (2) 分布式P2P模式:这种模式不再使用中央目录服务器, 网络中只存在对等的节点, 每个节点自行接入网络, 与自己相邻的节点建立连接。对等节点之间的信息查询和文件共享在相邻节点间通过广播的方式在全网进行接力传递, 形成大量网络流量, 导致搜索速度慢, 排队响应时间长。 (3) 混合式P2P模式:这种模式综合了前两种模式的优点, 用分布的超级结点取代中央目录服务器。节点按能力不同 (计算能力、连接带宽、网络滞留时间等) 分为普通节点和超级节点两个层次。其中超级节点与其临近的若干普通节点之间构成一个自治的簇, 簇内采用集中式的P2P结构, 而簇与簇之间再通过分布式P2P的结构将超级节点相连起来。这种结构综合了集中式P2P快速查找和分布式P2P无中心化的优势:分层次的快速搜索可以快速发现内容分布存储的位置, 改进了搜索性能, 缩短了排队响应时间, 超级节点的加入提高了网络性能和弹性。
1 混合P2P模式资源搜索算法分析
根据混合P2P模式中的超级节点间的查询转发和结果返回的方式不同, 有两种实现策略:全连接方式和部分连接方式。
全连接方式是指超级节点RVP在转发查询时, 向其所有相邻超级节点RVP发出查询并且收到查询的RVP把自已的本地查询结果直接返回给最初发起查询的RVP (如图1所示) 。RVP A发出的查询被RVP A的各相邻RVP转发, 所有搜索到结果的RVP, 将把结果直接返回给RVP A。
部分连接方式是指超级节点RVP在转发查询时, 依据某种规则, 仅向与其相邻的某些RVP发出查询, RVP完成查询后, 将结果沿查询的原路径反向传回最初的查询RVP。如图2所示, RVP A仅向其两个相邻RVP转发查询, 并且结果被反向传回。部分连接方式具有比全连接方式更好的总体性能:
(1) 大量减少网络连接数。
(2) 转发的查询数量减少。
但其缺点是:搜索范围比全连接方式小以及搜索速度也要慢。
2 混合P2P模式资源搜索算法改进
2.1 改进思想
同一个查询消息在一个节点被重复处理或在同一条路径上重复转发, 则称之为冗余消息。我们研究发现, 产生指数级查询消息的冗余的原因是一个节点不管是否已处理了这个消息都接收它所有邻居重复发来的同一个查询消息, 当在本节点未找到结果时又向它所有邻居广播。在全连接方式中, 当网络中的超级节点RVP数量很大时, 查询请求会被大量的RVP接收和转发, 从而有可能像Gnutella网络一样产生大量的冗余查询消息和查询结果在网络中转发, 形成大量网络流量, 导致搜索速度慢, 排队响应时间长, 也增加了最初发起查询的超级节点的负担。针对这些问题, 特别是减少查询消息在P2P网络中转发时所产生的大量冗余信息以及提高查找效率, 我们设想:每个超级节点仅对某个查询消息第一次到达时进行本地查询或转发, 而后面到达的相同查询消息都不进行处理, 从而避免了产生大量冗余查询消息;查询结果直接返回给发起查询的节点而不是沿原路返回, 提高查询结果的返回速度。
2.2 改进策略
每个超级节点RVP维护一个已经处理的查询消息表, 它记录第一个到达的查询消息的ID。当查询消息到达时, 先查询此表来判断它是否是第一次到达本RVP, 每个RVP只对第一个到达的查询消息进行本地查询或转发, 然后把本地查询结果直接返回给最初发起查询的对等点而不是最初发起查询的RVP, 如图3所示, 边缘节点A (Edge Peer A) 发起查询消息, 本地RVP B先通过本地查询来满足边缘对等点的需要。如果本地RVP B不能找到满足要求的查询结果时, RVP B向其所有相邻RVP发出查询, 同时发出的查询被RVP B的各相邻RVP按照改进的转发策略进行转发, 最后把查询结果直接返回给最初发起查询的Edge Peer A, 从而加快了查询结果的返回速度。然后Edge Peer A再把查询结果的相关信息发生给本地超级节点, 这样就能有效地减少后继相同查询的代价和提高查询速度。
2.3 信息表及消息的定义
(1) DisposedQueryTable
每个汇聚对等点维护一个已经处理的查询消息表Disposed QueryTable, 它记录第一个到达或已经被处理了的查询消息的QueryID和最初发起此查询的对等点的PeerID, 如下所示。
(2) QueryMsg
QueryMsg:查询消息。如下所示, 其中MessageType是消息类型, 分为查询消息和响应消息;QueryID是查询消息的ID;QueryContent为查询内容;TTL (Time To Live) 为查询消息传播的最大范围;PeerID为最初发起查询消息的对等点的ID。
(3) QueryResponseMsg
QueryResponseMsg:查询响应消息。如下所示, 其中MessageType为响应消息ResponseMsg;ResponseID是响应消息的ID;QueryResult是查询结果。
2.4 改进算法描述
改进后的消息查询、转发以及结果返回算法的详细描述如下:
3 实验结果比较与分析
为了验证改进算法的综合性能, 以NS-2网络仿真器为实验平台, 从查询消息冗余量和查询结果返回延时两个性能指标对混合P2P网络模式的全连接方式和改进后的消息查询转发与查询结果返回算法进行对比分析。
使用的网络模拟器有:packet-level Gnutellasim, NS2, gtitm。NS2是一个广泛使用的网络模拟器软件, 但是NS无法建立P2P网络, 本文需要在NS之上使packet-level Gnutellasim和gt-itm来建立P2P网络拓扑结构。其模拟过程如下:要运packetlevel Gnutellasim, 先安装网络模拟器NS2, 然后使用GT-ITM建立网络拓扑结构。为了得到实际的P2P网络系统, 需要对GT-ITM进行一些修改:将sgb2ns文件进行修改, 重新编译后, 放置在gt-itm/bin子目录下, 就可以在gt-itm下运行sgb2ns了, 这样就可以将gt-itm的输出转换为NS2形式了。
为了便于分析, 在NS2的tcl脚本中进行参数设置:设网络带宽为1.5Mbps, 数据源端节点以固定的速率连续产生数据流, 数据包高效有序地在网络中传输, 共享文件的数量为10, 节点邻节点个数为2-4, TTL=8s。仿真结果如图4和5所示, 性能参数如表1所示。表1记录了全连接方式与改进后的查询转发与结果返回机制在第6跳时所产生的查询消息冗余量和查询结果平均返回延时。
实验结果表明, 这种改进后的查询转发与结果返回方式的优点除了具有混合型P2P模式的优点外还体现在:
(1) 对于来自同一个节点的查询消息, 每个RVP只处理第一个到达的查询消息, 减少了50%左右的冗余查询消息在RVP间的传播与查询。
(2) 查询结果直接返回到最初发起查询的对等点, 平均延时为8.7s, 返回速度提高了27.2%。
(3) 查询结果直接返回到最初发起查询的节点, 也减轻了最初发起查询的超级节点RVP的负载。
4 结论
本文分析了混合P2P模式存在的缺陷, 针对这些缺陷提出了一种资源搜索的改进算法, 该搜索算法使查询消息以洪泛式扩散到达邻居节点, 每个超级节点对同一个查询消息仅处理一次, 对于后来的冗余消息都不处理, 查询结果直接发给发起查询的节点。实验结果表明, 本文提出的改进搜索算法, 既继承了原混合P2P模式的搜索速度快和覆盖范围广的优点, 又减少大量冗余信息和有效地提高可扩展性, 并且利用此搜索算法所搜索出的成功结果可用于指导后来的查找请求, 从而能够快速定位到目的节点和提高搜索效率。
参考文献
[1]罗杰文.Peer to Peer综述[EB/OL].http://www.intsci.ac.cn/users/luojw/papers/p2p.htm.
[2]Geoffrey.F.Peer-to-Peer Networks[J].Computing in Sci2ence&Engineering.2001.
[3]周功业, 黎书生.新一代网络计算模型——P2P及其JXTA体系结构的设计与实现[J].计算机应用研究.2002.
[4]Gutella Protocol Specification.http://www9.limewire.com/de-veloper/gnutella_protocol_0.4.pdf.2001.
[5]Ben Byer, EvanMartin, Colten Edwards, et al.Napster messages[EB/OL].http://opennap.sourceforge.net/napster.txt.
[6]Beverly Yang, Hector Garcia-Molina.Improving Search in Peer-to-Peer Networks[R].Technical report, Stanford University.March 2002.
模式搜索算法 篇3
在现代社会中,火灾、爆炸、坍塌事故常有发生,救援过程中因建筑情况不清,意外坍塌事故等导致救援人员遇难的惨剧时有发生。为避免此类事故,应用机器人及时探知险情和受困人员的情况和位置有着极大的应用意义。论文中将机器人所面临的搜救环境抽象为一个迷宫,而搜救就是要在迷宫中先搜索到目标物并带着目标物返回到出发点处。
迷宫的种类[1]有很多,而用的比较普遍的是Perfect迷宫,所谓的Perfect迷宫是一种没有任何环路且没有任何不能到达的区域。本次实验中,所选择的迷宫环境都为Perfect迷宫。目前,经典的搜索路径算法有D*算法和A*算法,而在迷宫中运用最为普遍的搜索算法是泛洪算法,而泛洪算法是一种基于改进的深度优先搜索算法[2]。泛洪算法在搜索过程中多次遇到目标点,但它的目的是要从这些路径中找到最快到达目标点的一条路径,原始的泛洪算法不适合本次实验中的搜救应用,于是,我们在实验中是用深度优先搜索算法进行比较研究。Takayuki Goto,Takeshi Kosaka研究了A*以及D*算法在ITS(智能运输系统)和机器人路径规划中的应用,确定了A*算法以及D*算法的优势[3]。而对于A*算法中启发式函数的选取,已有多种选择。在启发式函数的选取上,有对A*算法估价函数所出现的问题,将距离和角度进行归一化处理[4];也有对当前节点进行评估的思想上,增加了最短路径中当前节点的父节点,并对当前节点与终节点的距离进行了评估,这使得A*算法的搜索方向更加趋向终点,从而提高了搜索速度[5];还有一般情况下对启发式函数的设定选择为两点间的欧几里得距离[6];
本次实验中,将分别对含有三种不同启发式函数的A*算法与深度优先搜索算法用于迷宫中进行比较仿真研究。
1 实验研究
1.1 实验研究方法
实验研究目的是将算法用于现实搜救中,既然是为了搜救,那么时间是关键,搜索迷宫所用时间的长短就成为评价算法优劣的主要因素。对于机器人来说,所处的迷宫环境是未知的,它只能通过传感器感测到目标点所在的大致位置,然后根据算法一步一步的搜索到目标物。从出发点处找到目标物时所耗的时间我们记录为搜索迷宫所用的时间,当然,搜救的目的不仅仅是为了找到目标物,同时是需要在找到目标物后将目标物带回至出发点处。从目标点返回到出发点时,如果沿之前的原路返回,那就会浪费很多没必要的时间,使搜救时间变长,所以我们要做的工作是要将之前的走过的路径进行优化,使机器人带着目标物返回出发点时不用走“冤枉路”,从而节省搜救时间。
真实环境中,目标物在目标点处通过敲打墙壁或地面等发出声音,模拟“呼救”,从而让机器人通过传感器感知到目标物。但由于外界因素(例如:传感器的精度,迷宫环境中障碍物对声音的阻碍作用等)的干扰会导致机器人只能判断出目标物的大致位置,这个大致位置是随着机器人离目标物越来越近而会越来越精确,直至找到目标物。
而在本次仿真实验中,为了能够比较真实的模拟真实环境,我们人为的让目标点坐标产生了一定的偏差,并且让这个偏差值随着机器人越来越靠近目标点而变得越来越小。
1.2 深度优先搜索算法
所谓“深度优先”,即:状态树的生长或展开,首先沿状态树的深度方向进行。深度优先搜索算法需要记录下状态树的生长过程,深度优先搜索算法是一种盲目的搜索算法,搜索中可能很多次的搜索到目标点,深度搜索算法通过不断剪枝,寻找出一条从起始点到目标点最近且最省时的路径,即深度优先搜索算法也是一种全局的搜索算法,这样的深度优先搜索算法运用到未知迷宫搜救中是没有意义的。而本次实验中,深度优先搜索算法是以找到目标物为目的,没有剪枝的步骤,只要搜索到目标物,迷宫的搜索过程就成功退出。
1.3 A*算法
A*算法是人工智能中的一种搜索算法,是一种启发式搜索算法,它不需遍历所有节点,只是利用包含问题启发式信息的评价函数对节点进行排序(Node Ordering),使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价节点处于最短路线上的可能性的度量。A*算法中引入了评估函数,评估函数如下:
其中:n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。仿真实验中,我们为A*实现了三种启发式函数,如引言中所述,一种启发式函数为当前点到目标点的欧几里得距离评估,我们定义为A*(1);
即A*(1)算法的评估函数为:
其中启发式函数h1(i)为当前节点i到偏移目标点的欧几里得距离。
另一种启发式函数在第一种的启发式函数中增加了当前节点的父节点到目标点的欧几里得距离评估,我们定义为A*(2);
A*(2)算法的评估函数为:
j为当前节点的父节点,h2(i)为已评估出的当前节点i的父节点到偏移目标点的距离。
最后一种启发式函数是在第一种启发式函数的评估上加入了当前点到目标点的角度评估,我们定义为A*(3)。
A*(3)算法的评估函数为:
其中,为权重值,取ω1=0.55,ω2=0.45;θ为当前点到偏移目标点的直线与水平线的夹角,α为起始点到实际目标点的直线与水平线的夹角,角度如图2中标示;l为当前点坐标到实际目标点坐标的欧几里得距离,L为起始点到实际目标点坐标的欧几里得距离。
2 仿真实验分析
实验的迷宫环境设置如下图所示,将环境划分为一个一个的栅格,红色栅格为障碍物,白色栅格为通道,生成的10个迷宫均为Pefect迷宫,保证了整个迷宫中至少有一条从起点到目标点的通道并不会产生环路。起点坐标设为(0,0),目标点坐标设为(24,24)。
由于机器人在检测呼救信号时存在不准确因素(例如:传感器的精度,迷宫环境障碍物对声音的阻碍作用等),都会导致机器人在搜索时存在或多或少的误差,所以仿真实验中,为了比较真实的模拟现实搜救环境,我们对目标点做了偏差处理,处理方式如图2中所示。
其中,(xs,ys)为起始点坐标,(x,y)为机器人当前所在位置坐标,(xt',yt')为偏移目标点的坐标,(xt,yt)为实际目标点坐标:
为目标点产生的偏移误差:
其中,k为权重值,通过实验,取得k=40,l为当前点坐标到实际目标点坐标的欧几里得距离,L为起始点到实际目标点坐标的欧几里得距离,rand(-1,1)为随机数,随机数的取值范围为(-1,1)。
实验中,我们将三种A*算法分别在10个不同的Perfect迷宫中运行,统计结果如表1所示。
通过上表的结果分析可知,正如文献3中所述,加入了父节点评估的A*算法(即A*(2))在搜索时,提高了搜索速度;而在文献2中所述的提高搜索速度的优势在本次实验中没有很好的体现出来,这是因为,在本次实验中,我们加入了偏差值,对于A*(3)中的估价函数,不仅在距离上加入了偏差,同时在角度上也加入了偏差,从而使得A*(3)算法在本次搜索中没有优势。从表中我们还可以得出,带有启发式函数的A*算法要优于深度优先搜索算法。
仿真实验中,对于返回路径的优化,我们通过算法设定,让机器人每走过一个栅格都将该栅格的状态标记为“已访问”,被标记为“已访问”的栅格,机器人在搜索时就不会再走,除非遇到是死路的栅格。那么在算法中我们定义两个状态,一个状态是通过栅格的次数(count),另一个状态是栅格是否为分支。当机器人搜索到目标点后,返回时只需要走count为1或者栅格为分支(is Branch=true)的路线就是返回的最优路线,且不会走“冤枉路”。
3 结论
本文通过仿真实验比较了A*算法与深度优先搜索算法在未知迷宫中的搜索应用,仿真实验中还同时比较了三种带有不同启发式函数的A*算法的应用,通过仿真实验比较得出的结果是:总体来说,未知迷宫中,在仅知道目标点的大概位置的情况下,进行搜索时,A*算法要优于深度优先搜索算法,而A*算法在启发式函数不同的情况下,搜索产生的结果也是不同的,从上述仿真实验结果的比较中可以得出,A*(2)算法搜索路径的时间是最优的,其次是A*(1)和A*(3)算法。同时,从实物实验比较结果也可以得出,带有启发式函数的A*算法要优于深度优先搜索算法。深度优先搜索算法在未知迷宫中进行搜索时是盲目的,而A*算法在搜索过程中通过引入启发式信息来实现向目标节点移动的判别,无需遍历地图,使得计算复杂度相对较小,实现了快速、高效。但是,这也导致搜索的过程中排除了大量节点,而由于经验及实际问题的复杂性,引入启发信息的代价函数无法做到完全正确,这些被排除的节点可能就是最优路径的节点之一。
摘要：本文通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在标准迷宫中的应用,在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度。机器人搜索的目的是为了进行搜救,因此机器人应该要在尽量短的时间内搜索到目标物并将目标物带回。通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法。
关键词：迷宫搜索,深度优先搜索算法,A*算法
参考文献
[1]http://www.astrolog.org/labyrnth.htm.
[2]A.Francy Golda,S.Aridha,and D.Elakkiya,"AlgorithmicAgent for Effective Mobile Robot Navigation in anUnknown Environment."Intelligent Agent&Multi-AgentSystems,2009,IAMA 2009.
[3]Takayuki Goto,Takeshi Kosaka,and Hiroshi Noborio,"Onthe Heuristics of A*or A Algorithm in ITS and Robot Path-Planning,"Proceedings of the 2003 IEEE/RSJ InternationalConference on Intelligent Robots and Systems,pp.1159-1166,Oct,2003.
[4]史辉,曹闻,朱述龙,"A*算法的改进及其在路径规划中的应用"[J].测绘与空间地理信息,2009,32,6:208-211.
[5]张仁平,周庆忠,熊伟,"A*算法改进算法及其应用"[J].计算机系统应用,2009,98-100.
三分搜索算法 篇4
众所周知,在没有更多的关于元素组次序的信息时,要找出是否在元素组中的元素,搜索元素组中的所有元素是不可避免的。但当知道元素组按升(降)序排列时,人们往往采用分治法解决。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。根据分治法的分割原则,应把原问题分为多少个子问题才较适宜?每个子问题是否规模相同或怎样才为适当?这些问题一般很难予以肯定的回答。但人们从大量的实践中发现,在用分治法设计算法时,最好使问题的规模大致相同。即将一个问题分成大小相等的k个子问题来处理是行之有效的。许多问题可以取k=2。这种使问题规模大致相等的做法是出自一种平衡子问题的思想,它常常比子问题规模不等的做法要好。
给定已排序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。
二分搜索算法解决这一类问题的基本思想是将这n个元素分成大致相同的两部分,取a[(n-1)/2]与x比较。如果x=a[(n-1)/2],则找到x,算法终止。如果x<a[(n-1)/2],则只须在数组a的左半部继续搜索x。如果x>a[(n-1)/2],则只须在数组a的右半部继续搜索x。具体算法可描述如下[1]。
输入:n个元素的升序数组a[0:n-1]和元素x
输出: 如果x=a[j],1≤j≤n-1,则输出j,否则输出-1。
low←0; high←n-1;j←-1
while(low≤high)and(j=-1)
mid←[(low+high)/2]
if x=a[mid] then j←mid
else if x<a[mid] then high←mid-1
else low←mid+1
end while
return j
容易看出,每执行一次算法的while循环,待搜索数组的大小减少一半。 但在寻找的x大于或等于数组的最大元素时,算法总执行最大次数的比较,即算法并未充分利用最大数(或最小数)。因此,在最坏的情况下,while循环执行了O(log n),循环体内运算需要O(1)时间,整个算法在最坏情况下的计算时间复杂性为O(log n)。由此可见,对搜索元素大于或等于待搜索数组的最大元素时,二分搜索法的效率不如其他情况的效率。要解决这样问题的搜索效率,又兼顾搜索元素在靠近待搜索数组中间位置的搜索效率问题,可采用将待搜索数组大致三等分的搜索方法——三分搜索法来解决。
三分搜索法的基本思想与二分搜索法基本思想类似,将这n个元素分成大致相同的的三部分,取a[(n-1)/3]与x比较。如果x=a[(n-1)/3],则找到x,算法终止。如果x<a[(n-1)/3],则只须在数组a的左三分之一部分中继续搜索x。如果x>a[2(n-1)/3],则只须在数组a的右三分之一部分中继续搜索x。上述两种情况都不成立时,则在数组中间的三分之一部分中继续搜索x。具体算法可描述如下:
输入:n个元素的升序数组a[0:n-1]和元素x
输出:如果x=a[j],1≤j≤n-1,则输出j,否则输出-1。
low←0;high←n-1;j←-1
while(low≤high)and(j=-1)
mid1←[(low+(high-low)/3]
mid2←[(high-(high-low)/3]
if x=a[mid1] then j←mid1
else if x<a[mid1] then high←mid1-1
else if x=a[mid2] then j←mid2
else if x>a[mid2] then low←mid2+1
else low←mid1+1;high←mid2-1
end while
return j
这是从小到大方向上的搜索。容易看出,每执行一次算法的while循环,待搜索数组的大小减少三分之二。在寻找的x等于数组的中间元素时,算法总执行最大次数的比较。因此,在最坏的情况下,while循环执行了O(lg3n),循环体内运算需要O(2)时间,整个算法在最坏情况下的计算时间复杂性为O(lg3n)。对具体n值的数组进行搜索时,虽然三分搜索法在数据搜索时,循环次数减少了,但在一次循环中最坏情况下需要进行数据的两次比较,数据减少量在同等数据的比较量下不如二分搜索法,由于充分利用了待搜索数组的最大数和最小数,在搜索方向的选择上灵活性更强。这是因为对上述算法稍加变化可得从大到小方向上的三分法的搜索算法。
low←0;high←n-1;j←-1
while(low≤high)and(j=-1)
mid1←[low+(high-low)/3]
mid2←[high-(high-low)/3]
if x=a[mid2] then j←mid2
else if x>a[mid2] then low←mid2+1
else if x=a[mid1] then j←mid1
else if x<a[mid1] then high←mid1+1
else low←mid1+1;high←mid2-1
end while
return j
由此当对待搜索数组的结构有所了解,就可以根据搜索数的大体位置选择搜索方向,从而更快捷的搜索出该数在数组中的位置。该算法对某些数据库关于某些已排序字段进行搜索记录给出了一种新的启示。
上面的问题也可利用递归思路解决,其算法可描述如下。
int ternarysearch(int a[],int low,int high,int x)
if (high<low)
j=-1;
else
int mid1=low+(high-low)/3;
int mid2=high-(high-low)/3;
if(x=a[mid1])
j=mid1;
else if(x<a[mid1])
j=ternarysearch(a,low,mid1-1,x);
else if(x=mid2)
j=mid2;
else if(x>a[mid2])
j=ternarysearch(a,mid2+1,high,x);
else
j=ternarysearch(a,mid1+1,mid2-1,x);
return j
这是按数组元素从小到大方向上的三分搜索法的递归算法,同样也可给出从大到小方向上的三分搜索法的递归算法,不再赘述。
摘要：给出了利用最大数(或最小数)的排序元素组的三分搜索法,该方法具有编程简单且易于计算机实现等特点,也可看成是对二分搜索法的补充。
关键词：排序元素,搜索,三分搜索
参考文献
禁忌搜索算法评述 篇5
工程领域内存在大量的优化问题, 对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识, 属于局部优化算法。智能随机算法不依赖问题的性质, 按一定规则搜索解空间, 直到搜索到近似优解或最优解, 属于全局优化算法, 其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法 (Tabu Search, TS) 最早是由Glover在1986年提出, 它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制, 采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦 (破禁) 准则来释放一些被禁忌的优良状态, 以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法, 可以克服搜索过程易于早熟收敛的缺陷而达到全局优化[1]。
迄今为止, TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域, 并显示出极好的研究前景[2,3,4,5,6,7,8,9,11,12,13,14,15]。目前关于TS的研究主要分为对TS算法过程和关键步骤的改进, 用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。
禁忌搜索提出了一种基于智能记忆的框架, 在实际实现过程中可以根据问题的性质做有针对性的设计, 本文在给出禁忌搜索基本流程的基础上, 对如何设计算法中的关键步骤进行了有益的总结和分析。
2 禁忌搜索算法的基本流程
TS算法一般流程描述[1]:
(1) 设定算法参数, 产生初始解x, 置空禁忌表。
(2) 判断是否满足终止条件?若是, 则结束, 并输出结果;否则, 继续以下步骤。
(3) 利用当前解x的邻域结构产生邻域解, 并从中确定若干候选解。
(4) 对候选解判断是否满足藐视准则?若成立, 则用满足藐视准则的最佳状态y替代x成为新的当前解, 并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象, 同时用y替换“best so far”状态, 然后转步骤 (6) ;否则, 继续以下步骤。
(5) 判断候选解对应的各对象的禁忌情况, 选择候选解集中非禁忌对象对应的最佳状态为新的当前解, 同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。
(6) 转步骤 (2) 。
算法可用图1所示的流程图更为直观的描述。
3 禁忌搜索算法中的关键设计
3.1 编码及初始解的构造
禁忌搜索算法首先要对待求解的问题进行抽象, 分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略, 主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示[2], 十进制编码将问题的解用一个十进制串来表示[3], 实数编码将问题的解用一个实数来表示[4], 在某些组合优化问题中, 还经常使用混合编码[5]、0-1矩阵编码等。
禁忌搜索对初始解的依赖较大, 好的初始解往往会提高最终的优化效果。初始解的构造可以随机产生, 但效果往往不够理想, 通常是基于问题特征信息, 借助一些启发式方法产生, 以保证初始解的性能。
3.2 邻域移动、邻域解及邻域解规模
邻域移动, 相关文献也称作邻域操作、邻域结构、邻域变换等。禁忌搜索要想不断进行就要依赖邻域移动来不断拓展搜索空间, 邻域移动是在当前解的基础上, 按照特定的移动策略产生一定数目的新解, 这些新解被称为邻域解, 新解的数目称为邻域解规模。邻域移动的设计通常与问题有关, 如排列置换类组合优化问题, 常用的邻域移动方法是交换、插入、逆序等[3,6,7,8]。不同的移动将导致邻域解个数及其变化情况的不同, 进而影响搜索的质量和效率。在一些应用中为了取得好的搜索效果, 会根据搜索的进展情况动态改变邻域移动策略, 即变邻域移动[9]。邻域移动的设计策略既要保证变化的有效性还要保证变化的平滑性, 即产生的邻域解和当前解既有不同, 又不能差异太大。不同使搜索过程向前进行, 不能差异太大保证搜索是有序而非随机的搜索。邻域解的规模, 也并不总是取可产生邻域解个数的上限, 可以根据需要和经验设定成小于上限的值, 以提高搜索的运行效率。
3.3 解的评价函数
解的评价函数, 相关文献又称其为适应值函数、适配值函数或适应度函数。对于禁忌搜索空间中的解, 通过评价函数来计算其对应的评价函数值, 评价函数值的大小代表了解的优劣程度。根据问题的特性, 可能评价函数值越大越好, 反之也可能越小越好。依据数学方法, 两种目标可以等价转换。直接把优化目标作为评价函数是一种简单、直观的方法, 同时任何与优化目标等价的变换函数也可以作为评价函数。有时, 目标函数的计算困难或是耗时较多, 则可以取体现问题目标的特征值来替代计算, 但必须要保证特征值与问题目标有一致的最优性。
与遗传算法的评价函数类似, 在求解带有约束的优化问题时, 可以将解违反约束的情况作为惩罚因子加入评价函数, 从而规避传统启发式方法中对于约束的复杂处理。基本形式如公式 (1) 。
其中, P (Rj, x) 为第j个约束的惩罚值, 当解满足约束时, 惩罚值为0。关于评价函数的设计详见文献[10]。
3.4 禁忌表、禁忌对象、禁忌长度、候选解及禁忌频率
禁忌表是用来存放禁忌对象的一个容器, 被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索, 可见禁忌表模拟了人的记忆机制, 防止搜索陷入局部最优, 进而探索更多的搜索空间。禁忌表可以使用数组、队列、栈、链表等顺序结构实现, 每个顺序结构的元素定义根据具体问题确定。
禁忌对象就是放入禁忌表中的元素, 归纳而言, 禁忌对象通常可选取状态 (解的编码) 本身或状态分量或适配值的变化等, 禁忌范围依次扩大[1]。其中选取状态本身易于理解, 也最为常用, 禁忌范围最小。
禁忌长度就是每个禁忌对象在禁忌表中的生存时间, 也称为禁忌对象的任期。当一个禁忌对象加入禁忌表时, 设置其任期为禁忌长度值, 搜索过程每迭代一次, 禁忌表中的各禁忌对象的任期自动减1, 当某一禁忌对象任期为0时, 将其从禁忌表中删除。任期不为0的禁忌对象处于禁忌状态, 不能被搜索过程选为新解。
候选解是当前解邻域解集的一个子集。搜索中为了减少搜索的代价 (包括空间和时间) , 要求禁忌长度和候选解集尽量小, 但禁忌长度过小将使搜索无法跳出局部最小, 候选解集过小将使搜索早熟收敛。候选解集的大小常根据问题特性和对算法的要求确定, 禁忌长度的选取则主要有静态和动态两种方法。静态方法是指在搜索过程中, 禁忌长度是一个固定值, 比如, 其中n为问题维数或规模。动态方法是指在搜索过程中, 禁忌长度也是动态变化的, 当算法搜索能力较强时, 可以增大禁忌长度从而延续当前的搜索能力, 并避免搜索陷入局部优解, 反之亦然。
禁忌频率记录每个禁忌对象出现在禁忌表中的次数, 以此作为搜索过程的重要参考, 如若某个对象出现频繁, 则可以增加禁忌长度来避免循环。此外可以把某对象的禁忌频率作为评价解的因素加入评价函数来指导搜索过程。
3.5 特赦准则
特赦准则, 相关文献也称为藐视准则、破禁准则[11]、释放准则等。特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解 (或状态) 被禁时, 能够释放特定解 (或状态) , 从而实现高效的全局优化搜索。
3.6 终止准则
终止准则也称停止准则, 即算法在何条件下停止搜索过程。实际应用中无法使用在禁忌长度充分大的条件下实现状态空间的遍历这一理论收敛条件, 往往使用如下近似终止 (收敛) 准则。
(1) 算法迭代次数达到指定最大次数停止[8,11]。
(2) 最优解的目标函数值小于指定误差。
(3) 最优解的禁忌频率达到指定值。
4 总结和展望
本文简述了禁忌搜索算法的发展、特点及应用, 给出了基本禁忌搜索算法实现的流程, 对禁忌搜索设计过程中的关键步骤进行了分析和总结, 为推广禁忌搜索算法在优化领域的应用有一定意义。
今后关于禁忌搜索算法的研究热点主要有以下几个方面。
(1) 与其他优化算法结合, 如与传统启发式算法、遗传算法、模拟退火算法、粒子群算法、神经网络算法、蚁群算法、混沌算法等结合, 构成更新型的混合优化算法[2,4,5,12,13,14,15]。
(2) 为推广禁忌搜索算法在超大规模优化领域中的应用, 突破禁忌搜索的串行性限制, 研究并行禁忌搜索算法。包括基于问题空间分解的并行策略和基于多禁忌搜索任务的并行策略[1]。
(3) 对禁忌搜索算法本身的关键步骤进行改良设计。如根据禁忌频率信息在算法中增加集中搜索和分散搜索, 分别实现优良区域的重点搜索和搜索范围的扩展。
(4) 探索禁忌搜索算法适于应用的新的优化领域。
和声搜索算法参数研究 篇6
在音乐创作过程中, 乐师们凭借自己的记忆, 通过反复调整乐队中各乐器的音调, 最终达到一个美妙和声的过程。Geem[1]等人受这一现象启发, 提出一种新型的群智能优化算法——和声搜索算法, 已经在函数优化[2,3]和调度[4,5,6]等问题中表现出了优势。此算法结构简单, 参数少, 通过对参数的分析及调整, 利用多维函数进行仿真实验, 最终找出最优参数组合。
1 和声搜索算法 (Harmony Search, HS)
HS是Geem等通过类比音乐和最优化问题的相似性而提出的一种现代启发式群智能算法。将乐器的和声Ri (i=1, 2, …n) 类比于函数第i分量的解向量Xi (i=1, 2, …, n) , 评价对应解的函数值。HMS为和声记忆库的大小, 即和声库中解向量的个数。和声库HM=[X1, X2…, XHMS], 其中, 每个解向量由n分量组成Xi=[xi1, xi2, …, xin], i=1, 2, …HMSHMCR是产生新解时从和声库中保留解分量的概率;PAR则为记忆扰动概率。
1.1 初始化和声库
为了保证初始解的质量和多样性, 并保证优化结果具有一定的代表性, 初始种群在函数定义域内应均匀分布, 产生方式如下:
undefined
其中r为 (0, 1) 内产生的随机数, xi∈[LBi, UBi]
1.2 新解产生
候选解X'=[x'1, x'2, …, x'n] 中的每个分量j=1, 2, …, n, 产生方式如下:
(1) 和声库的学习。
undefined
当产生的随机数小于和声记忆概率时, 从第j列分量随机选取一个, 否则就在解取值范围中随机产生一个。
(2) 候选解分量微调。如新产生的候选解分量来自于和声记忆库, 若随机数小于PAR就对其进行微调, 其中α为微调变量。
undefined
候选解评价值小于和声库中最差解则替换之, 否则和声库不更新。
与其它算法不同, 和声搜索算法候选解产生原理是多个个体合作完成, 并通过微调机制增加算法局部寻优能力。
2 参数设计
2.1 HMS设计
HMS是影响算法执行性能和优化效率的重要因素之一, 决定了算法的全局搜索能力。若值太小则不能提供足够的采样点从而导致算法优化性能较差;反之, 取值越大, 搜索全局最优解的能力越强, 但是其值也不能过大, 太大值反而会增加计算量而导致收敛时间较长。因此, 采用合适的和声库规模有利于提高算法的收敛速度和解的质量。
2.2 HMCR设计
和声库记忆选择概率是影响优化结果的一个关键因素。HMCR值较大时, 解向量从和声库中进行选择的几率较高, 更好地继承了和声库的信息, 当HMCR较小时, 新解产生随机数的概率高, 增加了和声库的多样性。
2.3 PAR设计
PAR用于控制解的扰动概率。若PAR太大, 种群中的解以较大概率进行扰动, 容易使较好的解被破坏掉;若PAR太小, 种群中的解以很小的概率参与扰动, 则会使搜索停滞不前, 搜索速度减慢, 和声库失去多样性。
3 仿真实验与数据分析
为了对几个参数的设置进行比较, 采用了一些Benchmark问题进行计算, 相关函数如下:
(1) Sphere Model
undefined
(2) Schwefel’s problem
undefined
(3) Step function
undefined
(4) Rosenbrock function
undefined
采用C++编程语言, 在处理器为Intel (R) Core (TM) i3 2GHz、内存为512M的PC机上进行程序测试。每个函数进行30次仿真, 每次仿真的迭代次数为10 000, 求其平均值。
HMCR的值为0.1～0.9, HMS=5, PAR=0.3, 得到的结果如表1所示。
从表1可知, 针对如上4个函数, HMCR越大, 效果越好, 因此对其进行进一步实验, 细化HMCR的取值, 范围为0.91～0.99, 所得结果如表2所示。
从表2 可知, 通过对以上4个函数的测试, HMCR较理想的取值为0.96和0.97。
PAR参数在0.1～0.9范围内, HMCR=0.97, HMS=5时对4个函数结果影响如表3所示。
由表3可知, 综合几个函数进行考虑, PAR的取值为0.5时得到的结果最好, 因为参数PAR的变化对函数结果的影响不是特别大, 因此不进行细化研究。
HMCR=0.97, PAR=0.5, 固定这两个参数, 对HMS进行研究, HMS的取值分别设为5、10、20、30、50。研究其对函数结果的影响, 如表4所示。
由表4可知, HMS=5时, 函数结果得到最优值。
HMS、HMCR、PAR在算法中不仅各尽其责, 而且相互影响、紧密联系, 共同影响着算法的性能。只有选择较好的组合, 才能更好地指导算法。从各个参数中选择较好值进行组合, 得到结果如表5所示。
从表5可以看出, 针对文中用到的4个基准函数, 参数组合0.97、0.5、5为最优参数设计组合, 保证了算法具有较好的全局收敛性能, 同时具有较快的收敛速度, 能有效避免算法陷入局部最优。
4结语
HS算法是一种有效的群智能优化算法, 通过参数研究找出最优参数组合, 能更有效地解决函数优化和组合优化问题, 本文通过列举法得到了较好的参数组合。当然, 针对不同的问题还需要作进一步调整, 本文为以后HS的研究奠定了基础。
摘要：合适的参数能够提高和声搜索算法的性能和收敛速度。详细介绍了和声搜索算法的流程, 并总结了每个参数对算法的作用及参数变化对算法的影响。针对如何选取参数才能达到提高算法性能的目的, 通过参数调整的方法, 利用4个基准函数对算法进行仿真实验, 实验结果表明, 较高的HMCR、PAR和HMS取较小的值能使函数得到较优值。
关键词：和声搜索算法,基准函数,参数调整,仿真实验
参考文献
[1]GEEM Z W, KIM J H, LOGANATHAN G V.A new heuristic op-timazation algorithm:harmony search[J].Simulation, 2001 (2) .
[2]GEEM Z, KIM J, LOGANATHAN G.Harmony search optimiza-tion:application to pipe network design[J].International Journal ofModel Simulation, 2002 (2) .
[3]张凤荣, 潘全科, 庞荣波, 等.基于和声退火算法的多维函数优化[J].计算机应用研究, 2010 (3) .
[4]韩红燕, 潘全科.求解批量流水线调度问题的改进和声搜索算法[J].计算机工程, 2011 (6) .
[5]李俊青, 王玉亭, 潘全科, 等.混合离散和声搜索算法求解旅行商问题[J].微电子学与计算机, 2009 (3)
博弈及其常用搜索算法初探 篇7
搜索算法是人工智能的一个基本问题。算法的好坏直接关系到智能系统的性能与效率, 也是人工智能领域核心问题之一。搜索就是根据实际的问题, 在推理过程中发掘可利用的知识, 进而找到一条代价较小的解决问题的途径。搜索有两种形式:盲目搜索和启发式搜索。盲目搜索又称为无信息搜索, 仅仅根据预先制定的策略进行搜索, 在搜索中获得的新知识不用来改进策略。启发式搜索在搜索过程中, 需要对每一个搜索位置进行评估, 从而得到最好的位置再进行下一步的搜索, 直到目标达成。在人机博弈过程中, 博弈树搜索算法是核心, 它与规则及估值构成一个完整的系统。
2 博弈树
博弈是一类富有智能行为的竞争活动, 如下棋、打牌、战争等, 是启发式搜索的一个重要应用领域。最简单的一种博弈是双人完备信息博弈。双人完备信息博弈指两位选手对垒, 轮流走步, 每一方不仅知道对方已经走过的棋步, 而且还能估计出对方未来的走步, 对弈的结果是一方赢, 另一方输, 或者双方和局。这里就以双人完备信息博弈作为主要的对象, 为考虑复杂的博弈打下基础。
设博弈的双方中一方为甲方, 另一方为乙方。在博弈过程中, 某一方当前有多个行动方案可供选择时, 他总是挑选对自己最为有利而对对方最为不利的行动方案。此时, 如果我们站在甲方的立场上, 则可供甲方选择的若干行动方案之间是“或”的关系, 因为这是主动权在甲方手里, 他可以选择这些行动方案中的任何一个行动方案。但是, 若乙方也有若干个可供选择的行动方案, 则对甲方来说这些行动方案之间是“与”的关系, 因为乙方走棋时主动权在乙方手里, 这些可供选择的行动方案中的任何一个都可能被乙方选中, 甲方必须考虑对自己最不利的情况的发生。这个博弈的过程用图表示出来, 得到的就是一颗“与/或”树, 如图1所示。“与/或”树始终是站在某一方的立场上得出的, 对于不同的走棋方“与/或”树不同。描述博弈过程的“与/或”树就是博弈树 (game tree) 。图1中方形节点代表轮到甲方走棋的棋局, 圆形节点代表轮到乙方走棋的棋局。
博弈树的每个结点代表一个问题, 根结点代表初始问题。具有儿子的结点称为非端结点, 每个非端结点或具有与儿子, 或者具有或儿子。如果任何一个或儿子代表的问题得到解决, 则具有或儿子的结点代表的问题就得到解决;如果所有与儿子代表的问题都得到解决, 则具有与儿子的结点代表的问题得到解决。没有儿子的节点称为端结点, 每个端节点代表了一个或者可解或者不可解的基本问题。博弈树搜索是寻找一棵在某种条件下最好的解树。
3 算法
3.1 极大极小法
极大极小算法是为博弈中的一方寻找一个最优行动方案的方法。为了找到当前的最优行动方案, 需要对各个行动方案可能产生的后果进行比较。具体地说, 就是要考虑每一方案实施后对方可能采取的所有行动, 并计算可能的分值。为计算分值, 需要定义一个估值函数, 用来估算当前博弈树叶节点的分值。当叶节点的估值计算出来后, 再推算出父节点的分值。推算的方法是, 对于“或”节点, 选其子节点中一个最大的分值作为父节点的分值, 这是为了使自己在可供选择的方案中选出一个对自己最有利的方案;对于“与”节点, 选其子节点中一个最小分值作为父节点的分值, 即考虑最坏的情况。如果一个行动方案获得较大的倒推值, 则它就是当前最好的行动方案。图1给出了计算倒推值得实例。详细描述如下:假使最后一层叶子节点为终节点, 并且已经计算估值函数值如图所示。由于最后一层为或节点, 其父节点为与节点, 那么在父节点进行求值时, 取其子节点中的最大值为其值, 对节点E来说, 其子节点K、L中最大值为20, 故E取值20。对节点B来说, 其为或节点, 其子节点E、F中最小值为19, 故其取值为19。通常将取极大值的一方称为Max, 另一方称为Min。
3.2 剪枝技术
用极大极小算法求倒推值的过程中, 存在着两种明显的冗余现象。第一种现象是极大值冗余, 如图2 (a) 所示的博弈树, 我们要用极大极小值算法找出极大值节点A的最佳着法。先对A的第一个子节点B进行搜索, 得出B的各子节点的评价分别是20、25、19和30, 那么B的值为19。节点A的值应是节点B和节点C的值中之较大者。现在已知节点B的值大于节点D的值。由于节点C的值应是它的诸子节点的值中之极小者, 此极小值一定小于等于节点D的值, 因此也一定小于节点B的值, 这表明继续搜索节点C的其他诸子节点E、F...已没有意义, 它们不能做任何贡献, 于是可以把以节点C为根的子树全部剪去。这种优化称为α剪枝。图2 (b) 是与极大值冗余对偶的现象, 称为极小值冗余。节点A的值应是节点B和节点C的值中之较小者。现在已知节点B的值小于节点D的值。由于节点C的值应是它的诸子节点的值中之极大者, 此极大值一定大于等于节点D的值, 因此也一定大于节点B的值, 这表明继续搜索节点C的其他诸子节点已没有意义, 可以把节点C为根的子树全部剪去, 这种优化称为β剪枝。
3.3静态估值函数与算法
对于博弈树求解有了良好的搜索算法还只是问题的一个方面, 问题的另一个方面就是静态估值函数。只有有了良好的静态估值函数才能保证较快地找到正解。而静态估值函数是对博弈的综合评估, 该函数的好坏直接决定解题能力强与弱。通常一个优秀的选手总有一个良好的对棋局的判断能力, 能够协调各棋子的关系、取舍, 有机地组织各棋子的进攻步调, 控制棋局的发展。如果要把这一整套的思维物化成一个数值函数来评估, 本身就是一个相当复杂的问题。有时一个损失极大的走步, 在若干步之后体现出强大的优越性, 有时一个看似取得明显实利的走步, 却在对方步步紧逼之下变得极为不利。怎样评估一个棋局的优越性是值得思考的问题。然而无论怎样设计静态估值函数, 都难免有山脊、平原和小丘现象出现, 这些现象的产生是问题本身所具有的, 估值函数无法克服, 主要通过搜索算法来解决。
4总结
本文着重讨论了什么叫博弈, 及博弈问题的两种常用解法, 并对静态估值函数进行了定性的分析。在实际应用中, 应综合考虑算法及估值函数的设计, 这样才能更好地解决博弈问题。
参考文献
[1]Stuart Russell, Peter Norvig著, 姜哲、金奕江、张敏、杨磊, 等译.人工智能——一种现代方法 (第二版) [M], 北京:人民邮电出版社, 2004.
[2]肖齐英, 王正志.博弈树搜索与静态估值函数[J], 计算机应用研究, 1997年第4期.
[3]李红, 吴粉侠, 刘小豫.博弈树搜索算法研究[J], 长春工程学院学报 (自然科学版) , 2007年第8卷第2期.
[4]孙伟, 马绍汉.博弈树搜索算法设计和分析[J], 计算机学报, 1993年5月.
[5]杨涛, 何志均, 俞瑞钊.博弈树函数及其计算优化[J], 计算机学报, 1988年2月.
[6]岳金朋, 冯速.博弈树搜索算法概述[J], 计算机系统应用, 2009年第9期.
[7]张聪品, 刘春红, 徐久成.博弈树启发式搜索的α-β剪枝技术研究[J], 计算机工程与应用, 2008.