资源描述
(完整版)人工智能导论实验
人工智能导论
实验报告
姓名:蔡鹏
学号: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)
展开阅读全文