您好,欢迎访问三七文档
人工智能课内实验报告计算机31班2130505008付若璇一、实验题目(1)利用线性插值技术,绘制主观贝叶斯的EH公式图像。要求给出LS、LN、P(H)、P(E)四个参数。(2)实现重排九宫格问题。二、问题分析和实验原理2.1主观贝叶斯EH公式线性插值曲线绘制2.1.1知识的不确定性在主观贝叶斯方法中,知识是如下形式的产生式规则表示:IFETHEN(LS,LN)H(P(H))其中:LS是充分性度量。其定义为:LS=P(E|H)/P(E|¬H)LN是必要性度量,其定义为:LN=P(¬E|H)/P(¬E|¬H)=(1-P(E|H))/(1-P(E|¬H))2.1.2LS和LN的意义LS是充分性度量,当证据E越是支持H为真时,则应是使相应的LS值越大。而LN是必要性度量,反映了¬对H的支持程度,¬越是支持H,则LN越大。所以,不能出现LS1且LN1的取值。虽然LS、LN可以有若干种取值,但是,一般情况下,取LS1,LN1。这是符合人类的思维习惯的。另外,实验程序中不允许输入LS>1且LN>1或者LS<1且LN<1的输入。2.1.3根据证据存在与否而确定的各种情况主观贝叶斯方法的核心是用P(E|S)将P(H)更新为P(H|S)。在证据确定的情况下,我们因该用杜达等人1976年证明了的公式来进一步讨论:P(H/S)=P(H/E)*P(E/S)+P(H/¬E)*P(¬E/S)分四种情况讨论这个公式:(1)P(E/S)=1时当P(E/S)=1时,P(-E/S)=0。此时公式变成(肯定存在的情况):1)(*)1()(*)/()/(HPLSHPLSEHPSHP(2)P(E/S)=0时当P(E/S)=0时,P(-E/S)=1.此时公式变成(肯定不存在的情况):1)(*)1()(P*)/()/(HPLNHLNEHPSHP(3)P(E/S)=P(E)时当P(E/S)=P(E)时,表示E与S无关。利用全概率公式就将公式变为:)()(*)/()(*)/()/(HPEPEHPEPEHPSHP(4)当P(E/S)为其它值时通过分段线性插值就可得到计算P(H/S)的公式:1)/()(P,)()/(*)(1)()/()()()/(0),/(*)()/()()/()/(SEPEEPSEPEPHPEHPHPEPSEPSEPEPEHPHPEHPSHP若若该公式称为EH公式或UED公式。2.2利用A*算法实现重排九宫格2.2.1搜索的一般过程(1)把初始节点S0放入OPEN表,并建立只含S0的图,记为G。OPEN:=S0,G:=G0(G0=S0)(2)检查OPEN表是否为空,若为空则问题无解,退出。LOOP:IF(OPEN)=()THENEXIT(FAIL)(3)把OPEN表的第一个节点取出放入CLOSE表,记该节点为节点n。N:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE)(4)观察节点n是否为目标节点,若是,则求得问题的解,退出。IFGOAL(n)THENEXIT(SUCCESS)(5)扩展节点n,生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M,并把这些节点作为节点n的子节点加入G中。EXPAND(n)--M(mi),G:=ADD(mi,G)针对M中子节点的不同情况,分别进行如下处理:对于那些未曾在G中出现过的M成员设置一个指向父节点(n)的指针,并把它放入OPEN表;对于那些先前已在G中出现过的M成员,确定是否要修改指向父节点的指针;对于那些先前已在G中出现,并且已经扩展了的M成员,确定是否需要修改其后继结点指向父节点的指针。(6)按某种搜索策略对OPEN表中的节点进行排序(7)转第2步。2.2.2A*算法我在实验中采用A*算法实现重排九宫格。A*算法是一种全局择优的启发式算法,可以证明它具有最优性。A*算法可以描述为f(n)=h(n)+g(n)的形式。其中,h(n)被称作启发函数,是当前结点到目标结点的代价描述;而g(n)是代价函数,描述了起始结点到当前结点的代价;f(n)是估价函数。A*算法是不回溯的,每次都选择f值最小的路径推进。在程序中,启发函数h(n)我选取的是当前结点和目标结点状态不同的个数。三、程序源码平台:windows10程序语言:Python2.7(32bit)依赖库:matplotlib(1)主观贝叶斯:from__future__importdivisionimportmatplotlib.pyplotaspltprintu输入LS:LS=input()printu输入LN:LN=input()printu输入P(H):PH=input()printu输入P(E):PE=input()p1=(LS*PH)/((LS-1)*PH+1)p0=(LN*PH)/((LN-1)*PH+1)pesline1=[0,PE]phsline1=[p0,PH]pesline2=[PE,1]phsline2=[PH,p1]plt.plot(pesline1,phsline1,'b')#,label=$line1$)plt.plot(pesline2,phsline2,'r')#,label=$line2$)plt.xlabel('P(E/S)')plt.ylabel('P(H/S')plt.xlim(0,1.1)plt.ylim(0,1.1)plt.legend()plt.show()重排九宫格importcopyimportsyssys.setrecursionlimit(1000000)start0=[[2,8,3],[1,0,4],[7,6,5]]end=[[1,2,3],[8,0,4],[7,6,5]]fathergraph=[]graph1={}openlist=[]closedlist=[]path1=[]classVector(object):docstringforVectordef__init__(self,value):super(Vector,self).__init__()self.father=0self.deep=0self.value=valueself.hn=0forx_index,linenumerate(value):fory_index,vinenumerate(l):ifv==0:self.x=x_indexself.y=y_indexdef__eq__(self,other):returnself.value==other.valuedeffathers(self,v):self.father=vdefdeeps(self,d):self.deep=ddefcmpVec(vec1,vec2):diffvec1=0diffvec2=0forindex,valueinenumerate(end):ifvec1.value[index]!=value:diffvec1+=1ifvec2.value[index]!=value:diffvec2+=1diffvec1+=vec1.deepdiffvec2+=vec2.deepreturndiffvec1-diffvec2definGraph(ve):ifnotfathergraph:returnFalseforiinfathergraph:ifi==ve:returnTruereturnFalsedefcontrol(s0,end):openlist.append(s0)deepmax=50whileopenlist:openlist.sort(cmp=cmpVec,reverse=True)n=openlist.pop()ds=n.deepclosedlist.append(n)ifn==end:printsucessbreakres=nextVector(n)ifresandn.deepdeepmax:ds+=1M=[xforxinresifxnotinfathergraph][x.fathers(n)forxinM][x.deeps(ds)forxinM][openlist.append(x)forxinM]Graph(graph1,n,M)defGraph(graph,fathervec,sonvec=[]):iffathervecnotingraph:graph[fathervec]=[]fathergraph.append(fathervec)ifsonvec:forvecinsonvec:graph[fathervec].append(vec)fathergraph.append(vec)returngraphdefnextVector(V):resultlist=[]temp=0x=V.xy=V.yifV.x==0:Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x+1][y]Vlist[x+1][y]=tempresultlist.append(Vector(Vlist))ifV.x==1:Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x+1][y]Vlist[x+1][y]=tempresultlist.append(Vector(Vlist))Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x-1][y]Vlist[x-1][y]=tempresultlist.append(Vector(Vlist))ifV.x==2:Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x-1][y]Vlist[x-1][y]=tempresultlist.append(Vector(Vlist))ifV.y==0:Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x][y+1]Vlist[x][y+1]=tempresultlist.append(Vector(Vlist))ifV.y==1:Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x][y+1]Vlist[x][y+1]=tempresultlist.append(Vector(Vlist))Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x][y-1]Vlist[x][y-1]=tempresultlist.append(Vector(Vlist))ifV.y==2:Vlist=copy.deepcopy(V.value)temp=Vlist[x][y]Vlist[x][y]=Vlist[x][y-1]Vlist[x][y-1]=tempresultlist.append(Vector(Vlist))returnresultlistif__name__=='__main__':result=[]s=Vector(start0)fathergraph.append(s)e=Vector(end)control(s,e)fa=closedlist[len(closedlist)-1]whilefa:result.append(fa)fa=fa.fatherresult=result[::-1]forxinresult:printx.value四、程序结果(1)主观贝叶斯(2)重排九宫格①初始状态:2,8,3,1,0,4,7,6,5结束状态:1,2,3,8,0,4,7,6,5②初始状态:2,8,1,3,0,4,7,6,5结束状态:1,2,3,8,0,4,
本文标题:实验报告
链接地址:https://www.777doc.com/doc-7273636 .html