人工智能导论实验.doc

(完整版)人工智能导论实验人工智能导论实验报告姓名：蔡鹏学号：1130310726实验一一、 实验内容有如下序列，试把所有黑色格移到所有白色格的右边,黄色格代表空格，黑色格和白色格可以和距离不超过三的空格交换。二、 实验代码#include #define N 10define inf 9999int g=999;void tree_gener(struct node *fn，struct node root）;struct nodechar seq7；int f,g，n；struct node *snN；;struct stackint num;struct node *n50；void Enstack（struct node *sn,struct stack S)SnS-num=sn;S-num+；struct node Destack（struct stack *S)S-num；return S-nS-num;void find_min_f（struct node root）int i;struct node n，min；struct stack S;S。num=0；min=root；Enstack（root，&S）;while(S。num！=0）n=Destack（&S）；if(n-f sni，S); tree_gener（min,root）；if（gmin-g） printf(”seq:%c %c %c c c c c g：%d n，min-seq0，minseq1,minseq2,min-seq3,min-seq4，minseq5,minseq6,ming）;g=min-g;void swap（struct node sn，struct node fn，int n,int m）int i;for(i=0;i7;i+）snseqi=fnseqi；snseqn=fnseqm;sn-seqm=fn-seqn;int calcu_h(char seq）int m=0，n=0,i；for（i=0；i7;i+）if(seqi=B）m+；if(seqi=W)n=n+m；return n；void tree_gener(struct node fn，struct node *root）if (calcu_h（fn-seq)!=0)int i;int j=0，k；for （i=0；iseqi=）for(k=1;k=3;k+）if（i+ksnj=(struct node *)malloc（sizeof(struct node)；swap(fnsnj，fn,i,i+k)；fnsnj-g = fn-g+k；fnsnjf = fn-snjg + 3*calcu_h（fnsnj-seq);fn-snjn=0;j+;if(i-k=0)fnsnj=（struct node *）malloc（sizeof（struct node)）；swap（fnsnj，fn，i,ik）;fnsnjg = fn-g+k；fnsnjf = fn-snjg + 3*calcu_h（fnsnjseq）；fn-snj-n=0；j+；fn-n=j；fnf=inf;find_min_f（root);int main（） struct node root；printf(seq:每一次选择的f最小的序列ng:当前节点已花费的代价nf：预计花费和已花费的代价的和.n);printf(倒序输出:n”）;root=（struct node *)malloc(sizeof(struct node）);rootseq0=B；rootseq1=B;root-seq2=B;rootseq3=W；root-seq4=W;rootseq5=W；rootseq6=；rootg=0；root-f=0;tree_gener(root，root）；三、 实验结果四、 代码解释1. 数据类型数据类型内容含义数据类型含义struct nodeChar seq7节点序列由父节点序列交换空格和与空格距离不大于3的节点得到的序列的子节点Int f代价函数值Int g当前节点已花费代价Int n子节点个数Struct node sn子节点指针Struct stackInt num栈顶标号用于深度优先遍历树的栈Struct node *sn节点数组2。函数函数名输入值返回值含义void tree_gener（struct node fn,struct node *root）父节点、根节点null为每次选取的代价函数最小的节点生成所有可能出现的子节点。int calcu_h（char seq)节点序列估计代价计算输入序列的估计代价void swap(struct node *sn，struct node *fn，int n，int m）空序列子节点、父节点、父节点交换的两个点位置null由父节点生成一种可能的子节点，交换父节点空格和白格或黑格的位置，交换后的序列赋给子节点.void find_min_f（struct node root）根节点null深搜树找到f最小的节点。void Enstack(struct node *sn，struct stack *S)子节点、栈null入栈struct node *Destack(struct stack *S)栈节点出栈Calcl_hswapTree_genermainDestackEnstackfind_min_f3.函数调用关系4. 算法介绍这里用到了A*算法（1） main函数首先生成一个根节点，调用tree_gener(根节点,根节点)（2） tree_gener，为传入的节点生成所有可能的子节点，并计算每个节点的g、f，调用find_min_f（根节点)（3） find_min_f深搜遍历树节点，找到f最小的的叶节点，调用tree_gener(f最小叶节点，根节点）（4） 直到find_min_f找不到最小叶节点为止路径即为解。5. 计算f用到的策略f=g+h，h等于所有白格子左边黑格子个数和的和。6. A*算法（引用百度百科)A(A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等）,在线查询效率是A算法的数千甚至上万倍。公式表示为： f(n)=g（n）+h（n),其中 f(n) 是从初始点经由节点n到目标点的估价函数,g(n) 是在状态空间中从初始节点到n节点的实际代价,h（n） 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数f(n）的选取：估价值h(n）= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低.但能得到最优解。并且如果h（n）=d（n）,即距离估计h（n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的.如果 估价值实际值,搜索的点数少,搜索范围小，效率高，但不能保证得到最优解。实验二一、实验内容编程实现mgu一般合一算法二、mgu一般和一算法的定义 置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义: 置换是形如t1/x1， t2/x2, , tn/xn的有限集合.其中，x1， x2， ， xn是互不相同的变量，t1， t2， , tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中.例如：a/x，c/y，f（b)/z是一个置换。g（y）/x,f(x)/y不是一个置换. 置换的合成 设qt1/x1, t2/x2, ， tn/xn， lu1/y1, u2/y2, , un/yn，是两个置换. 则q与l的合成也是一个置换,记作ql.它是从集合t1l/x1， t2l/x2， ， tnl/xn, u1/y1， u2/y2, ， un/yn 中删去以下两种元素： 当til=xi时,删去til/xi (i = 1, 2, ， n)； 当yix1,x2, , xn时，删去uj/yj (j = 1， 2， , m)最后剩下的元素所构成的集合。 合成即是对ti先做l置换然后再做q置换 例:设：qf(y)/x, z/y,la/x， b/y, y/z，求q与l的合成。解：先求出集合f(b/y)/x， （y/z)/y， a/x， b/y, y/zf(b)/x， y/y, a/x, b/y, y/z其中，f（b）/x中的f(b)是置换l作用于f（y）的结果;y/y中的y是置换l作用于z的结果.在该集合中,y/y满足定义中的条件i，需要删除;a/x,b/y满足定义中的条件ii，也需要删除。最后得qlf（b)/x，y/z合一 合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。 定义：设有公式集FF1,F2，Fn，若存在一个置换q，可使F1qF2q= Fnq，则称q是F的一个合一。同时称F1，F2，.。. ，Fn是可合一的. 例：设有公式集FP(x， y, f(y）), P（a,g(x）,z)，则la/x, g(a）/y, f(g（a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的. 最一般合一 设是谓词公式集F的一个合一，如果对F的任意一个合一q都存在一个置换，使得=.，则称是一个最一般合一。 最一般合一求取方法 令W=F1，F2 令k=0,W0=W， 0= 如果Wk已合一，停止， k=mgu,否则找Dk 若Dk中存在元素vk和tk，其中，vk不出现在tk中，转下一步，否则，不可合一. 令k+1= k.tk/vk,Wk+1=Wktk/vk=W k+1 K=k+1转第3步。例：W=P（a,x,f（g（y）)，P(z,f（a),f（u)，其中，F1 P（a,x，f(g(y)）)，F2 P(z，f(a)，f（u）求F1和F2的mgu解:由mgu算法（1)W= P(a，x，f(g（y），P(z，f(a),f(u)）（2）W0=W,0=（3） W0 未合一，从左到右找差异集，有D0=a,z（4)取V0=z，t0a（5)令3=2. t2/v2=a/z,f(a)/x,g（y）/u W3= W2 3=P(a,f（a)，f(g(y），P(a，f（a),f（g(y）)（3) W3 已合一 3= a/z,f(a)/x，g(y）/u便是F1和F2的mgu。算法的第(4)步，当不存在vk或不存在tk或出现差异集为x，f(x)，都会导致不可合一。此时，算法返回失败。三、实验代码故而，我们利用以上的理论和样例解释，我们可以进编程实现以上功能的C+代码。代码：include iostream#include #include t ）； Transform different（const string f1，const string f2) int i=0； Transform t; while(f1.at(i)=f2.at(i）) i+; int j1=i； while(j1f1。length()1&f1.at(j1)!=,) j1+； if（j1-i=0） return t； t.t_f1=f1。substr(i,j1-i）; int j2=i； while(j2f2.length（)-1&f2.at（j2）!=，) j2+； if(j2i=0) return t; t。t_f2=f2。substr（i，j2-i）； while（t。t_f1j1i-1=t。t_f2j2i-1) t。t_f1.erase(j1-1i）； t。t_f2。erase(j2-i-1）; j1； j2； return t； bool same(const string f1，const string f2）; string change(string f,Transform t）； bool legal（Transform &t）； int var（const string s)； void show（);bool Syncretism：Issyn（string f1，string f2，vectorTransform lan） while(！same(f1,f2) Transform t=different（f1,f2）; bool flag=legal(t)； if（!flag） return false; else lan.push_back（t）； if(flag) f1=change（f1，lan。back（)； f2=change(f2,lan.back()； cout”变换后：endl； coutf1:”f1endl； coutf2:”f2endlendl; if(same(f1,f2）) break； return true;bool Syncretism：:same(const string f1， const string f2) if（f1。compare(f2)=0) return true; else return false；string Syncretism：:change(string f,Transform t) int i=f.find(t。t_f2)； while(if.length（）) i=f。find(t。t_f2)； if（if.length(） f=f。replace（i，t。t_f2.length(）,t。t_f1）; return f；bool Syncretism:legal（Transform &t） if(t.t_f1.length（）=0|t.t_f2.length(）=0） return false； else if（var（t.t_f1）=0|var(t。t_f2)=0) return false； else if(var（t。t_f1)=1var(t.t_f2)=1&t。t_pare（t.t_f2）！=0) return false; else if(var(t.t_f1)=2) if(var（t。t_f2)=1) string temp=t.t_f1; t.t_f1=t.t_f2; t。t_f2=temp； else int i1=var（t。t_f2); i1=iC; iC=0； int i2=var（t。t_f1)； i2=iC; if(i11） int i=0; while（is。length（)&s.at（i)！=（） i+； iC+; string ss=s。substr(i+1，s.length()i2）; return var(ss)； else return 2;void Syncretism：:show() cout常量：形如a，b,c，d（ag)等endl变量：形如x,y,z,u等”endl； string f1,f2； coutf1; coutf2； vector Transform lan; if（Issyn（f1,f2,lan)） if（same（f1,f2） cout”合一 = ”endl; return； cout”合一 = ”; int i=0； for(； ilan。size()1； i+） coutlani.t_f1”/”lani。t_f2,”； coutlani.t_f1”/lani.t_f2 endl; else cout不能进行合一endl；int main(） Syncretism Sy; Sy。show（); return 0;相应的样例输入为：F1:p(a，x,f(g(y）F2:p（z,f（z),f（u）)对应的样例输出为：（详见下图中的样例输出）实验三一、实验内容Nim游戏：Nim游戏是博弈论中最经典的模型(之一），它又有着十分简单的规则和无比优美的结论 Nim游戏是组合游戏（Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（ICG）。游戏条件:1、有两名选手；2、两名选手交替对游戏进行移动(move),每次一步,选手可以在有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动,且这个局面的合法的移动集合为空（也就是说此时无法进行移动）,则这名选手负。 形象描述:Nim游戏的定义是这样的：有若干堆火柴（本题目为11），每堆火柴的数量都是有限的，合法的移动是“选择一堆火柴并拿走若干根（不能不拿），如果轮到某个人时所有的火柴堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。必胜策略：定义Pposition和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是Pposition，也就是“后手可保证必胜”或者“先手必败”,现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜。更严谨的定义是:1。无法进行任何移动的局面（也就是terminal position）是Pposition；2.可以移动到Pposition的局面是Nposition；3。所有移动都导致N-position的局面是Pposition.根据上面这个过程,可以得到一个递归的算法对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略.可以证明，对于一个Nim游戏的局面(a1，a2,.。,an)，它是P-position当且仅当a1a2。.an=0，其中表示异或(xor)运算.按照如上介绍，改写策略代码，实现电脑难以被战胜.二、实验结果实验测试：多次游戏均为AI获胜结果如下图：四、实验代码：def nim_func（p1，p2，p3,p4,p5,p6，p7，p8,p9，p10,p11）: print p1,p2,p3,p4,p5,p6，p7,p8,p9，p10，p11 p = 0，p1,p2,p3，p4,p5,p6,p7，p8，p9,p10，p11 x = 0 for i in range（1,12）：x=xpi if(x=0）:for i in range（1,12）： if(pi0）:return （i，pi-1) else:for i in range(1，12）： if（pixpi）:return (i,pix) return (-1,1）