2005年11月17日

博弈搜索

诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种,我们讨论最简单的"二人零和、全信息、非偶然"博弈,其特征如下:
  (1) 对垒的MAXMIN双方轮流采取行动,博弈的结果只有三种情况:MAX方胜,MIN方败;MIN方胜,MAX方败;和局。
  (2) 在对垒过程中,任何一方都了解当前的格局及过去的历史。
  (3) 任何一方在采取行动前都要根据当前的实际情况,进行得失分析,选取对自已为最有利而对对方最为不利的对策,不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。
  在博弈过程中,任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时,他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时,如果我们站在MAX方的立场上,则可供MAX方选择的若干行动方案之间是""关系,因为主动权操在MAX方手里,他或者选择这个行动方案,或者选择另一个行动方案,完全由MAX方自已决定。当MAX方选取任一方案走了一步后,MIN方也有若干个可供选择的行动方案,此时这些行动方案对MAX方来说它们之间则是""关系,因为这时主动权操在MIN方手里,这些可供选择的行动方案中的任何一个都可能被MIN方选中,MAX方必须应付每一种情况的发生。
  这样,如果站在某一方(MAX方,即MAX要取胜),把上述博弈过程用图表示出来,则得到的是一棵"与或树"。描述博弈过程的与或树称为博弈树,它有如下特点:
  (1) 博弈的初始格局是初始节点。
  (2) 在博弈树中,""节点和""节点是逐层交替出现的。自己一方扩展的节点之间是""关系,对方扩展的节点之间是""关系。双方轮流地扩展节点。
  (3) 所有自己一方获胜的终局都是本原问题,相应的节点是可解节点;所有使对方获胜的终局都认为是不可解节点。
  我们假定MAX先走,处于奇数深度级的节点都对应下一步由MAX走,这些节点称为MAX节点,相应地偶数级为MIN节点。

在二人博弈问题中,为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案,就需要对当前的情况以及将要发生的情况进行分析,通过某搜索算法从中选出最优的走步。在博弈问题中,每一个格局可供选择的行动方案都有很多,因此会生成十分庞大的博弈树,如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的,比如曾有人估计,西洋跳棋完整的博弈树约有1040个节点。
  最常使用的分析方法是极小极大分析法。其基本思想或算法是:
  (1) 设博弈的双方中一方为MAX,另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。
  (2) 为了找到当前的最优行动方案,需要对各个可能的方案所产生的后果进行比较,具体地说,就是要考虑每一方案实施后对方可能采取的所有行动,并计算可能的得分。
  (3) 为计算得分,需要根据问题的特性信息定义一个估价函数,用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。
  (4) 当端节点的估值计算出来后,再推算出父节点的得分,推算的方法是:对“或”节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案;对“与”节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。
  (5) 如果一个行动方案能获得较大的倒推值,则它就是当前最好的行动方案。
  在博弈问题中,每一个格局可供选择的行动方案都有很多,因此会生成十分庞大的博弈树。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树,然后进行极小极大分析,找出当前最好的行动方案。在此之后,再在已选定的分支上扩展一定深度,再选最好的行动方案。如此进行下去,直到取得胜败的结果为止,至于每次生成博弈树的深度,当然是越大越好,但由于受到计算机存储空间的限制,只好根据实际情况而定。

  首先分析极小极大分析法效率,上述的极小极大分析法,实际是先生成一棵博弈树,然后再计算其倒推值,至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。
  α-β剪枝技术的基本思想或算法是,边生成博弈树边计算评估各节点的倒推值,并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点,即相当于剪去了博弈树上的一些分枝,从而节约了机器开销,提高了搜索效率。具体的剪枝方法如下:
  (1) 对于一个与节点MIN,若能估计出其倒推值的上确界β,并且这个β值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β,则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 )。这一过程称为α剪枝。
  (2) 对于一个或节点MAX,若能估计出其倒推值的下确界α,并且这个α值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界β,即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 )。这一过程称为β剪枝。
  从算法中看到:
    (1) MAX节点(包括起始节点)的α值永不减少;
    (2) MIN节点(包括起始节点)的β值永不增加。
  在搜索期间,α和β值的计算如下:
    (1) 一个MAX节点的α值等于其后继节点当前最大的最终倒推值。
    (2) 一个MIN节点的β值等于其后继节点当前最小的最终倒推值。

 下面让我们对α-β剪枝技术的搜索效率再作一些分析。要进行α-β修剪,必须至少使某一部分的搜索树生长到最大深度,因为α和β值必须以端节点的静态估值为依据。因此采用α-β剪枝技术通常都要使用某种深度优先的搜索方法。而且在一次搜索期间修剪的枝数取决于早期的α、β值与最终倒推值之间的近似程度。
  起始节点的最终倒推值等于某个端节点的静态估值。如果在深度优先搜索过程中第一次就遇到这个端节点,则修剪枝数最大。当前修剪枝数最大时,需要生成和估计的端节点数就最少。
   α-β剪枝技术的搜索效率还可通过数学公式进行估算,

前言
"搬运工"是一个十分流行的单人智力游戏,玩家的任务是在一个仓库中操纵一个搬运工人
将N个相同的箱子推到N个相同的目的地。不清楚规则不要紧,玩一玩附件里的SokoMind就
知道了。我在里面加上了标准的测试关卡90关,幼儿关卡61关和文曲星170关,在以后的介
绍中,我们就用这些关来测试我们的程序,因此我建议你自己先试一试,看看你能过多少
关:)
因为本文内容不算少,在这里我先给大家提供一个小小的阅读建议。初学的朋友或者不知
道IDA*算法的朋友一定要从第一章开始阅读并弄懂,因为它是全文的基础。第二章很好懂
,大家只需要做一个了解,知道搬运工问题的难点在哪里,为什么我们选择了IDA*算法。
急于看程序的朋友可以先看看第三章,我们的第一个版本S4-Baby诞生了,接着是一系列的
改进措施,喜欢人工智能的朋友不妨认真看看,也许会找到灵感哦!最后是总结,和第一
章一样的重要,不要错过了。
我假定本文的读者已经对相关知识有一定了解,所以一般不给出很严格的定义或者论证,
只是粗略的提一下,语言尽量做到通俗易懂。但由于我的水平实在有限,错误之处一定不
少,恳请大家批评指正:)

一 状态空间搜索基本知识
1.状态空间(state space)
对于一个实际的问题,我们可以把它进行一定的抽象。通俗的说,状态(state)是对问题在
某一时刻的进展情况的数学描述,状态转移(state-transition)就是问题从一种状态转移
到另一种(或几种)状态的操作。如果只有一个智能体(Agent)可以实施这种状态转移,则
我们的目的是单一的,也就是从确定的起始状态(start state)经过一系列状态转移而到达
一个(或多个)目标状态(goal state)。
如果不止一个智能体可以操纵状态转移(例如下棋),那么它们可能会朝不同的,甚至是对
立的目标进行状态转移。这样的题目不在本文讨论范围之内。
我们知道,搜索的过程实际是在遍历一个隐式图,它的结点是所有的状态,有向边对应于
状态转移。一个可行解就是一条从起始结点出发到目标状态集中任意一个结点的路径。这
个图称为状态空间(state space),这样的搜索就是状态空间搜索(Single-Agent Search)
2.盲目搜索(Uninformed Search)
盲目搜索主要包括以下几种:
纯随机搜索(Random Generation and Random Walk)
听起来比较"傻",但是当深度很大,可行解比较多,解的深度又不重要的时候还是有用的
,而且改进后的随机搜索可以对付解分布比较有规律(相对密集或平均,或按黄金分割比
例分布等)的题目。一个典型的例子是:你在慌乱中找东西的时候,往往都是进行随机搜
索。
广度优先搜索(BFS)和深度优先搜索(DFS)
大家都很熟悉它们的时间效率,空间效率和特点了吧。广度优先搜索的例子是你的眼镜掉
在地上以后,你趴在地板上找:)- 你总是先摸最接近你的地方,如果没有,在摸远一点
的地方…深度优先搜索的典型例子是走迷宫。它们还有逆向和双向的搜索方式,但是不再
本文讨论范围之内。
重复式搜索
这些搜索通过对搜索树扩展式做一些限制,用逐步放宽条件的方式进行重复搜索。这些方
法包括:
重复式深度优先(Iterative Deepening)
限制搜索树的最大深度Dmax,然后进行搜索。如果没有解就加大Dmax再搜索。虽然这样进行
了很多重复工作,但是因为搜索的工作量与深度成指数关系,因此上一次(重复的)工作
量比起当前的搜索量来是比较小的。这种方法适合搜索树总的来说又宽又深,但是可行解
却不是很深的题目(一般的深度优先可能陷入很深的又没有解的地方,广度优先的话空间
又不够)
重复式广度优先(Iterative Broadening)
它限制的是从一个结点扩展出来的子节点的最大值Bmax,但是因为优点不是很明显,应用并
不多,研究得也比较少。
柱型搜索(Beam Search)
它限制的是每层搜索树节点总数的最大值Wmax。显然这样搜索树大小与深度成正比,但是
可能错过很接近起点的解,而增加Wmax的时候保留哪些节点,Wmax增加多少是当前正在研
究的问题。
3.启发式搜索(Informed Search)
我们觉得一些问题很有"想头",主要是因为启发信息比较多,思考起来容易入手,但是却
不容易找到解。我们不愿意手工一个一个盲目的试验,同样也不愿意我们的程序机械的搜
索。也就是说,我们希望尽可能的挖掘题目自身的特点,让搜索智能化。下面介绍的启发
式搜索就是这样的一种智能化搜索方法。
在刚才的那些算法中,我们没有利用状态本身的信息,只是利用了状态转移来进行搜索。
事实上,我们自己在解决问题的时候常常会估计状态离目标到底有多接近,进而对多种方
案进行选择。把这种方法用到搜索中来,我们可以用一个状态的估价函数来估计它到目标
状态的距离。这个估价函数是和问题息息相关的,体现了一定的智能。为了以后叙述方便
,我们先介绍一些记号:
S 问题的任何一种状态
H*(s) s到目标的实际(最短)距离 - 可惜事先不知道:)
H(s) s的启发函数 - s到目标距离的下界,也就是h(s)<=h*(s),如果h函数对任意状态s1和
s2,还满足h(s1)<=h(s2)+c(s1,s2)(其中c(s1,s2)代表状态s1转移到s2的代价),也就是状
态转移时,下界h的减少值最多等于状态转移的实际代价,我们说h函数是相容(consisten
t)的。(其实就是要求h不能减少得太快)
G(s) 到达s状态之前的代价,一般就采用s在搜索树中的深度。
F(s) s的估价函数,也就是到达目标的总代价的估计。直观上,应该
有f(s)=g(s)+h(s),即已经付出的和将要付出的代价之和。如果g
是相容的,对于s1和它的后辈节点,有h(s1)<=h(s2)+c(s1,s2)
两边同时加上g(s1),有h(s1)+g(s1)<=h(s2)+g(s1)+c(s1,s2),也就是
f(s1)<=f(s2)。因此f函数单调递增。
表1   启发式搜索用到的符号
贪心搜索(Best-First Search)
象广度优先搜索一样用一个队列储存待扩展,但是按照h函数值从小到大排序(其实就是优
先队列)。显然由于h估计的不精确性,贪心搜索不能保证得到的第一个解最优,而且可能
很久都找不到一个解。
A*算法
和贪心搜索很类似,不过是按照f函数值进行排序。但是这样会多出一个问题:新生成的状
态可能已经遇到过了的。为什么会这样呢?由于贪心搜索是按照h函数值排序,而h只与状
态有关,因此不会出现重复,而f值不仅状态有关,还与状态转移到s的方式有关,因此可
能出现同一个状态有不同的f值。解决方式也很简单,如果新状态s1与已经遇到的状态s2相
同,保留f值比较小的一个就可以了。(如果s2是待扩展结点,是有可能出现f(s2)>f(s1)的
情况的,只有已扩展结点才保证f值递增)。A*算法保证得到最优解,但是所用的空间是很
大的,难以适应我们的搬运工问题。
IDA*算法
   既然A*算法存在空间问题,那么我们能不能借用深度优先搜索的空间优势,用重复式搜
