Single Agent Search

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Single Agent Search,Rujia,Liu,Content,AI(,人工智能,):,通用问题求解器,(GPS, General Problem Solver),Search,这个词,Single Agent(,代理,智能体,) Search,建模大部分工作放在状态空间,(State Space),给,”,所有可能是解的东西,”,建立一个模型,Path Finding,:,Sokoban,搬运工,. 10*,10,最多,5,个箱子,格子,:,人,箱子,空地,障碍,目标,在目标中的箱子,状态空间,(,图,很大,且隐式,),所有可能出现的布局,(,结点,),及布局相互转化规则,(,边,),任务,:,寻找,S,到,T,中任意元素的一条路径,(,隐式图搜索,),分析,最基本的分析,: 6,100,只有一个人,! 100*C(99,5),箱子只有,5,个,*,3(,空地,障碍,目标,),94,空地、障碍固定,. 3,100,合并一下,: 100*C(99,5),修改状态空间,定义,: 20*C(k,5) k,是内部空地的数目,Sokoban,通常,search,对空间利用相当充分,type,State = record,box:array1.5,1.2 of byte;,renx,reny,: byte;,end,空地编号,: 12,个字节, 6,字节,状态转移,procedure,expand(s:state,);,如何利用,s,生成其他结点,每推一次算一步,for i:=1 to 5 do,for j:=1 to 4 do begin,if (,boxi,的,j,方向有空位置,) and (,相对位置可达,) then,begin,生成新状态,s,s := s;,s.boxi, :=,s.boxi,的,j,方向相邻格子坐标,;,s.ren,:=,s.boxi,;,end;,end;,树和图,不管是,DFS,还是,BFS,得到的是树,但实际上是一个图,因此有重复结点生成,function Issame(s1, s2:state):boolean;,begin,Issame,:=false;,For i:=1 to 5 do,If s1.boxi s2.boxi then exit;,If s1.ren s2.ren then exit;,Issame,:=true;,end;,问题,(?),人相互可达的问题,箱子位置排序,? (trade-off),状态定义里,扩展,harder,判重,easier,判重时排,扩展,easier,判重,harder,扩展一个,判一个重,(BFS),算法,盲目,深度优先搜索,DFS,广度优先搜索,BFS,迭代加深搜索,ID (iterative Deepening),双向广度优先搜索,Bi-directional,*启发式,IDA*,深度优先搜索,procedure,dfs(depth:integer,;,state:statetype,);,begin,if state,是解,then ,处理,else If state,是其他边界,then .,else for state,的每个儿子,son do,dfs(depth+1, son);,end;,DFS,变形,state:,statetype,;,procedure,dfs(depth:integer,);,begin,if,边界,then ,else for,每个转移,i do,begin,用,state,自身做转移,I,dfs(depth+1);,恢复转移以前状态,;,end;,end;,空间,时间,(,复制工作,恢复工作,),宽度优先搜索,states:array1.maxn of,statetype,;,a,b:integer,;,procedure,bfs(start:statetype,);,begin,states1:=start; a:=1; b:=2;,repeat, if,statesa,是解, then (,标准,) ,for,statesa,的每个儿子,son do,begin,if,son,在,states1.b,里没出现过,then begin,if son,是解, then ,有问题,statesb, := son;,inc(b,); end;,end;,inc(a,);,until,找到解,;,end;,判重细节,把,states,组织成,hash table,先比较,”,特征”,如果特征符合,再精细比较,按照,”,特征”把元素分到若干,”,桶”中,每个桶有相同的特征,查找,:,先计算特征,再在相应的桶中顺序查找,.,这里的特征, Hash function,例,: 6,个,byte,加在一起,0-255*6,Hash function,例,1: 6byte,相加,例,2: 6byte,相乘, 255,6,在,分布均匀,的情况下, Hash function,值域越大,每个桶的越小,总的时间开销也越小,(,计算,hash function,本身代价不计,),总时间开销,=,计算,hash function,的开销,+,桶内元素个数 * 比较时间,模多项式法,hfirst:array0.MAXENTRY-1 of,statetype,;,h := 0;,for i:=1 to 6 do,h:= (h * t +,bi,) mod MAXENTRY;,模多项式,:,Suma,k,x,k,在,x=t,的值,mod MAXENTRY,注意事项,1.,模取素数,2. hash,表每一个,hash function,值对应一个桶,组织成链表,(,不带指针,),state = record,next: integer; -1, if this is the last one,end;,实现细节,状态内容,:,States:array,桶内第一元素索引,: Hfirst:array0.MAXENTRY of integer,如果计算出,hash function=h,那么,桶的第一元素是,stateshfirsth,第二元素是,StatesHfirsth.next,第三元素是,StatesHfirsth.next.next,.,查找,function,find_state(s:statetype):boolean,;,begin,find_state,:=true;,h :=,compute_hash_function(s,);,temp :=,hfirst(h,);,while temp != -1 begin,if,issame(statestemp, s) then exit;,temp :=,statestemp.next,;,end;,find_state,:=false;,end;,插入,procedure,insert_state(idx:integer,);,begin,statesidx.next,:=,hfirsth,;,hfirsth,:=,idx,;,end;,估计,lg(10,100,)=100,lg(6,100,)=100*lg6=100*0.7781=77.81,lg(100!)=lg2+lg3+lg4+lg100,华容道,最优解,: 81,步,细节,状态空间大小,: 12!/(2!*4!*4!)=415k,状态编码,:,递推,代码*,10,元组,p0, p1, p2, p9,状态转移方便, hash function,可能会有冲突,1415k-1,整数,判重简单,转换,f(,局面,) =,整数,g(,整数,) =,局面,中间,:,排列,转换,f(,整数,) =,排列,f(0) = 001111222234,f(100) = ?,若第,1,位为,1,则,0xxxxx,全部排在前,0xxxxx,有多少个,?11!/(4!*4!)=69300,问题变为,:,给,1,4,4,1,1,求,f(100),F(70000)=?,第,1,位为,0,的全在前面,第,1,位为,1,的有,11!/(2!3!4!)=138600,第,1,位为,1.,问题变为,:,给,2,3,4,1,1,求,f(700),一般情况,f(x,),设第,1,位为,k,的有,sumk,个,sk,=sum0+.+sumk,若存在,sk-1 = x ,sk,第,1,位为,k.,问题变成,:,给出,p0, p1, pk-1, .,求,f(x-sk-1),求,hash function,g(,排列,) =,整数,g(242232111001)=?,形如,0xxxxxx(sum0),的有,69300,个,形入,1xxxxxx(sum1),的有,138600,个,因此,g(242232111001) = 69300+138600+k,问,g(42232111001)=?,重新算,sum0, sum1, .,累加,sum0+sum1+sum2+sum3,for(i,= 0; i PIECE_COUNT; i+),for(j,= 0; j 0),countj,-;,hash += fact11 - i /,(factcount0 * factcount1 * factcount2,* factcount3 * factcount4);,countj,+;,countcodei,-;,新的判重算法,/insert into,hashtable,code =,NodeCode(rear,);,if(HashTablecode,) rear-;,else,LastStaterear, = p;,HashTablecode, = true;,如何输出解,?,怎么保存,?,怎么输出,?,DFS:,栈里的东西就是一条路径,BFS?,State = record,Command :,commandtype,; /,操作序列,End;,有可能,command,比较大,长度为,81,的字符串？,设置父指针,.,状态,100,是状态,90,得到的,.,链表,States:array, of,statetype,State = record,Last : integer; / byte,Command : integer; / byte,end,双向广度优先搜索,判断：,与本方向,所有结点,中有相同,不要（长路径）,与相反方向,外层结点,中有相同,找到解,最优的么？正反,正,+,反,2,？,6+2=5+3,，由于长度为的路,全,搜过，因此应包含这一条,While,not_found,do,Begin,if count0 count1 then search(0);,else search(1);,End;,迭代加深搜索,两个大类,DFS,，没有一个,f(S,),函数，空间少,缺点：有圈，第一个解不一定最优，要全搜完,优点：空间开销小,Best-first search: BFS, A*,缺点：空间开销大,优点：第一个解最优,迭代加深搜索：,空间开销小,maxdepth,) then exit;,if,isgoal(state,) then,printanswer,else for direction :=1 to 4 do,go(state, direction),search(depth+1);,go(state, direction-1);,end;,End;,Begin,for,maxdepth,:= 1 to 1000 do,if search(1) then exit;,End.,有解充分必要条件,把空格看成数码,16,，对于任意的布局,S,，定义,perm(S,),为从上到下从左到右排出,S,的各个元素得到的,116,的排列，则,perm,（终态）,= 1, 2, 3, 4, 5,16,。这样，对于任意的,S,，设,16,的位置为,i,，考虑四种移动方法：,空格上移：相当于是元素,i,和元素,i,-4,交换。,空格下移：相当于是元素,i,和元素,i,+4,交换。,空格左移：相当于是元素,i,和元素,i,-1,交换。,空格右移：相当于是元素,i,和元素,i,+1,交换。,不管哪种情况，排列,perm(S,),的逆序数,+dist(16),的奇偶性不变（请读者验证）。进一步有定理：给初态,S,，,15,数码问题可解当且仅当,perm(S,),的逆序数,+ dist(16),为偶数。,约束满足,是要找一个解,(,序列、元组、集合,.),满足一定约束,.,只需要输出解就可以了,8,皇后,:,找一个排列,p1, p2, p3, p8,使得,pi,pj,不在同一对角线上,骑士遍历,:,找一个长度为,n,2,跳跃序列,(,每个跳法是一个,(,dx,dy,),记,di,为跳,i,步以后的位置,则,di,=di-1+(dxci,dyci,),每个,di,位置合法且不同,通常的方法,:,分步,看约束是否满足,部分结果不满足约束,则全局不满足约束,(prune),约束满足的特点,局部约束不满足,则全局约束也不满足,对比路径寻找问题,如,8,数码,剪枝条件,!,解的深度本来就是固定,/,基本固定,BFS,的,”,第一解最优”优点发挥不出来,DFS,扩展本来就不会形成环,BFS,的判重优点也发挥不出来,启发函数,:,路径没有意义,传统的启发式搜索的优点发挥不出来,约束满足的特点,状态空间对比,路径寻找问题,:,点比较完全的状态空间,问题在于图的结构,(,边,),约束满足问题,:,形态比较奇怪的状态空间,由所有满足约束的部分解组成,问题在于点,算法比较单一,年历回溯,*LDS,启发式修补,年历回溯,年历回溯算法,(chronological backtracking),的主要思想是依次确定每一个变量的取值，像深度优先算法一样，如果某变量的所有取值都会违反某约束，就回溯到上一个变量重新取值。,问题,!,搜索什么变量,以怎么样顺序搜,以怎样的顺序扩展,汽车问题,枚举方式,枚举第,1,2,3,数列的公差,枚举每个数属于哪个数列,对比,:8,数码问题的状态空间,超级天平,解,: 1n,的排列,约束,:,对于每个天平,sumwi,*,pi,=0,wi,为在位置,i,的秤砣重量或者子天平总重,特殊情况,:,动态规划判断是否有解,判断剩下位置的最小力矩和最大力矩,如果,current + max 0,则,prune,启发式修补,n,皇后问题,