single agent search

《single agent search》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SingleAgentSearchRujiaLiuContentAI(人工智能):通用问题求解器(GPS,GeneralProblemSolver)Search这个词…SingleAgent(代理,智能体)Search建模大部分工作放在状态空间(StateSpace)给”所有可能是解的东西”建立一个模型PathFinding:Sokoban搬运工.10*10,最多5个箱子格子:人,箱子,空地,障碍,目标,在目标中的箱子状态空间(图,很大,且隐式)所有可能出现的布局(结点)及布局相互转化规则(边)任务:寻找S到{T}中任意元素的一条路径(隐式图搜索)分析最基本的分析:61

2、00只有一个人!100*C(99,5)箱子只有5个*3(空地,障碍,目标)94空地、障碍固定.3100合并一下:100*C(99,5)修改状态空间定义:20*C(k,5)k是内部空地的数目Sokoban通常,search对空间利用相当充分typeState=recordbox:array[1..5{,1..2}]ofbyte;ren{x,reny}:byte;end空地编号:12个字节6字节状态转移procedureexpand(s:state);{如何利用s生成其他结点,每推一次算一步}fori:=1to5doforj:=1to4dobeginif(box[i]的j

3、方向有空位置)and(相对位置可达)thenbegin生成新状态s’s’:=s;s’.box[i]:=s.box[i]的j方向相邻格子坐标;s’.ren:=s.box[i];end;end;树和图不管是DFS还是BFS,得到的是树但实际上是一个图,因此有重复结点生成functionIssame(s1,s2:state):boolean;beginIssame:=false;Fori:=1to5doIfs1.box[i]<>s2.box[i]thenexit;Ifs1.ren<>s2.renthenexit;Issame:=true;end;问题(?)人相互可达的问题箱子

4、位置排序?(trade-off)状态定义里√扩展harder,判重easier判重时排扩展easier,判重harder扩展一个,判一个重(BFS)算法盲目深度优先搜索DFS广度优先搜索BFS迭代加深搜索ID(iterativeDeepening)双向广度优先搜索Bi-directional*启发式IDA*深度优先搜索proceduredfs(depth:integer;state:statetype);beginifstate是解then{处理}elseIfstate是其他边界then{….}elseforstate的每个儿子sondodfs(depth+1,son)

5、;end;DFS变形state:statetype;proceduredfs(depth:integer);beginif边界then…elsefor每个转移idobegin用state自身做转移Idfs(depth+1);恢复转移以前状态;end;end;空间,时间(复制工作,恢复工作)宽度优先搜索states:array[1..maxn]ofstatetype;a,b:integer;procedurebfs(start:statetype);beginstates[1]:=start;a:=1;b:=2;repeat{ifstates[a]是解,then…(标准)

6、}forstates[a]的每个儿子sondobeginifson在states[1..b]里没出现过thenbeginifson是解,then…{有问题}states[b]:=son;inc(b);end;end;inc(a);until找到解;end;判重细节把states组织成hashtable先比较”特征”,如果特征符合,再精细比较按照”特征”把元素分到若干”桶”中,每个桶有相同的特征查找:先计算特征,再在相应的桶中顺序查找.这里的特征,Hashfunction例:6个byte加在一起0-255*6Hashfunction例1:6byte相加例2:6byte相乘

7、,2556在分布均匀的情况下,Hashfunction值域越大,每个桶的越小,总的时间开销也越小(计算hashfunction本身代价不计)总时间开销=计算hashfunction的开销+桶内元素个数*比较时间模多项式法hfirst:array[0..MAXENTRY-1]ofstatetype;h:=0;fori:=1to6doh:=(h*t+b[i])modMAXENTRY;模多项式:Sum{akxk}在x=t的值modMAXENTRY注意事项1.模取素数2.hash表每一个hashfunction值对应一个桶,组织成链表(不带指针)