索的方式来缓解危机呢?经过研究,Korf于1985年提出了一个Iternative Deepening A*(
IDA*)算法,比较好的解决了这一问题。一开始,我们把深度最大值Dmax设为起始结点的h
值,开始进行深度优先搜索,忽略所有f值大于Dmax的结点,减少了很多搜索量。如果没有
解,再加大Dmax的值,直到找到一个解。容易证明这个解一定是最优的。由于改成了深度
优先的方式,与A*比较起来,IDA*更加实用:
1. 不需要判重,不需要排序,只用栈就可以了。操作简单。
2. 空间需求大大减少,与搜索树大小成对数关系。
其他的启发式搜索
这些方法包括深度优先+最优剪枝式的A*,双向A*,但是由于很不成熟或者用处并不大,这

里就不介绍了。A*算法有一个加权的形式,由于在搬运工问题中效果不明显,这里从略。

二 搬运工问题及其特点
在对状态空间搜索算法有一定了解之后,我们来看看我们的搬运工问题。究竟用什么方法
比较好呢?让我们先来看看该问题的特点。
1. 搬运工问题
我们在前面已经介绍过搬运工问题,这里我只是想提一些和解题有关的注意事项。首先,
我们考虑的搬运工问题的地图规模最大是20*20,这已经可以满足大部分关卡了。为了以后
讨论方便,我们把地图加以编号。从左往右各列称为A,B,C…,而从上往下各行叫a,b,c
…。而由于不推箱子时的走路并不重要,我们
在记录解的时候忽略了人的位置和移动,只记录箱子的移动。人的动作很容易根据箱子的
动作推出来。下面是包含解答的标准关卡第一关。

呵呵,怎么样,第一关都要那么多步啊…以后的各关,可是越来越难。
2. 搬运工问题的特点
我在前言里吹了这么半天,我想你即使以前没有玩,现在也已经玩过了吧:)。
有什么感觉呢?是不是变化太多了,不好把握?不仅人不好把握,连编程序也变得困难了
很多。我们不妨拿它与经典的8数码问题作一个比较。
1.死锁!
初学者很快就会学到什么是死锁 - 一旦他(她)把一个箱子推到角上。显然,这样的布局
再继续玩下去是没戏了,不管以后怎么推都不可能把这个箱子推离那个角。不少玩家都总
结了不少死锁的经验,但是要比较系统的解决这个问题并不是一件容易的事。我们将用整
整一章(其实也不长啦)的篇幅来分析这个问题。

典型的死锁。想一想,为什么:)我们再看一下8数码问题。它没有死锁,因为每一步都是
可逆的。在这一点上,搬运工问题要令人头疼得多了。
容易看出,这样的状态空间不是无向图,而是有向图。
2.状态空间。
8数码问题每次最多有4中移动方法,最多的步数也只有几十步。而搬运工问题呢?困难一
点的关卡可以是一步有100多种选择,整个解答包括600多次推箱子动作。分支因子和解答
树深度都这么大,状态空间自然就非同小可了。
3.下界估计
在启发式搜索中,我们需要计算h值,也就是需要对下界进行估计。8数码问题有很多不错
的下界函数(如"离家"距离和),但是搬运工问题又怎么样呢?我们不能直接计算"离家"
距离,因为谁的家是哪儿都不清楚。很自然,我们可以做一个二分图的最佳匹配,但是这
个下界怎么样呢?
a.准确性
对于A*及其变种来说,下界与实际代价越接近,一般来说算法效率就越高。我们这个最佳
匹配只是"理想情况",但是事实上,在很多情况下箱子相互制约,不得已离开目标路线来
为其他箱子腾位置的事情是非常普遍的。例如我们的标准关卡第50关,有的箱子需要从目
标格子穿过并离开它来为其它箱子让路。我们的下界函数返回值是100,但是目前的最好结
果是370。多么大的差别!
b.效率
由于下界函数是一个调用非常频繁的函数,其效率不容忽视。最佳匹配的时间渐进复杂度
大约是O(N^3),比8数码的下界函数不知大了多少…我们将会在后面给出一些改进方法,但
是其本质不会改变。
3. 如何解决搬运工问题
已经有人证明了搬运工问题是NP-Hard,看来我们还是考虑搜索吧。回想一下上一节提到过
的状态空间搜索,用哪一种比较好呢?
既然是智力游戏,可用的启发式信息是非常丰富了,我们不仅是要用,而且要用得尽量充
分,所以应该用启发式搜索。而前面已经提到了,搬运工问题的状态空间是非常大的,A*是
没有办法了,因此我们选择了IDA*算法:实现简单,空间需求也少。
既然搬运工问题这么难,为什么有那么多人都解决了相当数量的关卡呢(标准的90N年以前
就被人们模透了)。因为人聪明嘛。他们会预测,会安排,会学习,有直觉的帮助,还有
一定的冒险精神。他们(也包括我啦,呵呵)常用的是一些"高层次"的解题策略,既有效
,又灵活。(Srbga:想学吗? Readers:当然想!!)可惜这些策略不是那么简单易学,也不是
很有规律的。在后面的章节中,我将尽力模仿人的思维方式给我们的程序加入尽量多的智
能。

三 用IDA*算法解搬运工问题
实现与改进
在上一节中,我们知道了IDA*算法是我们解决搬运工问题的核心算法。在这一节里,我们
将用IDA*算法来做一个解决搬运工问题的程序 - 虽然是我们的最初版本(我们称做S4-Bab
y),但是不要小看它哦!
1 IDA*算法框架
由前所述,IDA*算法是基于重复式深度优先的A*算法,忽略所有f值大于深度限制的结点。
那么,我们不难写出IDA*算法框架的伪代码
伪代码1 - IDA*算法框架
procedure IDA_STAR(StartState)
begin
  PathLimit := H( StartState ) - 1;
  Success := False;
repeat
inc(PathLimit);
StartState.g:= 0;
Push(OpenStack,StartState);
repeat
  CurrentState:=Pop(OpenStack);
  If Solution(CurrentState) then
    Success = True
  Else if PathLimit >= CurrentState.g + H(CurrentState) then
    Foreach Child(CurrentState) do
      Push(OpenStack, Child(CurrentState));
until Success or empty(OpenStack);
until Success or ResourceLimitsReached;
end;
这只是一个很粗略的框架,什么事情都不能做。不过我想大家可能比较急于试验一下IDA*
的威力,因此我们不妨就做一个最最基本的程序。
2. 第一个程序
要从框架做一个程序需要填充一些东西。在这里我们就展开一些讨论。
输入输出文件格式
输入文件是一个文本文件,它由N行构成,每行是一些字符。
各种字符的含义是:
SPACE   空地
.       目标格子
$       箱子
*       目标格子中的箱子
@       搬运工
+       目标格子中的搬运工
#       墙
表2 输入文件格式
这种格式和Xsokoban, SokoMind和Rolling Stone的格式是一致的,因此会比较方便一些。
输出文件第一行是推箱子的次数M,以下M行,每行的格式是:x y direction,代表把第x行
第y列的箱子往direction的方向推一步。Direction可以是left,right,up,down之中的一个
,1<=x,y<=20
数据结构
由于是最初的版本,我们不必考虑这么多:只需要可行,编程方便就可以了,暂时不管它
的效率和其他东西。优化是以后的事。
我们定义新的数据类型BitString,MazeType,MoveType,StateType和IDAType。请大家看附
录中的程序,不难猜出它们的含义和用途。唯一需要说明的BitString类型。记录状态时,
我们把地图看成一个大数,一个格子是一个bit。那么所有箱子构成一个BitString,检查某
一个是否有箱子(或者目标,墙)时只需要检测对应位置上的bit是否为1。这样虽然会浪
费一些空间,但是判断会比较快,操作也比较简单。
我们把x,y坐标合并成一个"position"变量。其中Position=(x-1)*width+(y-1)。
我们用常量数组DeltaPos:array[0..3]表示上,下,左,右的Position增量。
算法
为了简单起见,我们连最佳匹配也不做了,用所有箱子离最近目标的距离和作为下界函数
。不过,这里的"距离"是指推的次数,计算的时候(MinPush函数),只要忽略其它所有箱
子,然后用一次BFS就可以了。
效果
嘿嘿,这个效果嘛,不说你也知道的,就是标准关一个也过不了啦。不过为了说明我的程
序是正确的,你可以试验一下幼儿关卡(共61关)嘛!

什么!第一关都就没有动静了…55555,生成了18万个结点???不过很多关都很快就过了的
。我们用1,000,000个结点为上限(在我的Celeron 300A上要运行十多分钟),得到以下的测
试结果:
No.     步数    结点数  No.     步数    结点数  No.     步数    结点数
1       15      186476  21      8       102     41      11      145
2       6       24      22      7       110     42      10      118
3       5       14      23      10      192     43      12      223
4       6       24      24      10      432     44      8       63
5       9       31      25      4       23      45      12      138
6       5       8       26      11      846     46      14      178
7       6       35      27      3       18      47      8       296
8       11      39      28      9       38      48      8       156
9       4       12      29      10      142     49      5       60
10      5       14      30      8       641     50      11      14451
11      5       13      31      7       192     51      N/A     >1M
12      4       19      32      3       12      52      N/A     >1M
13      4       14      33      11      51      53      8       470
14      6       20      34      11      332     54      16      24270
15      6       57      35      16      11118   55      N/A     >1M
16      12      3947    36      10      242     56      14      3318
17      6       63      37      9       1171    57      N/A     >1M
18      11      5108    38      11      556     58      N/A     >1M
19      10      467     39      10      72      59      11      328
20      10      1681    40      9       203     60      N/A     >1M
                                                61      N/A     >1M
