人工智能导论实验.doc

(完整版)人工智能导论实验
人工智能导论
实验报告

姓名：蔡鹏
学号：1130310726

实验一

一、 实验内容

有如下序列，试把所有黑色格移到所有白色格的右边,黄色格代表空格，黑色格和白色格可以和距离不超过三的空格交换。

二、 实验代码
#include <iostream〉
#include 〈stdlib.h〉
#include 〈stdio.h>
#define N 10
＃define inf 9999
int g=999;
void tree_gener(struct node *fn，struct node ＊root）;
struct node
{
char seq［7]；
int f,g，n；
struct node *sn［N］；
｝;
struct stack
{
int num;
struct node *n［50］；
｝；
void Enstack（struct node *sn,struct stack ＊S)
｛
S—〉n[S-〉num］=sn;
S-〉num++；
}
struct node ＊Destack（struct stack *S)
｛
S-〉num——；
return S->n[S->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 < min-〉f)
{
min=n；

}
for(i=0;i〈n—〉n；i++）
｛
Enstack(n->sn[i]，＆S);
}
｝
tree_gener（min,root）；
if（g〉min-〉g）
｛
printf(”seq:%c %c %c ％c ％c ％c ％c ｜ g：%d \n"，min->seq［0]，min—〉seq［1］,min—>seq[2］,min-〉seq[3］,min->seq[4]，min—〉seq[5],min—>seq[6］,min—>g）;
｝
g=min->g;
｝
void swap（struct node ＊sn，struct node ＊fn，int n,int m）
｛
int i;
for(i=0;i〈7;i++）
｛
sn—〉seq［i]=fn—>seq[i]；
}
sn—〉seq［n]=fn—〉seq［m];
sn-〉seq[m］=fn->seq[n];
}
int calcu_h(char seq［］）
｛
int m=0，n=0,i；
for（i=0；i〈7;i++）
{
if(seq［i］=='B’）
{
m++；
}
if(seq[i]=='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；i<7;i++）
｛
if(fn->seq［i］=='＃'）
｛
for(k=1;k<=3;k++）
｛
if（i+k<7)
{
fn—>sn[j］=(struct node *)malloc（sizeof(struct node))；
swap(fn—〉sn［j]，fn,i,i+k)；
fn—>sn［j］->g = fn->g+k；
fn—>sn[j］—>f = fn-〉sn［j]—〉g + 3*calcu_h（fn—〉sn[j]->seq);
fn-〉sn[j]—>n=0;
j++;
｝
if(i-k〉=0)
{
fn—〉sn[j］=（struct node *）malloc（sizeof（struct node)）；
swap（fn—〉sn［j］，fn，i,i—k）;
fn—〉sn［j］—〉g = fn->g+k；
fn—>sn[j]—>f = fn-〉sn［j]—〉g + 3*calcu_h（fn—〉sn［j］—〉seq）；
fn-〉sn［j］->n=0；
j++；
｝
}
｝
}
fn->n=j；
fn—〉f=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）);
root—〉seq[0]=’B’；
root—〉seq［1］=’B’;
root->seq[2］=’B’;
root—>seq［3]='W'；
root->seq［4]=’W’;
root—〉seq[5]='W’；
root—〉seq[6]='＃'；
root—>g=0；
root->f=0;
tree_gener(root，root）；
｝
三、 实验结果

四、 代码解释
1. 数据类型
数据类型
内容
含义
数据类型含义
struct node
Char seq[7]
节点序列
由父节点序列交换空格和与空格距离不大于3的节点得到的序列的子节点
Int f
代价函数值
Int g
当前节点已花费代价
Int n
子节点个数
Struct node ＊sn[］
子节点指针
Struct stack
Int 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_h
swap
Tree_gener
main
Destack
Enstack
find_min_f
3.函数调用关系

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}不是一个置换.

置换的合成
• 设q＝{t1/x1, t2/x2, …， tn/xn｝，
l＝｛u1/y1, u2/y2, …, un/yn}，是两个置换.
则q与l的合成也是一个置换,记作q·l.它是从集合
｛t1·l/x1， t2·l/x2， …， tn·l/xn, u1/y1， u2/y2, …， un/yn }
中删去以下两种元素：
– 当til=xi时,删去til/xi (i = 1, 2, …， n)；
– 当yiÎ｛x1,x2, …, xn｝时，删去uj/yj (j = 1， 2， …, m)
最后剩下的元素所构成的集合。
合成即是对ti先做l置换然后再做q置换
• 例:
设：q＝{f(y)/x, z/y},l＝｛a/x， b/y, y/z}，求q与l的合成。
解：先求出集合
{f(b/y)/x， （y/z)/y， a/x， b/y, y/z}＝{f(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，也需要删除。最后得
q·l＝{f（b)/x，y/z}

合一
• 合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。
• 定义：设有公式集F＝｛F1,F2，…，Fn｝，若存在一个置换q，可使F1q＝F2q＝…= Fnq，则称q是F的一个合一。同时称F1，F2，.。. ，Fn是可合一的.
•  例：
设有公式集F＝｛P(x， y, f(y）), P（a,g(x）,z)}，则l＝{a/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=Wk｛tk/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，t0＝a
（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 <string>
#include <vector〉
using namespace std;
int iC=0;
class Syncretism
{
private:
struct Transform
｛
string t_f1；
string t_f2;
}；
public:
bool Issyn（string f1，string f2， vector〈Transform> ＆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(j1〈f1。length()—1&&f1.at(j1)!=’,')
j1++；
if（j1-i==0） return t；
t.t_f1=f1。substr(i,j1-i）;
int j2=i；
while(j2〈f2.length（)-1&＆f2.at（j2）!='，’)
j2++；
if(j2—i==0) return t;
t。t_f2=f2。substr（i，j2-i）；
while（t。t_f1［j1—i-1]==t。t_f2[j2—i-1])
｛
t。t_f1.erase(j1-1—i）；
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，vector〈Transform〉 ＆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；
cout〈<"f1:”<<f1<<endl；
cout〈〈"f2:”〈〈f2〈<endl<〈endl;
｝
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(i<f.length（）)
{
i=f。find(t。t_f2)；
if（i〈f.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)==1＆＆var(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(i1<i2)
｛
string temp=t。t_f1;
t。t_f1=t.t_f2；
t.t_f2=temp;
｝
｝
return true;
｝
else
return true;
｝
int Syncretism：:var(const string s)
｛
if（s。length（）==0） return 0;

if（s。length(）==1&&s[0］〉='a’＆&s［0]〈=’g') return 1；
if（s.length（)>1）
{
int i=0;
while（i<s。length（)&＆s.at（i)！=’（'）
i++；
iC++;
string ss=s。substr(i+1，s.length()—i—2）;
return var(ss)；
}
else return 2;
｝
void Syncretism：:show()
｛
cout〈〈"常量：形如a，b,c，d（a—g)等"<〈endl〈<"变量：形如x,y,z,u等”<<endl；
string f1,f2；
cout〈<”输入F1:";
cin〉>f1;
cout〈<"输入F2:"；
cin>〉f2；
vector 〈Transform〉 lan;
if（Issyn（f1,f2,lan)）
｛
if（same（f1,f2））
｛
cout〈<”合一σ = ε ”〈〈endl;
return；
｝
cout〈〈”合一σ =｛ ”;
int i=0；
for(； i〈lan。size()—1； i++）
cout〈<lan［i］.t_f1〈<”/”〈<lan［i]。t_f2<<",”；
cout〈〈lan［i］.t_f1<<”/"<〈lan[i].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），每堆火柴的数量都是有限的，合法的移动是“选择一堆火柴并拿走若干根（不能不拿）"，如果轮到某个人时所有的火柴堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
必胜策略：
定义P—position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P—position，也就是“后手可保证必胜”或者“先手必败”,现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜"。更严谨的定义是:1。无法进行任何移动的局面（也就是terminal position）是P—position；2.可以移动到P—position的局面是N—position；3。所有移动都导致N-position的局面是P—position.
根据上面这个过程,可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略.
可以证明，对于一个Nim游戏的局面(a1，a2,.。。,an)，它是P-position当且仅当a1^a2^。..^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=x^p［i]
if(x==0）:
for i in range（1,12）：
if(p［i］〉0）:
return （i，p［i-1］)
else:
for i in range(1，12）：
if（p［i］^x<p[i]）:
return (i,p［i]^x)
return (-1,—1）