没有解决的几关是:51,52,55,57,,58,60,61
比较困难的几关是1,16,18,20,26,30,35,37,38,50,53,54,56
下面,我们来看看"困难关卡"的下界估计的情况,看看"偷懒"付出的代价。
关卡    最优步数        初始深度        结点总数        顶层结点数
1       15      11      186476  7416
16      12      7       3947    844
18      11      10      5108    49
20      10      6       1681    42
26      11      5       846     394
30      8       6       641     200
35      16      3       11118   3464
37      9       4       1171    493
38      11      5       556     250
50      11      6       14451   51
53      8       5       470     48
54      16      9       24270   2562
56      14      4       3318    460
由此可见,下界估计对于搜索树的大小是很有关系的。看看第18,20,35,50,54,56关吧。顶
层结点多么少!如果一开始就从这一层搜索不就…看来我们真的需要用最佳匹配算法了。

3.试验最佳匹配算法的威力
好,下面我们来使用最佳匹配算法。最佳匹配算法可以用网络流来实现,但是这里我们采
用修改顶标算法,我是抄的书上的程序(偷个懒嘛,呵呵)。现在,程序改叫Baby2了^_^
下面是刚才的"难题"的测试情况。
关卡    实际步数        初始深度        Baby-1结点总数  Baby-2结点总数
1       15      15      186476  60
16      12      10      3947    304
18      11      11      5108    46
20      10      8       1681    76
26      11      5       846     552
30      8       8       641     153
35      16      4       11118   6504
37      9       5       1171    438
38      11      5       556     546
50      11      7       14451   98
53      8       8       470     37
54      16      12      24270   273
56      14      4       3318    2225
哇!有的比刚才的顶层结点还要少!当然了,下界估计好了,当前层的深度剪枝也更准确
了嘛。
另外,现在我们来看看文曲星的前12关,第1,2,4,6,8,9,11关已经可以在50000个结点之内
出解。
关卡    实际步数        初始深度        结点总数        顶层结点数
1       31      31      75      75
2       11      11      142     142
4       26      18      33923   159
6       16      16      47      47
8       27      21      239     213
9       12      6       4806    2778
11      14      14      73      73
那么下一步干什么呢?打印出每个状态来分析,我们不难发现大量重复结点。所以下一个
问题自然就是:怎么避免重复呢?

4.试验HASH表的威力
判重嘛,当然就需要HASH表了。不过一个很棘手的问题是:如何表示状态?在结点扩展中
,我们用比特流的方式定义了箱子的状态,但是在这里我们需要的是合适的数组的下标。
这种表示法不爽吧。所以在构造HASH表的时候我们就用箱子的坐标来表示状态,也就是N元
组(p[1],p[2],p[3]..p[n])。至于散列函数嘛,我们根据HASH表的项数来考虑。这里,如
果箱子最多100个,我们就用10000项试试看。一种方案是把所有的坐标加起来,但是这样
做冲突很多!因为一个箱子A右移一格,另一个箱子B左移一格,散列函数值不变。考虑到
必须使冲突变少,函数又不宜太复杂,我们采用坐标的加权和来作为散列函数值,也就是
Sum{k*Position[k]},当然,最后要对10000取余数,其实这个函数也不好,不过我比较懒
了,以后再改进吧。至于冲突处理吗,为了简单起见,我们用开链法 设立链表来保存所有
元素。值得注意的是,箱子坐标相同而人的坐标不能互通的状态是不同的,应该一起保存
。下面是刚才那些关的测试结果:
关卡    实际步数        初始深度        Baby2结点数     Baby3结点数
Kid 1   15      15      60      52
Kid 16  12      10      304     189
Kid 18  11      11      46      41
Kid 20  10      8       76      67
Kid 26  11      5       552     192
Kid 30  8       8       153     145
Kid 35  16      4       6504    704
Kid 37  9       5       438     136
Kid 38  11      5       546     152
Kid 50  11      7       98      96
Kid 53  8       8       37      24
Kid 54  16      12      273     258
Kid 56  14      4       2225    1518
Wqx 1   31      31      75      75
Wqx 2   11      11      142     107
Wqx 4   26      18      33923   33916
Wqx 6   16      16      47      46
Wqx 8   27      21      239     226
Wqx 9   12      6       4806    968
Wqx 11  14      14      73      67
新完成的关卡有:
关卡    实际步数        初始深度        结点总数        顶层结点数
Kid 51  13      13      629     629
Kid 52  18      18      39841   39841
Ki d55  14      4       4886    1919
Kid 60  15      9       6916    916
需要注意的是,在保护模式下运行kid57的时候出现的heap overflow,说明完全保存结点
没有必要(费空间,费时间),也不大可能。那么,我们应该怎样做呢?我们知道,评价一
个HASH表的优劣,一般是从两个方面:查表成功的频率和查表成功以后节省的工作。因此
,我们可以设置两个Hash表,一个保存最近的结点(查到的可能性比较大)和深度大的结
点(一旦找到,节省很多工作)。这样做不会增加多少结点数,但是是程序效率有所提高
,求解能力(空间承受能力)也有较大改善。但是为了方便,我们的程序暂时只使用第一
个表。

5.结点扩展顺序的优化
在这一节中,我们的最后一个改进是优化结点扩展的顺序,不是想修剪搜索树,而是希望
早一点得到解。具体的改进方法是这样的:
1.优先推刚刚推过的箱子
2.然后试所有的能够减少下界的方案,减少得越多越先试。如果减少得一样多,就先推离
目标最近的。
3.最后试其他的,也象2一样按顺序考虑。
可以预料,这样处理以后,"比较容易"先找到解,但是因为下界估计不准所花费的代价是
无法减小的(也就是说只能减少顶层结点数)。不过作为IDA*的标准改进方法之一,我们
有必要把它加入我们的程序中试试。
(需要注意的是,我们使用的是栈,应该把比较差的方案先压栈)
实际测试结果,1的效果比较好,2和3的效果不佳,甚至产生了更多的结点。可能主要是我
们的下界估计不准确,而2和3用到了下界函数的缘故。这一个版本Baby-4中,我们屏蔽了
第2,3项措施。
好了,写了四个Baby版程序,想不想比较一下呢?不过我只对几个困难一点的数据感兴趣
。
关卡 实际步数 Baby-1 Baby-2 Baby-3 Baby-4
Kid 1 11 186476 60 52 38
Kid 16 7 3947 304 189 149
Kid 18 10 5108 46 41 31
Kid 35 16 11118 6504 704 462
Kid 50 11 14451 98 96 152
Kid 51 13 Too many Too many 629 54
Kid 52 18 Too many Too many 39841 97
Kid 54 16 24270 273 258 140
Kid 55 14 Too many Too many 4886 3390
Kid 56 14 3318 2225 1518 1069
Kid 60 15 Too many Too many 6916 5022
Wqx 4 26 97855 33923 33916 24251
Wqx 9 12 116927 4806 968 350
从上表可以看出,我们的优化总的来说是有效的,而且直观的看,那些改进不明显的很多
是因为下界估计比较差,这一点我们以后会继续讨论。不管怎样,这61关"幼儿关"过了58
关倒是挺不错的,至少可以说明我们程序的Baby版已经具有普通儿童的"智力"了^_^。不过
这只是个开头,好戏还在后头!

6.Baby-4源程序
程序S4BABY4.PAS在附件中,这里只是加了少量的注释。大家可以试试它的效果,但是没有
必要看得太仔细,因为在以后的章节中,我会改动很多东西,甚至连IDA*主程序框架都会
变得不一样。
常量定义:
const
  {Version}
  VerStr='S4 - SRbGa Super Sokoban Solver (Baby Version 4)';
  Author='Written by Liu Rujia(SrbGa), 2001.2, Chongqing, China';
  {Files}
  InFile='soko.in';
  OutFile='soko.out';
  {Charactors}
  Char_Soko='@';
  Char_SokoInTarget='+';
  Char_Box='$';
  Char_BoxInTarget='*';
  Char_Target='.';
  Char_Wall='#';
  Char_Empty=' ';
  {Dimentions}
  Maxx=21;
  Maxy=21;
  MaxBox=50;
  {Directions}
  Up=0;
  Down=1;
  Left=2;
  Right=3;
  DirectionWords:array[0..3] of string=('UP','DOWN','LEFT','RIGHT');
  {Movement}
  MaxPosition:integer=Maxx*Maxy;
  Opposite:array[0..3] of integer=(1,0,3,2);
  DeltaPos:array[0..3] of integer=(-Maxy,Maxy,-1,1);
我们把x,y坐标合成一个值position,其中position=(x-1)*maxy+(y-1)。这里用类型常量
是因为以后会根据地图的尺寸改变MaxPosition的值。Opposite就是相反方向例如Opposit
e[UP]:=DOWN;DeltaPos也是会重新设定的。我们在进行移动的时候只需要用:NewPos:=Ol
dPos+DeltaPos[Direction]就可以了,很方便。
  {IDA Related}
  MaxNode=1000000;
  MaxDepth=100;
  MaxStack=150;
  DispNode=1000;
每生成多少个结点报告一次。
  {HashTable}
  MaxHashEntry=10000;
  HashMask=10000;
  MaxSubEntry=100;
  {BitString}
  BitMask:array[0..7] of byte=(1,2,4,8,16,32,64,128);
  Infinite=Maxint;

类型定义:
type
  PositionType=integer;
  BitString=array[0..Maxx*Maxy div 8-1] of byte;
整个地图就是一个BitString。第position位为1当且仅当position位置有东西(如箱子,
目标,墙)。
  MapType=array[1..Maxx] of string[Maxy];
  BiGraph=array[1..MaxBox,1..MaxBox] of integer;
  MazeType=
  record
    X,Y:integer;
    Map:MapType;
    GoalPosition:array[1..MaxBox] of integer;
    BoxCount:integer;
    Goals:BitString;
    Walls:BitString;
  end;
尺寸,原始数据(用来显示状态的),目标的BitString,箱子总数,目标位置(BitStri
ng和位置数组都用是为了加快速度)和Walls的BitString。
  MoveType=
  record
    Position:integer;
    Direction:0..3;
  end;
Direction是箱子被推向的方向。
  StateType=
  record
    Boxes:BitString;
    ManPosition:PositionType;
    MoveCount:integer;
    Move:array[1..MaxDepth] of MoveType;
    g,h:integer;
  end;
  IDAType=
  record
    TopLevelNodeCount:longint;
    NodeCount:longint;
    StartState:StateType;
    PathLimit:integer;
    Top:integer;
    Stack:array[1..MaxStack] of StateType;
  end;
Top是栈顶指针。
  PHashTableEntry=^HashTableEntry;
  HashTableEntry=
  record
    Next:PHashTableEntry;
    State:StateType;
  end;
  PHashTableType=^HashTableType;
  HashTableType=
  record
    FirstEntry:array[0..MaxHashEntry] of PHashTableEntry;
    Count:array[0..MaxHashEntry] of byte;
  end;
这些是Hash表相关类型。我们采用的是拉链法,这样可以利用指针申请到堆空间,结合保
护模式使用,效果更好。
var
  HashTable:PHashTableType;
  SokoMaze:MazeType;
  IDA:IDAType;
procedure SetBit(var BS:BitString; p:integer);
begin
  BS[p div 8]:=BS[p div 8] or BitMask[p mod 8];
end;
procedure ClearBit(var BS:BitString; p:integer);
begin
  BS[p div 8]:=BS[p div 8] xor BitMask[p mod 8];
end;
function GetBit(var BS:BitString; p:integer):byte;
begin
  if BS[p div 8] and BitMask[p mod 8]>0 then GetBit:=1 else GetBit:=0;
end;
这些是位操作,设置,清除和得到一个BitString的某一项。
procedure Init;
var
  Lines:MapType;
  procedure ReadInputFile;
  var
    f:text;
    s:string;
  begin
    SokoMaze.X:=0;
    SokoMaze.Y:=0;
    SokoMaze.BoxCount:=0;
    assign(f,infile);
    reset(f);
    while not eof(f) do
    begin
      readln(f,s);
      if length(s)>SokoMaze.Y then
        SokoMaze.Y:=length(s);
      inc(SokoMaze.X);
      Lines[SokoMaze.X]:=s;
    end;
    close(f);
  end;
procedure AdjustData;
  var
    i,j:integer;
  begin
    for i:=1 to SokoMaze.X do
      while length(Lines[i])<SokoMaze.Y do
        Lines[i]:=Lines[i]+' ';
    SokoMaze.Map:=Lines;
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        if SokoMaze.Map[i,j] in [Char_BoxInTarget,Char_SokoInTarget,Char_Targe
t] then
          SokoMaze.Map[i,j]:=Char_Target
        else if SokoMaze.Map[i,j]<>Char_Wall then
          SokoMaze.Map[i,j]:=Char_Empty;
调整Map数组,把箱子和搬运工去掉。
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        if Lines[i,j] in [Char_Target,Char_BoxInTarget,Char_SokoInTarget] then
        begin
          inc(SokoMaze.BoxCount);
          SokoMaze.GoalPosition[SokoMaze.BoxCount]:=(i-1)*SokoMaze.Y+j-1;
        end;
统计Goal的个数和GoalPosition。
    DeltaPos[Up]:=-SokoMaze.Y;
    DeltaPos[Down]:=SokoMaze.Y;
    MaxPosition:=SokoMaze.X*SokoMaze.Y;
根据地图尺寸调整DeltaPos和MaxPosition
  end;
  procedure ConstructMaze;
  var
    i,j:integer;
  begin
    fillchar(SokoMaze.Goals,sizeof(SokoMaze.Goals),0);
    fillchar(SokoMaze.Walls,sizeof(SokoMaze.Walls),0);
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        case Lines[i,j] of
          Char_SokoInTarget, Char_BoxInTarget, Char_Target:
            SetBit(SokoMaze.Goals,(i-1)*SokoMaze.Y+j-1);
          Char_Wall:
            SetBit(SokoMaze.Walls,(i-1)*SokoMaze.Y+j-1);
        end;
  end;
  procedure InitIDA;
  var
    i,j:integer;
    StartState:StateType;
  begin
    IDA.NodeCount:=0;
    IDA.TopLevelNodeCount:=0;
    fillchar(StartState,sizeof(StartState),0);
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        case Lines[i,j] of
          Char_Soko, Char_SokoInTarget:
            StartState.ManPosition:=(i-1)*SokoMaze.Y+j-1;
          Char_Box, Char_BoxInTarget:
            SetBit(StartState.Boxes,(i-1)*SokoMaze.Y+j-1);
        end;
    StartState.g:=0;
    IDA.StartState:=StartState;
    new(HashTable);
    for i:=1 to MaxHashEntry do
    begin
      HashTable^.FirstEntry[i]:=nil;
      HashTable^.Count[i]:=0;
    end;
  end;
begin
  ReadInputFile;
  AdjustData;
  ConstructMaze;
  InitIDA;
end;
procedure PrintState(State:StateType);
var
  i,x,y:integer;
  Map:MapType;
begin
  Map:=SokoMaze.Map;
  x:=State.ManPosition div SokoMaze.Y+1;
  y:=State.ManPosition mod SokoMaze.Y+1;
  if Map[x,y]=Char_Target then
    Map[x,y]:=Char_SokoInTarget
  else
    Map[x,y]:=Char_Soko;
  for i:=1 to MaxPosition do
    if GetBit(State.Boxes,i)>0 then
    begin
      x:=i div SokoMaze.Y+1;
      y:=i mod SokoMaze.Y+1;
      if Map[x,y]=Char_Target then
        Map[x,y]:=Char_BoxInTarget
      else
        Map[x,y]:=Char_Box;
    end;
  for i:=1 to SokoMaze.X do
    Writeln(Map[i]);
end;
function Solution(State:StateType):boolean;
var
  i:integer;
begin
  Solution:=false;
  for i:=1 to MaxPosition do
    if (GetBit(State.Boxes,i)>0) and (GetBit(SokoMaze.Goals,i)=0) then
      exit;
  Solution:=true;
end;

function CanReach(State:StateType; Position:integer):boolean;
用BFS判断在状态State中,搬运工是否可以到达Position
var
  Direction:integer;
  Pos,NewPos:integer;
  Get,Put:integer;
  Queue:array[0..Maxx*Maxy] of integer;
  Reached:Array[0..Maxx*Maxy] of boolean;
begin
  fillchar(Reached,sizeof(Reached),0);
  Pos:=State.ManPosition;
  Get:=0; Put:=1;
  Queue[0]:=Pos;
  Reached[Pos]:=true;
  CanReach:=true;
  while Get<>Put do
  begin
    Pos:=Queue[Get];
    inc(Get);
    if Pos=Position then
      exit;
    for Direction:=0 to 3 do
    begin
      NewPos:=Pos+DeltaPos[Direction];
      if Reached[NewPos] then continue;
      if GetBit(State.Boxes,NewPos)>0 then continue;
      if GetBit(SokoMaze.Walls,NewPos)>0 then continue;
      Reached[NewPos]:=true;
      Queue[Put]:=NewPos;
      inc(Put);
    end;
  end;
  CanReach:=false;
end;
function MinPush(BoxPosition,GoalPosition:integer):integer;
在没有其他箱子的情况下,从BoxPosition推到GoalPosition至少要多少步。
var
  i:integer;
  Direction:integer;
  Pos,NewPos,ManPos:integer;
  Get,Put:integer;
  Queue:array[0..Maxx*Maxy] of integer;
  Distance:Array[0..Maxx*Maxy] of integer;
begin
  for i:=0 to Maxx*Maxy do
    Distance[i]:=Infinite;
  Pos:=BoxPosition;
  Get:=0; Put:=1;
  Queue[0]:=Pos;
  Distance[Pos]:=0;
  while Get<>Put do
  begin
    Pos:=Queue[Get];
    inc(Get);
    if Pos=GoalPosition then
    begin
      MinPush:=Distance[Pos];
      exit;
    end;
    for Direction:=0 to 3 do
    begin
      NewPos:=Pos+DeltaPos[Direction];
      ManPos:=Pos+DeltaPos[Opposite[Direction]];
      人应该站在后面
if Distance[NewPos]<Infinite then continue;
      if GetBit(SokoMaze.Walls,NewPos)>0 then continue;
      推不动
      if GetBit(SokoMaze.Walls,ManPos)>0 then continue;
      人没有站的地方
      Distance[NewPos]:=Distance[Pos]+1;
      Queue[Put]:=NewPos;
      inc(Put);
    end;
  end;
  MinPush:=Infinite;
end;
procedure DoMove(State:StateType; Position,Direction:integer; var NewState:Sta
teType);
var
  NewPos:integer;
begin
  NewState:=State;
  NewPos:=Position+DeltaPos[Direction];
  NewState.ManPosition:=Position;
  SetBit(NewState.Boxes,NewPos);
  ClearBit(NewState.Boxes,Position);
end;
function MinMatch(BoxCount:integer;Gr:BiGraph):integer;
这个是标准算法,抄的书上的程序,不用看了。
var
  VeryBig:integer;
  TempGr:BiGraph;
  L:array[1..MaxBox*2] of integer;
  SetX,SetY,MatchedX,MatchedY:Set of 1..MaxBox;
procedure MaxMatch(n,m:integer);
function Path(x:integer):boolean;
var
  i,j:integer;
begin
  Path:=false;
  for i:=1 to m do
    if not (i in SetY)and(Gr[x,i]<>0) then
    begin
      SetY:=SetY+[i];
      if not (i in MatchedY) then
      begin
        Gr[x,i]:=-Gr[x,i];
        MatchedY:=MatchedY+[i];
        Path:=true;
        exit;
      end;
      j:=1;
      while (j<=m)and not (j in SetX) and (Gr[j,i]>=0) do inc(j);
      if j<=m then
      begin
        SetX:=SetX+[j];
        if Path(j) then
        begin
          Gr[x,i]:=-Gr[x,i];
          Gr[j,i]:=-Gr[j,i];
          Path:=true;
          exit;
        end;
      end;
    end;
end;
var
  u,i,j,al:integer;
begin
  Fillchar(L,sizeof(L),0);
  TempGr:=Gr;
  for i:=1 to n do
    for j:=1 to m do
      if L[i]<Gr[i,j] then
        L[i]:=Gr[i,j];
  u:=1; MatchedX:=[]; MatchedY:=[];
  for i:=1 to n do
    for j:=1 to m do
      if L[i]+L[n+j]=TempGr[i,j] then
        Gr[i,j]:=1
      else
        Gr[i,j]:=0;
  while u<=n do
  begin
    SetX:=[u]; SetY:=[];
    if not (u in MatchedX) then
    begin
      if not Path(u) then
      begin
        al:=Infinite;
        for i:=1 to n do
          for j:=1 to m do
            if (i in SetX) and not (j in SetY) and (L[i]+L[n+j]-TempGr[i,j]<al
) then
              al:=L[i]+L[n+j]-TempGr[i,j];
        for i:=1 to n do if i in SetX then L[i]:=L[i]-al;
        for i:=1 to m do if i in SetY then l[n+i]:=l[n+i]+al;
        for i:=1 to n do
          for j:=1 to m do
            if l[i]+l[n+j]=TempGr[i,j] then
              Gr[i,j]:=1
            else
              Gr[i,j]:=0;
        MatchedX:=[]; MatchedY:=[];
        for i:=1 to n+m do
          if l[i]<-1000 then
            exit;
      end
      else
        MatchedX:=MatchedX+[u];
      u:=0;
    end;
    inc(u);
  end;
end;
var
  i,j:integer;
  Tot:integer;
begin
  VeryBig:=0;
  for i:=1 to BoxCount do
    for j:=1 to BoxCount do
      if (Gr[i,j]<Infinite)and(Gr[i,j]>VeryBig) then
        VeryBig:=Gr[i,j];
  inc(VeryBig);
  for i:=1 to BoxCount do
    for j:=1 to BoxCount do
      if Gr[i,j]<Infinite then
        Gr[i,j]:=VeryBig-Gr[i,j]
      else
        Gr[i,j]:=0;
  这些语句是进行补集转化。
  MaxMatch(BoxCount,BoxCount);
  Tot:=0;
  for i:=1 to BoxCount do
  begin
    for j:=1 to BoxCount do
      if Gr[i,j]<0 then
      begin
        Tot:=Tot+VeryBig-TempGr[i,j];
        break;
      end;
    if Gr[i,j]>=0 then
    begin
      MinMatch:=Infinite;
      exit;
    end;
  end;
  MinMatch:=Tot;
end;
function CalcHeuristicFunction(State:StateType):integer;
计算启发函数值
var
  H,Min:integer;
  i,j,p,Count,BoxCount,Cost:integer;
  BoxPos:array[1..MaxBox] of integer;
  Distance:BiGraph;
begin
  p:=0;
  for i:=1 to MaxPosition do
    if GetBit(State.Boxes,i)>0 then
    begin
      inc(p);
      BoxPos[p]:=i;
    end;
  for i:=1 to p do
    for j:=1 to p do
      Distance[i,j]:=MinPush(BoxPos[i],SokoMaze.GoalPosition[j]);
  BoxCount:=SokoMaze.BoxCount;
  H:=0;
  for i:=1 to BoxCount do
  begin
    Count:=0;
    for j:=1 to BoxCount do
      if Distance[i,j]<Infinite then
        inc(Count);
    if Count=0 then
    有一个箱子推不到任何目的地
    begin
      CalcHeuristicFunction:=Infinite;
      exit;
    end;
  end;
  H:=MinMatch(BoxCount, Distance);
  CalcHeuristicFunction:=H;
end;
function HashFunction(State:StateType):integer;
var
  i,h,p:integer;
begin
  h:=0;
  p:=0;
  for i:=1 to MaxPosition do
    if GetBit(State.Boxes,i)>0 then
    begin
      inc(p);
      h:=(h+p*i) mod HashMask;
      你可以自己换一个
    end;
  HashFunction:=h;
end;
function SameState(S1,S2:StateType):boolean;
var
  i:integer;
begin
  SameState:=false;
  for i:=1 to MaxPosition do
    if GetBit(S1.Boxes,i)<>GetBit(S2.Boxes,i) then
      exit;
  if not CanReach(S1,S2.ManPosition) then
  注意只要两个状态人的位置是相通的就应该算同一个状态
    exit;
  SameState:=true;
end;

function Prior(State:StateType;M1,M2:MoveType):boolean;
var
  NewPos:integer;
  Inertia1,Inertia2:boolean;
  S1,S2:StateType;
  H1,H2:integer;
begin
  Prior:=false;
  if State.MoveCount>0 then
  begin
    NewPos:=State.Move[State.MoveCount].Position+
            DeltaPos[State.Move[State.MoveCount].Direction];
    if NewPos=M1.Position then Inertia1:=true else Inertia1:=false;
    连续推同一个箱子的动作优先
    if NewPos=M2.Position then Inertia2:=true else Inertia2:=false;
    if Inertia1 and not Inertia2 then begin Prior:=true; exit; end;
    if Inertia2 and not Inertia1 then begin Prior:=false; exit; end;
  end;
end;
procedure IDA_Star;
var
  Sucess:boolean;
  CurrentState:StateType;
  H:integer;
  f:Text;
  procedure IDA_Push(State:StateType);
  begin
    if IDA.Top=MaxStack then
      Exit;
    inc(IDA.Top);
    IDA.Stack[IDA.Top]:=State;
  end;
  procedure IDA_Pop(var State:StateType);
  begin
    State:=IDA.Stack[IDA.Top];
    dec(IDA.Top);
  end;
  function IDA_Empty:boolean;
  begin
    IDA_Empty:=(IDA.Top=0);
  end;
上面的是栈操作
  procedure IDA_AddToHashTable(State:StateType);
  var
    h:integer;
    p:PHashTableEntry;
  begin
    h:=HashFunction(State);
    if HashTable^.Count[h]<MaxSubEntry then
    begin
      new(p);
      p^.State:=State;
      p^.Next:=HashTable^.FirstEntry[h];
      HashTable^.FirstEntry[h]:=p;
      inc(HashTable^.Count[h]);
    end
    else begin
      p:=HashTable^.FirstEntry[h];
      while p^.Next^.Next<>nil do
        p:=p^.Next;
      p^.Next^.State:=State;
      p^.Next^.Next:=HashTable^.FirstEntry[h];
      HashTable^.FirstEntry[h]:=p^.Next;
      p^.Next:=nil;
    end;
  end;
function IDA_InHashTable(State:StateType):boolean;
  var
    h:integer;
    p:PHashTableEntry;
  begin
    h:=HashFunction(State);
    p:=HashTable^.FirstEntry[h];
    IDA_InHashTable:=true;
    while p<>nil do
    begin
      if SameState(p^.State,State) then
      begin
        if p^.State.g>State.g then
        begin
          p^.State.g:=State.g;
          IDA_InHashTable:=false;
如果找到的表项深度要大些,并不代表这一次深度小点的也无解。本来应该动态更新下界
的,这里作为没有找到处理,后面的章节会改进这个地方的。
        end;
        exit;
      end;
      p:=p^.Next;
    end;
    IDA_InHashTable:=false;
  end;
这是Hash表的操作。
  procedure IDA_AddNode(State:StateType);
  begin
    IDA_Push(State);
    inc(IDA.NodeCount);
    if IDA.NodeCount mod DispNode=0 then
      Writeln('NodeCount=',IDA.NodeCount);
    inc(IDA.TopLevelNodeCount);
    IDA_AddToHashTable(State);
  end;
  procedure IDA_Expand(State:StateType);
  var
    MoveCount:integer;
    MoveList:array[1..Maxx*Maxy*4] of MoveType;
    t:MoveType;
    i,j,Direction:integer;
    NewBoxPos, NewManPos:integer;
    NewState:StateType;
  begin
    MoveCount:=0;
    for i:=1 to MaxPosition do
      if GetBit(State.Boxes,i)>0 then
        for Direction:=0 to 3 do
        begin
          NewBoxPos:=i+DeltaPos[Direction];
          NewManPos:=i+DeltaPos[Opposite[Direction]];
          if GetBit(State.Boxes,NewBoxPos)>0 then continue;
          if GetBit(SokoMaze.Walls,NewBoxPos)>0 then continue;
          if GetBit(State.Boxes,NewManPos)>0 then continue;
          if GetBit(SokoMaze.Walls,NewManPos)>0 then continue;
          if CanReach(State,NewManPos) then
          begin
            DoMove(State,i,Direction,NewState);
            if CalcHeuristicFunction(NewState)=Infinite then continue;
            if CalcHeuristicFunction(NewState)+State.g>=IDA.PathLimit then con
tinue;
IDA*算法的核心:深度限制
            if IDA_InHashTable(NewState) then continue;
            inc(MoveCount);
            MoveList[MoveCount].Position:=i;
            MoveList[MoveCount].Direction:=Direction;
          end;
        end;
    for i:=1 to MoveCount do
      for j:=i+1 to MoveCount do
        if Prior(State,MoveList[i],MoveList[j]) then
        调整推法次序
        begin
          t:=MoveList[j];
          MoveList[j]:=MoveList[i];
          MoveList[i]:=t;
        end;
    for i:=1 to MoveCount do
    依次考虑所有移动方案
    begin
      DoMove(State,MoveList[i].Position,MoveList[i].Direction,NewState);
      inc(NewState.MoveCount);
      NewState.Move[NewState.MoveCount].Position:=MoveList[i].Position;
      NewState.Move[NewState.MoveCount].Direction:=MoveList[i].Direction;
      NewState.g:=State.g+1;
      IDA_AddNode(NewState);
    end;
  end;
  procedure IDA_Answer(State:StateType);
  var
    i:integer;
    x,y:integer;
  begin
    Writeln(f,'Solution Found in ', State.MoveCount,' Pushes');
    for i:=1 to State.Movecount do
    begin
      x:=State.Move[i].Position div SokoMaze.Y+1;
      y:=State.Move[i].Position mod SokoMaze.Y+1;
      Writeln(f, x,' ',y,' ',DirectionWords[State.Move[i].Direction]);
    end;
  end;
begin
  Writeln(VerStr);
  Writeln(Author);
  IDA.PathLimit:=CalcHeuristicFunction(IDA.StartState)-1;
  Sucess:=false;
  repeat
    inc(IDA.PathLimit);
    Writeln('Pathlimit=',IDA.PathLimit);
    IDA.TopLevelNodeCount:=0;
    IDA.Top:=0;
    IDA.StartState.g:=0;
    IDA_Push(IDA.StartState);
    repeat
      IDA_Pop(CurrentState);
      H:=CalcHeuristicFunction(CurrentState);
      if H=Infinite then continue;
      if Solution(CurrentState) then
        Sucess:=true
      else if IDA.PathLimit>=CurrentState.g+H then
        IDA_Expand(CurrentState);
    until Sucess or IDA_Empty or (IDA.NodeCount>MaxNode);
    Writeln('PathLimit ',IDA.PathLimit,' Finished. NodeCount=',IDA.NodeCount);
  until Sucess or (IDA.PathLimit>=MaxDepth) or (IDA.NodeCount>MaxNode);
  Assign(f,outfile);
  ReWrite(f);
  Writeln(f,VerStr);
  Writeln(f,Author);
  Writeln(f);
  if not Sucess then
    Writeln(f,'Cannot find a solution.')
  else
    IDA_Answer(CurrentState);
  Writeln('Node Count:',IDA.NodeCount);
  Writeln;
  close(f);
end;
begin
  Init;
  IDA_Star;
end.
摘自http://vip.6to23.com

讲了这么多DFS BFS的优化,还有一些重要的东西没有讲,其实以上所有的搜索策略都属于盲目搜索的范畴,还有一种搜索我们称之为启发式搜索,实际上我们之前说到的有序搜索也是属于启发式搜索的,当然其中的搜索次序不是固定的 而是由估价函数 f决定的 。而前面讲到的BFSDFS 都只是启发式搜索在某种情况下的特例。实际上DFS BFS 只不过是分别将 负深度,和深度分别作为估价函数的值来进行拓展的。

 

首先简单介绍一下著名的A*算法

    A*算法中引入了一个估价函数f,其定义为f=g+h。其中g为到达当前节点的耗费,而h表示对从当


前节点到达目标节点的耗费的估计。其必须满足两个条件:


  其一, h必须小于等于实际的从当前节点到达目标节点的最小耗费h*。其二,   f必须保持单调递增。


  A*算法的控制结构与广度搜索的十分类似,只是每次扩展的都是当前待扩展节点中f值最小的一个,如果扩展出来的节点与已扩展的节点重复,则删去这个节点。


要实现A* 算法 我们需要一个优先队列 一般是由堆来实现的,当然也可以是stl 中的优先队列,具体实现上还是有一定难度的。


因为A*在实现上有一定的难度,我们一般使用A*的一种变种 称为迭代加深的A*算法(IDA*)这种算法不但实现简单(因为不需要保存结点,不需要判重复,也不需要根据 f值对结点排序),而且占用内存较小,速度也能让人满意。

他的基本结构如下

 

maxdepth=0

do

       DFS(startstate,0,maxdepth); 

while (maxdepth++ && 没有找到可行解)

 

 

DFS(nowstate,nowdepth,maxdepth)

{

       if (nowstate == 目标状态)

              return answer==maxdepth  一旦发现目标状态 即为最优解 深度为maxdepth

 

fvalue=f(nowstate);       估算的剩余深度

       if (nowdepth+fvalue>maxdepth) return;如果估计不能再maxdepth步中完成,则返回

       DFS(allnextstate,nowdepth+1,maxdepth);拓展所有子状态

}

 

在程序的主循环中我们从零开始枚举maxdepth 然后以maxdepth 最为最大深度来进行dfs ,在dfs 的过程中通过估价函数f的计算 如果发现当前状态无法在 maxdepth的深度之内完成时,我们就把这个状态连同他的子状态一起剪掉,来加快搜索速度。当然在这里一个好的估价函数是起到关键作用的。

这里介绍一个 ida*解决的经典问题

toj 1029 这道题目是一个经典问题,我在高中时就看到过了,好像是某年的国家队组队赛试题,那个时候一点想法也没有,主要问题时无法确定解空间的规模,因为数字可以是无穷大的阿,然而这个问题用ida*就很容易解决,我们可以设原分数为n,我们当前确定的枚举的分母是ai,那么很显然我们至少要再添加(n-∑(1/a))*ai 个数字才能使这些分数和等于n,这样我们就有了一个很好的估价函数 f(ai)= (n-∑(1/a))*ai ,这样很显然我们搜索的空间变得有限了,让后再通过枚举深度就可以得到我们需要的解了

再例如 zju 1361 ,八数码问题,和搬运工问题(zju 上也有这道题,可惜半年一次事故我的代码都没了,所以也不知道题号了,不高兴找了,那个看到了告诉我一下)都可以用ida*得到很好地解决 搬运工的问题比较复杂一点 我的blog里还有一篇有关的文章 有兴趣地可以看一下 当然这么高级的就一定不是我的产品了

 

当然启发式搜索和a*的变种还有其它很多种形式 mmsA* acm的题目中遇到的概率较小,也就不多费口舌了

       在外漂泊了15天昨天终于到家了,这段时间不知是吃的太好了还是吃得太差了,一直在拉肚子,反正是有点消化问题,本想如果有幸能借此契机减掉几斤到也不失为一件美事,可很多是事情就是事与愿违。。。

       我的acm 2005就这样结束了,铜牌,我为之奋斗2年多的结果,从未曾想到结局如此悲惨,记得一年前,大败而归之时,也曾暗暗发誓要在今年一雪前耻,但今天我知道一年来我的努力远远不够。成都一役之前,可以说我们还是沉静在莫名的自信之中,网上热身赛的的成绩似乎也在时不时地讨好我们。也曾经仔细分析过去年北京的试题,一道简单题,两道搜索题,这三道题构成了通向铜牌甚至银牌的阶梯,于是就此把搜索作为自己的主攻方向,图论说实话也只是作为副业,在知道了大多数标准算法之后也就没有深究了,至于数学味比较浓厚的题目如 数论与计算几何就顾及得更少了(多么严重的错误阿),今年两战唯一的一道搜索题是川大的apple tree 典型的博弈搜索,可惜我们连做完那两道简单题的时间都不够,更本没有时间,北京更好一道也没有,和去年的题型大相径庭。也算是终于知道了一块奖牌的真真分量,acm  不是那么简单的。

    不管怎么样今年的活动结束了,一块铜牌 也算是有了一个交待,也相信机会永远是有的,真的希望明年的今天已经是在享受成功的喜悦了,不过在这之前我知道我要走的路还很长很长

2005年11月16日

常见的搜索优化策略

现在acm的难度不断增加,简单的常规的搜索算法,(因为这些搜索的本质是盲目搜索)已经不能很好地解决问题,下面介绍 一些常见的优化方式

首先是深度优先搜索,对于DFS的优化主要是在时间复杂度上的,方法也有很多种,但是无论是何种优化方式,其本质都是通过减少扩展点的数量来降低时间复杂度的,当然减少的只能是那些不含可行解,或是不含最优解的状态。

常见的优化方式主要有以下几种:

1.剪枝 当我们发现某个状态的所有子状态都不可能是可行解时,我们就可以通过剪枝来避免拓展这个状态,(当然在有些时候 我们也可以通过预处理来实现,如 相同状态的合并,状态的有序化等)。剪枝的动机主要是通过主观判断,和数学推理来实现的,说来容易,但优秀的剪枝策略是需要通过大量的实践和 深厚的数学功底才能实现的。

例如, zju 1008 ,  zju 1909 都是属于深度优先加剪枝的经典题目,前者需要通过预处理的同状态合并,和判断来实现剪枝。而后者 则是通过有序枚举 状态中的元素 来消除重复的状态提高速度的。

 

 

2.有序搜索 也可以叫做 最优先搜索 是通过一定次序的搜索方式或是某种估价函数的判断来拓展状态从而寻找最优解的搜索,一般我们比较少使用估价函数,因为这已经不属于盲目搜索的范围了。有时对于某些DFS 问题中 我们可以先规定一个搜索的顺序,使我们能尽快地找到最优解 或者保证我找到的第一个可行解 即为所求得最优解。

例如 zju 1499  由于题目要求从一个数字串中求出一个递增序列 使最后一个数尽可能的小,在这个基础上使第一个数字尽可能的大。我们可以从小到大枚举最后一个数字,对于每一在这样的数字 我们再由大到小枚举序列的 第一个数字,让后再DFS查找是否存在一个这样的可行解 ,这样一旦我们找到了一个可行解,这个解也就必定是最优解了。

 

 

下面说说广度优先的优化,广度优先搜索的主要矛盾是空间复杂度上的矛盾,所以优化也主要是集中在处理空间复杂度的问题

1.双向广度优先搜索 同时从初始状态 目标状态 进行层次遍历 因为层次遍历中空间成指数级增长,所以双向的BFS 能为我们节省等多的空间,这一点从下图中可以清楚看见


图中黄色的部分即为空间的需求,双向BFS 实现起来也是比较方便的,添加一张节点表,作为反向扩展表。此外我们只需在原来的状态中增加一个参数指出这个状态的根节点是目标状态还是初始状态,当我们添加一个状态时如果我们发现在我们的队列中有同样的状态但来自不同的根节点 我们就可以得到所求的解。这里还有一个改进就是略微修改一下控制结构,每次扩展正反两个方向中节点数目较少的一个,可以使两边的发展速度保持一定的平衡,从而减少总扩展节点的个数,加快搜索速度。

这种优化可以帮我们更好的解决诸如 8数码之类的问题 而几乎所有能用单向BFS 的问题都能使用双向BFS,当然双向广度优先也不是没有缺点, 例如在某些问题无解是 它的空间复杂度就会大大大于一般的单向BFS

对于这一点对于无解状态很多的问题显然是致命的,所以使用时一定要加以考虑。

  

      

2,状态空间的优化,在确定使用广度优先之后 我们需要仔细的估算状态的数量,和规模,如果规模太大,超过了承受范围,我们就需要试着去考虑缩小状态的规模。

例如 zju 2288 ,第一眼看到题目,自然而然的想到 使用 4int  1 bool 来表示一个状态 分别表示两岸的人数 船当前的位置 可是这里的范围是1-200 状态的规模相当于 (200^4)*2这是我们无法接受的。可是一想因为两岸的人数和是一个定值,只需要两个 int就可以完整的表示一个状态 ,这样规模一下子就成了 200^2*2 很容易就搞定了。题目虽然简单,但却足以说明 控制状态规模的重要性,当然很多难题具体如何优化也是需要靠经验积累的

 

 

3.状态储存的优化,有些问题的状态数量可以满足要求,但是状态比较复杂,储存起来比较困难,这个时候我们就要考虑一下如何表示一个状态

例如 pku 2697 初看题目最直观的想法就是开个char 的二位数组来记录状态,这样需要的空间就是 16 个字节 储存一个状态 。但是实际上整个状态中只有 8 个点对我们有意义, 每个点我们可以用 两个坐标表示 这样我们可以用 16个整数来表示 一个状态,这样占用的空间反而大了 16*4)字节,这时我们会发现这里的每个整数实际上最多只有3,也就是2位二进制,于是我们就可以将这16个数利用位操作压缩到132位的int 中,分别表示白点和黑点的位置,而储存空间只有原来的1/4了,同时由于变成了标准数据类型,使下一步的比较等工作,方便了不少

 

 

4.判重过程中的优化,大家知道在BFS中去除重复状态的工作是必需的,然而简单的遍历所有队列中的状态,代价是极大的,在大多数情况下会换来一个tle 。为解决这个问题我们一般会使用hash表来解决这个问题。Hash函数的设计是需要经验的,好的hash函数能极大增快程序的速度,在考虑hash 表来判重时因该首先考虑哪些没有冲突的hash 方案,例如 前面讲到的  zju 2288 我们只需要开个200*200 bool 数组 就可以解决问题 所也不用去想其他方案了。但是对于有些问题使用没有冲突的hash 表超过了储存空间的上限,这样的例子很多 也可以说 绝大多数问题属于这一类 pku 2697 ,zju 1361  都是这样 这时我建议使用stl 中的map 来代替hash map 的本质是一个平衡二叉树,插入,和查找的复杂度都在logN左右 和一般的hash表差距不大,加之已经被高度封装 使用起来相当方便。

相比之下,写带有冲突处理机制的hash表再自己设计hash函数就十分复杂了。在使用map  的过程中 需要注意的是 如果我们使用的是自定义数据类型,我们需要为之定义一个判断大小关系的函数,如果不是很熟练可能会带来一点麻烦,所以最好的办法还是将状态压缩到一些标准数据类型中,这样我们就无需自己定义函数了,也给比较等工作带来了很多方便,

例如 上面我们说到的pku 2697可以被压缩到一个int中,而zju 1361 的状态也可以被压缩到一个string  中。其实大多数问题的状态都可以被压缩成标准数据类型不但节省了空间,也方便了操作。

搜索策略的选择 优化 与实现

atombomb

acm  的竞赛中 搜索是一个重要的考察方面 ,在历年的比赛中都有相当数量着这类试题。在经过一段时间的研究和整理之后 总结了一些经验 希望起到抛砖引玉的作用

 

 

在这篇文章中 你将看到的是 :

       常见的搜索形式与选择,各种搜索的常见优化与实现,搜索算法的一些变种,

 

 

 

 

一.竞赛中常见的搜索形式

 

 

acm 竞赛中的搜索主要可以分为 经典搜索 ,和类搜索 (姑且让我这样称呼,这些搜索有时可能已经不能算是真正的搜索算法了 但是却采用了 一些搜索的框架,模型,或思想,在搜索算法的变种中,会介绍一些这样的算法)

经典搜索 目前指的主要还是 深度优先搜索 广度优先搜索

1.首先介绍一下 深度优先搜索 深度优先搜索 DFS 可以算是在acm 竞赛中 使用最多的算法了 有时可以是一个简单的 全排列, 全组合的生成函数 可有时也可以是一整道难题,这就造成了 dfs 没有一个十分明确的固定形式 变化极其多样。但是总的来说 dfs 一般是基于这样的一个形式

void dfs(nowstate)

{

       if nowstate == goalstate   得到可行解

    else if (nowstate 的所有子状态 均为不可行解) return;

       set allnextstate={ 所有由当前nowstate 生成的nextstate}

       for (int i=0;i<allnextstate.size;i++)

              dfs(allnextstate[i]); 进入下一状态

}

这里的nowstate 可以是一个参数 也可以是多个不同参数 也可以是一个复合数据类型 总之这些数据要能够要能完全表示对于问题的一种状态的所有信息,而下面的nextstate 一般也和nowstate 有着同样的数据结构。上面的allnextstate 可以看成一个集合 每个元素为由当前状态可以生成的下个状态 但是这并不表示我们需要将他们一次性的全部生成,实际上在更多的情况下,我们生成一个 拓展一个。 这里还有一个初学者需要值得注意的问题就是在每拓展一个状态的一个子状态之后,在拓展它的下一个子状态之前 我们有可能需要调整一些全局变量的值  使这些辅助的状态变量 恢复到扩展前一个状态前的值。而当我们通过一定的计算或推理发现一个状态的所有子状态一定都为不可行解时我们就没有任何理由去拓展这个状态,通过这样的操作我们就可以实现剪枝了,这也是dfs 中的重要优化。

 

 

2.除了dfs 之外,广度优先搜索(bfs)也是搜索算法的重要组成部分,与dfs 相比bfs 可以看成是对状态树的层次遍历求解,而这一特性 也注定了bfs dfs 的巨大差异

BFS 中我们需要创建一个队列以保存所有的待扩展节点,而不是像BFS 那样只需要保存当前状态即可,这样就使BFS DFS 需要占用更多的空间,常常是成指数级增长的,但由于BFS是按层次遍历的一般来说能比DFS  更快的找到解,因为它找到的第一个可行解一般来说都是最优解,而无需像DFS 那样进行回朔。这里我们可以看出在程序的算法中时间复杂度 和空间复杂度通常是对立的,

       一般来说 bfs也可以有这样的一个模式;

 

 

queue<statestruct> qq;

qq.push_back(start);

while (!qq.empty)

{

       nowstate=qq.front;

       set allnextstate={ 所有由当前nowstate 生成的nextstate};

    for (int i=0;i<allnextstate.size;i++)

       {

              if (nextstate 不在 队列qq中时)

qq.push_back(nextstate);

}

       qq.pop_front;

}

       在上面的伪代码中statestruct 为用来储存一个状态的数据结构,qq 为储存待扩展状态的循环队列。当我们想将一个新的状态加入队列时 我们需要检查它在队列中否出现过,这样的步骤是必需的,不然会使我们已经捉襟见肘的储存空间更加紧张,一般来说这是难以承受的。与DFS 相比 BFS的变化相对较少, 一般它的难点在于空间复杂度上,需要处理一些诸如 状态表示 状态规模压缩 的工作,而BFS需要处理的一般则是时间复杂度上的问题,通常需要有比较好的剪枝策略,才能获得比较满意的效果。

 

 

所以我们在考虑使用何种搜索算法时,如果要采用DFS 就需要仔细计算和分析状态的规模,规模空间要在空间的允许范围内,而状态数量则要在时间的允许范围内。对于想采用BFS的问题我们主要考虑 状态的数量,并需要想方设法的减少这一数字。一般来说 BFS  主要针对哪个状态层次明显的求最优解问题。而DFS着针对一些层次感不明显,或是状态无序的问题。

未完待续。。。。。

opengl 里的最简单的东西 都写得差不多了 ,后面的内容自己还需要好好整理整理 ,先暂停一下,以后慢慢写

六,消隐 与双缓冲

六,消隐 与双缓冲

在上面的例子里,我们已经能在窗口中画出一个完整的3D 图形了,并且可以将它旋转,也知道如何将它平移,和缩放(第四节讲的)。可是这里还有几个问题:

首先是大家可能已经发现,在我们之前提到的所有例子中,在图形的旋转过程中整个图形都有一定程度的闪烁现象,显得图形的过渡极不平滑,这当然不是我们所要的效果,幸好opengl 支持一个称为双缓存的技术,可以有效的帮助我们解决这个问题。我们知道在我们电脑中,屏幕中显示的东西都会被放在一个称为显示缓存的地方,在通常情况下我们只有一个这样的缓冲区,也就是单缓冲,在单缓冲中任何绘图的过程都会被显示在屏幕中,这也就是我们为什么会看到闪烁,而所谓双缓冲就是再这个显示的缓冲区之外 再建立一个不显示的缓冲区,我们所有的绘图都将在这个不显示的缓冲区中进行,只有当一帧都绘制完了之后才会被拷贝到真正的现实缓冲区显示出来,这样中间过程对于最终用户就是不可见的了,那即使是速度比较慢也只会出现停顿而不会有闪烁的现象出现。

OpenGL 中我们可以通过glut 库中的函数

void glutSwapBuffers(void) 来实现从非显示缓冲区到显示缓冲区的复制

当然在使用双缓冲之前我们也要在 glutInitDisplayMode 设定参数的时候选择GLUT_DOUBLE 而不是之前我们用的 GLUT_SINGLE 相信这两个参数的意思也应该很明白了

在解决了闪烁的问题之后 我们来解决另一个问题 首先我们在窗口中画两个交叉的分别位于ZOX ZOY 平面的长方形 并用不同的颜色填充它们,然后让它们旋转很快我们发现有个比较严重的问题发生了,因为我们发现opengl显然没有空间的位置观念因为它根本不能分辨物体的前后关系,当然也不能做出适当的显示,在opengl中我们使用深度缓冲区来解决这个问题,在这个缓冲区中存放着每个象素深度信息,当有一个新的象素需要显示的时候,我们可以通过一个被称为深度测试的函数来确定它们的先后关系,要使用深度缓冲区有以下几个步骤:

1.  在函数 glutInitDisplayMode(mode) 中将GLUT_DEPTH置位 表明要使用深度缓冲区

2.  使用函数glEnable(GL_DEPTH_TEST) 打开深度测试函数

void glEnable(GLenum cap);

void glDisable(GLenum cap);

这两个函数属于基本状态管理函数 用来打开和关闭一些常用的功能,常用的参数有以下几个

GL_BLEND  GL_DEPTH_TEST  GL_FOG  GL_LINE_STIPPLE GL_LIGHTING

3.  是用函数glDepthFunc()来设置深度测试函数

void glDepthFunc(GLenum func)

这里我们比较常用的深度测试函数有 GL_LESS GL_LEQUAL 两者的区别在于当深度相同时是显示新的象素 还是老的象素

4.  使用下面的函数来设置深度缓冲区的值

void glClearDepth(GLclampd depth)

           这里的参数是背景的深度 一般来说 我们都将背景深度设成最大值1

5.   最后在我们使用glClear(bits) 刷新背景的同时 我们要将GL_DEPTH_BUFFER_BIT置位 表示我们在刷新背景颜色的同时 用刷新背景深度

 

 

下面我们将看到一个完整的使用了 消隐 双缓冲 的例子 大家可以把其中的相关语句去除 看看其中的差别

// opengltest.cpp : 定义控制台应用程序的入口点。

//

 

 

#include "stdafx.h"

 

 

 

 

#include <math.h>

#include <gl/glut.h>

#include <gl/gl.h>

 

 

bool mouseisdown=false;

bool loopr=false;

int mx,my;

int ry=30;

int  rx=30;

 

 

void timer(int p)

{

     ry-=5;

        glutPostRedisplay();

     if (loopr)

          glutTimerFunc(200,timer,0);

 

 

}

 

 

void mouse(int button, int state, int x, int y)

{

    if(button == GLUT_LEFT_BUTTON)

     {

 

 

        if(state == GLUT_DOWN)

         {    mouseisdown=true;  loopr=false;}

         else

              mouseisdown=false;

     }

     if (button== GLUT_RIGHT_BUTTON)

         if(state == GLUT_DOWN)

         {loopr=true;  glutTimerFunc(200,timer,0);}

   

}

 

 

void motion(int x, int y)

{

    if(mouseisdown==true)

    {

        ry+=x-mx;

         rx+=y-my;

         mx=x;

         my=y;

         glutPostRedisplay();

    }

}

 

 

void special(int key, int x, int y)

 

 

{

    switch(key)

    {

    case GLUT_KEY_LEFT:

        ry-=5;

        glutPostRedisplay();

        break;

    case GLUT_KEY_RIGHT:

       ry+=5;

        glutPostRedisplay();

        break;

    case GLUT_KEY_UP:

        rx+=5;

        glutPostRedisplay();

        break;

    case GLUT_KEY_DOWN:

        rx-=5;

      

        glutPostRedisplay();

        break;

    }

}

 

 

 

 

void init()

    //设置OpenGL的一些状态变量的初始值

{

    glEnable(GL_DEPTH_TEST);     //深度测试

    glDepthFunc(GL_LESS);                      //设置深度测试函数

    glPolygonMode(GL_FRONT_AND_BACK,GL_FILL);        //设置多边形显示模式为正反面都是填充显示

    glClearColor(1,1,1,1);          //设置刷新背景色

    glClearDepth(1);          //设置清除深度缓冲区所用的值

}

 

 

void display()

{

       

         float red[3]={1,0,0};

         float blue[3]={0,1,0};

         float green[3]={0,0,1};

         float yellow[3]={1,1,0};   

 

 

        glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

        

        

         glLoadIdentity();

         glRotatef(ry,0,1,0);      

         glRotatef(rx,1,0,0);

        

             

         glBegin(GL_QUADS);

              glColor3fv(green);

              glVertex3f(0.5,0.5,0);

              glVertex3f(-0.5,0.5,0);

              glVertex3f(-0.5,-0.5,0);

              glVertex3f(0.5,-0.5,0);

             

        

         glEnd();

        

         glBegin(GL_QUADS);

              glColor3fv(red);

              glVertex3f(0.5,0.5,0.3);

              glVertex3f(-0.5,0.5,-0.3);

              glVertex3f(-0.5,-0.5,-0.3);

              glVertex3f(0.5,-0.5,0.3);

             

        

         glEnd();

        

         glBegin(GL_QUADS);

             

              glColor3fv(yellow);

              glVertex3f(0.5,0.5,-0.3);

              glVertex3f(-0.5,0.5,0.3);

              glVertex3f(-0.5,-0.5,0.3);

              glVertex3f(0.5,-0.5,-0.3);

             

        

         glEnd();

 

 

        glFlush();

         glutSwapBuffers();

 

 

        

          //更新窗口

}

    

 

 

int main(int argc, char** argv)

{

  

    glutInit(&argc, argv);

    glutInitDisplayMode (GLUT_DOUBLE| GLUT_RGBA|GLUT_DEPTH);         //设置显示模式:单缓冲区, RGBA颜色模式

    glutInitWindowSize (400, 400);        //设置窗口宽度、高度

    glutInitWindowPosition(100,100);         //设置窗口位置

    glutCreateWindow ("double");        //弹出窗口

     init();

    glutDisplayFunc (display);        //设置窗口刷新的回调函数

     glutMouseFunc(mouse);         //设置鼠标器按键回调函数

    glutMotionFunc(motion);

     glutSpecialFunc(special);

    glutMainLoop();        //开始主循环

    return 0;

}

五,常用输入消息处理 

五,常用输入消息处理 

在第二章我们就提到glut这是一套opengl的辅助库,他使我们能十分简单的设置各种消息处理函数,而且与平台无关,也就是说如果使用glut windows 下编译通过程序无需更改便可在linux, mac os 下的编译运行,这一点是十分有用的,要知道win32api繁琐的代码走出了windows 的窗户可什么也干不了。给glut 作了这么多广告,让我们看看他是怎么用的.

在第二章我们看到的以glut 开头的函数都是 glut 库的一部分,如处理参数的,和设置窗口的,我们在这里主要讨论glut 支持的各种消息处理

首先,就是窗口更新的处理函数,我们知道各种窗口的操作都会引发窗口更新消息,在glut中我们通过

void glutDisplayFunc(void (*func)(void))

来设置窗口刷新的消息处理函数,其唯一的参数指定了屏幕刷新时会调用的函数

         如果要处理窗口变化的消息我们可以通过设置下面函数来实现

void glutReshapeFunc(void (*func)(int w, int h))

这里的func为回调函数,w,h分别为改变后窗口的宽和高

         对于键盘和鼠标的输入我们可以通过下面两个函数来设置

void glutKeyboardFunc(void (*func)(unsigned char key, int x, int y))

void glutMouseFunc(void (*func)(int button, int state, int x, int y))

这两个函数中的x y 都表示鼠标的位置,key 为键盘按键的ASCII吗。而button则为GLUT_LEFT_BUTTONGLUT_RIGHT_BUTTON分别表示左右按键。state为按键的状态,若为按下则为GLUT_DOWN

       当鼠标移动式我们还可以通过下面的函数来设置鼠标移动消息的处理函数

void glutMotionFunc(void (*func)(int x, int y))

X,Y仍然为鼠标的位置

         这里还有一个函数比较特殊

void glutIdleFunc(void (*func)(void)).

这里设置的是系统空闲时将会调用的函数

下面我们将看到一个完整的例子,通过输入来控制三维物体的旋转

#include <math.h>

#include <gl/glut.h>

#include <gl/gl.h>

 

 

#define pi 3.1415926

 

 

bool mouseisdown=false;

bool loopr=false;

int mx,my;

int ry=30;

int  rx=30;

 

 

 

 

void timer(int p)

{

     ry-=5;

        glutPostRedisplay();

     if (loopr)

         glutTimerFunc(200,timer,0);

 

 

}

 

 

void mouse(int button, int state, int x, int y)

{

    if(button == GLUT_LEFT_BUTTON)

     {

 

 

        if(state == GLUT_DOWN)

         {    mouseisdown=true;  loopr=false;}

         else

              mouseisdown=false;

     }

     if (button== GLUT_RIGHT_BUTTON)

         if(state == GLUT_DOWN)

         {loopr=true;  glutTimerFunc(200,timer,0);}

   

}

 

 

void motion(int x, int y)

{

    if(mouseisdown==true)

    {

        ry+=x-mx;

         rx+=y-my;

         mx=x;

         my=y;

         glutPostRedisplay();

    }

}

 

 

void special(int key, int x, int y)

 

 

{

    switch(key)

    {

    case GLUT_KEY_LEFT:

        ry-=5;

        glutPostRedisplay();

        break;

    case GLUT_KEY_RIGHT:

       ry+=5;

        glutPostRedisplay();

        break;

    case GLUT_KEY_UP:

        rx+=5;

        glutPostRedisplay();

        break;

    case GLUT_KEY_DOWN:

        rx-=5;

        glutPostRedisplay();

        break;

    }

}

 

 

void display()

{

       

         float red[3]={1,0,0};

         float blue[3]={0,1,0};

         float green[3]={0,0,1};

         float yellow[3]={1,1,0};   

    

    

         glClearColor(1,1,1,1);

         glClear(GL_COLOR_BUFFER_BIT);

         glLoadIdentity();

         glRotatef(ry,0,1,0);      

         glRotatef(rx,1,0,0);

         glColor3fv(green);

         glutWireTeapot(0.5);

         glFlush();

}

 

 

int main(int argc, char** argv)

{

    glutInit(&argc, argv);

    glutInitDisplayMode (GLUT_SINGLE| GLUT_RGBA); 

    glutInitWindowSize (400, 400);

    glutInitWindowPosition(100,100);     

    glutCreateWindow ("A TEAPOT");       

    glutDisplayFunc (display);      

     glutMouseFunc(mouse);       

    glutMotionFunc(motion);

     glutSpecialFunc(special);

    glutMainLoop();      

    return 0;

}

 

 

运行这个程序我们会发现一个茶壶,我们可以通过鼠标和键盘的方向键来控制它的旋转,而按下鼠标右键则可以让这个茶壶自动旋转,这里还有几个函数我们要注意一下

void glutWireTeapot(GLdouble size) 在当前的OCS坐标中心画一个以size为大小的茶壶

 

 

void glutSpecialFunc(void (*func)( int key, int x, int y)) 这个函数与glutKeyboardFunc的区别在于前者是用来响应键盘上的特殊按键,如方向键和控制键等。而后者则是用来响应键盘上的字符按键

 

 

void glutTimerFunc(int delay, (void (*func)( int parameter),int parameter) 这个函数相当于win32 api 中的timer 定时器,也是在delay毫秒后 放出一个定时器消息,而这里的func 则为这个消息的处理函数, patameter为附加参数。 这里有一点要注意这个函数是一次性的, 如果要重复使用可以在func中继续调用glutTimerFunc,而且这个功能是可以叠加的,在opengl 内部将他们看成许多个不同的定时器,这也就是为什么我们在上面的例子中连续按下鼠标右键会加快旋转的速度

.坐标变换 平移,缩放与旋转

.坐标变换 平移,缩放与旋转

 

 

    前面我们知道OpenGL内建的坐标系,事实上OpenGl有两套坐标系,一个坐标系被称为眼睛坐标(eye coordinate system) 简称ECS ,上章讲的就是这个坐标系。  OpenGL还有一套坐标,被称为(object coordinate system) 简称OCS ,而这个才是更为重要的,其实我们用来绘图的正是OCS

两个坐标系中ECS 可以看成是一个现实存在的 基本不变的全局坐标系,而OCS则可以看成是用户自定义的坐标系,我们可以将这个坐标系任意的平移与缩放,在初始情况下他和ECS是重合的,也可以通过glLoadIdentity()强制复位,这样可以给我们的绘图带来极大的方便。这里有一点是要值得注意的是在使用一个函数时需要弄清它是使用什么坐标系的,刚刚我们用到的glVertex系列函数都是用的OCS

    下面是一个平移的例子:

    void makecross(float *color) //在当前OCS的中心画一个十字

{   

              glBegin(GL_LINES);

                        glColor3fv(color); //设置当前颜色

                        glVertex3f(-1,0,0);

                        glVertex3f(1,0,0);

                        glVertex3f(0,-1,0);

                       glVertex3f(0,1,0);

                           

              glEnd();

}

void display()

{

       

         float red[3]={1,0,0};

         float blue[3]={0,1,0};

         float green[3]={0,0,1};

         float yellow[3]={1,1,0};   

    

         glClearColor(1,1,1,1);

         glClear(GL_COLOR_BUFFER_BIT);

        

         glLoadIdentity();

         makecross(red);

         glTranslatef(-0.5,-0.5,0);

         makecross(blue);

         glTranslatef(1,0.25,0);

         makecross(green);

         glTranslatef(-0.75,0.75,0);

         glScalef(0.5,0.5,1); //在x,y 上缩小一半

         makecross(yellow);

             

        glFlush();          //更新窗口

}

 这两个函数中makecross的作用是在坐标中心画一个十字,前面我们知道glVertex使用的是OCS 所以makecross 的作用便是在当前OCS的中心画一个十字,以观察OCS的位置,

  glColor3fv(color)的功能于之前我们看到的glColor3f(r,g,b)是一样的,只不过一个是使用一个数组作为参数

 

 

void glLoadIdentity(void)

  在display中 glLoadIdentity 的作用是使OCS 与ECS 重合,在这里我们用来初始化OCS 

 

 

void glTranslate{fd}(TYPEx, TYPE y, TYPEz);

glTranslatef 是将OCS平移至x,y,z 出,也就是在(x,y,z)处建立新的OCS,这里要注意这里的参数X,Y,Z也是OCS坐标

 

 

void glScale{fd}(TYPEx, TYPE y, TYPEz);

  glScalef则是当前OCS的缩放,x,y,z 分别指在三个方向上的放大倍数

 

 

   说完了缩放和平移,我们来看看旋转,opengl 里的旋转是通过glrotate来实现的,他的本质是将当前矩阵在乘于旋转矩阵,就是将当前的OCS 旋转一个指定的角度

                    void glRotate{fd}(TYPE angle, TYPE x, TYPE y, TYPE z);

glrotate 是将当前OCS绕向量(x,y,z)逆时针旋转angle度 例如我们要讲上例中的图形旋转绕Z轴旋转45度则可以通过glrotatef(45,0,0,1)来实现