人工智能实习报告Word格式文档下载.docx
《人工智能实习报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《人工智能实习报告Word格式文档下载.docx（35页珍藏版）》请在冰点文库上搜索。
A*算法大致也同贪婪算法，只是对于结点的选择依据不同。
（4）运行结果：
（5）比较结论：
宽度优先
深度优先
贪婪算法
A*算法
生成结点数目
11
12
7
5
各算法搜索路径依次如下：
经过比较，显然，A*算法与贪婪算法生成的结点数目最少，效率最高。
深度优先生成的结点数目最多，效率最低，但这主要是因为程序中的搜索次序由对应结点序号决定，而恰好首选的结点又不是正确的结点才导致了这样的结果。
通常来讲，一般宽度优先的效率最低。
从运行出的搜索路径来看宽度优先、深度优先和贪婪算法搜索找到的也都不一定是最优解，只有A*算法具有完备性且始终找到的都是最优解。
即使宽度优先一定可以找到最优解，但往往它找到的第一个并非是最优的（本例中输出的就并不是最优的）。
在最坏的情况是，当目标结点是第d层的最后一个被扩展的结点时，它将耗费大量的时间。
其优先时间复杂度：
O（b^n+1）（b为分支因子，d为深度）；
空间复杂度为所存储的节点的个数。
而深度优先仅在结点有限的情况下是完备的，同样的，它也不能找到最优解。
深度优先的时间复杂度：
O（b^m）；
空间复杂度：
O（b*m+1）（b为分支因子，m为深度）。
贪婪算法找到的解也不一定是最优解。
其时间复杂度：
O（b^m）（b代表分支数，m为深度）；
空间复杂度为O（b^m）。
所以只有A*算法是完备的，且能够找到最优解。
第二部分N皇后问题
在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，分别用回溯法（递归）、GA算法和CSP算法求解n皇后问题。
ⅰ.输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率，并列表给出结果。
ⅱ.比较同一算法在n不相同时的运行时间，分析算法的时间复杂性，并列表给出结果。
1、逻辑结构：
用到线性结构包括一维数组，二维数组。
2、存储结构（物理结构）：
顺序存储结构。
回溯法：
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
在N皇后问题中基本思想是：
从第一列开始放置第一个皇后，然后第二列符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置，每次放置皇后之后都进行检查，验证是否符合要求（即皇后之间无冲突），当放置要求的数量N后问题即得到解。
GA算法：
从定义上看，遗传算法是模拟物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
对于一个求函数最大值的优化问题，首先初始化，包括种群的大小，编码的方案，遗传的代数，变异的概率，等等；
然后进行选择操作；
接着是将选择的个体进行交叉；
然后再进行选择，并将选择的个体进行变异；
最后就是更新最优值了。
在本题中，
采用的选择方法为按适应度比例选择，其中适应度为染色体（棋盘）中的基因（皇后）之间的冲突数目。
操作过程如下，采用单亲遗传算法：
1.产生初始种群。
2.对当前种群根据变异概率进行变异，生成新种群。
3.检验停止准则，如果有解则停止，否则转到2重复执行。
为了更快的得到解，采取了进一步的优化，在选择之后对中间个体进行一定几率的变异（将适应度较低的基因进行变异），从而使得更快的得到解决方案。
CSP算法：
1.初始化各个信息表，皇后位置初始化先让每列的皇后独占一行，确保每一行只有一个皇后，再随机交换任意两列皇后所在的位置，打乱棋盘
2.执行最小冲突算法：
1）.分析棋盘，算出棋盘每个位置其他皇后对它的冲突数，一个皇后对它冲突那个位置的值+1，每个皇后会影响水平和两个倾斜线上的各个位置
2）.从第一列开始遍历，把列的皇后移动到本列冲突数最小的位置，当有多个最小值的随机取得其中的一个。
3）.更新棋盘，按皇后原来的位置和移动后的位置更新三个方向上各个位置的冲突数，原来位置三个方向上各个位置冲突数-1，移动后的位置三个方向各个位置冲突数+1，遍历到最后一列。
4）.判断是否满足可行解，当各个皇后所在位置冲突数为0及找到可行解。
5）.当本次循环各个皇后的位置和上次循环皇后的位置不变，重新初始化各个皇后的位置。
跳转到2）
6）.当找到可行解退出循环。
（4）.运行结果：
（两种情况）
找不到结果时：
找到结果时：
（笑脸表示放置皇后的位置，*表示未放置皇后）
总体大致为：
回溯法
GA算法
CSP算法
时间复杂度
O（n!
）
O（kN）
O（N^N）
运行时间（s）
1.009
0.06
15.4
附程序关键代码：
罗马尼亚度假问题：
宽度优先算法：
intBFS（）
inti=0,j,v=0,r=1,u=0,m=1,p=0;
initdata（）;
while
（1）{
if（needvisit[i]!
=99）
{
visited[v]=needvisit[i];
v++;
u=needvisit[i];
needvisit[i]=99;
for（j=0;
j<
20;
j++）
{
if（data[u][j]!
=1000&
&
data[u][j]!
=0）
{
p=check_visit（j）;
if（p==0）
{
needvisit[m]=j;
m++;
result[r]=j;
r++;
if（j==2）
{
BFS_out（）;
return0;
}
}
}
}
}
else
i++;
}
return0;
深度优先算法：
intfind_after_node（intLine）
intj;
intp;
for（j=0;
20;
{
Line=needvisit[1];
if（data[Line][j]!
data[Line][j]!
p=check_visit（j）;
if（p==0）returnj;
return1;
intr=1;
intcal_DFS（）
{
inti,c=0;
while（needvisit[1]!
=99）
c=find_after_node（needvisit[1]）;
if（c!
=1）
{
result[r]=c;
r++;
needvisit[1]=c;
visited[c]=c;
if（c==2）
printf（"
路径为a:
"
）;
%s->
place[0].name）;
for（i=1;
result[i]!
=0&
i<
i++）
{
printf（"
place[result[i]].name）;
return0;
return1;
intDFS（）
inti=0,p1=0;
n_num=1;
visited[0]=0;
needvisit[1]=0;
//0标括?
记?
为a已?
访?
问ê
从洙?
第台?
结á
点?
开a始?
p1=cal_DFS（）;
while（p1==1）//没?
有瓺找ò
到?
正y确ā?
路·
径?
{
r=r-1;
result[r]=0;
//结á
果?
还1原-1位?
needvisit[1]=result[r-1];
p1=cal_DFS（）;
for（i=0;
i<
if（visited[i]==99）
n_num++;
printf（"
NULL"
\n生成结点数为a：
%d\n"
n_num）;
贪婪算法：
intfind_Greedy_node（intLine,intr）
intc1=0;
//c为所需返回的下一结点编括号
intmin=1000;
//存放最小移动消耗
check_visit（j）!
if（data[Line][j]<
min）
min=data[Line][j];
c1=j;
visited[c1]=c1;
result[r]=c1;
returnc1;
intGreedy_out（intr1）
inti;
intnum=0;
r1&
printf（"
if（visited[i]!
num++;
\n生成结点数为a:
num）;
intGreedy（）
intLine=0;
intr=1;
//r-result
while（Line!
=2）
Line=find_Greedy_node（Line,r）;
r++;
Greedy_out（r）;
A*算法：
intfind_A_node（intLine,intr）
intc=0;
intmin=10000;
=1）{
if（data[Line][j]+place[j].qf<
min=data[Line][j]+place[j].qf;
c=j;
visited[c]=c;
result[r]=c;
returnc;
intA_out（intr1）
intA（）
Line=find_A_node（Line,r）;
A_out（r）;
N皇后问题：
boolplace（intk）
for（i=1;
i<
k;
if（x[i]==x[k]||abs（i-k）==abs（x[i]-x[k]））
returnfalse;
}
returntrue;
}
intQueen（intt）
inti=0;
if（t>
n）
=n;
i++）
cout<
<
x[i]<
"
;
endl;
pl++;
else
i++）
x[t]=i;
if（place（t））
Queen（t+1）;
voidmain（）
clock_tstart,finish;
doubleduration;
Thenumberofqueen:
\n"
scanf（"
%d"
&
n）;
start=clock（）;
if（n==0）printf（"
Noresults!
else
Queen
（1）;
pl<
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
printf（"
Needtime:
%fseconds\n"
duration）;
system（"
pause"
voidUpdate（Population*p）
inti,j;
p->
unitFitness=0;
for（i=0;
n;
i++）
p->
eachFitness[i]=0;
for（j=0;
j<
j++）
p->
eachFitness[i]+=Aggressive（p,i,j）;
unitFitness+=p->
eachFitness[i];
voidCreateStartPopulation（）
inti,j;
inttmp[MAX_QUEENS];
tmp[i]=i;
j=rand（）%（n-i）;
s_population.queen[i]=tmp[j];
tmp[j]=tmp[n-i-1];
Update（&
s_population）;
voidMutate（）
inti,j,swap;
intworst;
Populationbaby;
worst=0;
if（s_population.eachFitness[i]<
s_population.eachFitness[worst]）
worst=i;
do{
j=rand（）%n;
}while（worst==j）;
baby=s_population;
swap=baby.queen[worst];
baby.queen[worst]=baby.queen[j];
baby.queen[j]=swap;
baby）;
if（baby.unitFitness>
s_population.unitFitness
||（double）rand（）/RAND_MAX<
Critical）
s_population=baby;
intRouletteWheelSelection（）
intselection=0;
inti;
doubleslice=（double）rand（）/RAND_MAX;
doubleaddFitness=0;
m_size;
addFitness+=（double）m_population[i].unitFitness/m_totFitness;
if（addFitness>
slice）
selection=i;
break;
returnselection;
voidCrossOverFM（Populationfather,Populationmother,Population*baby）
intflag[MAX_QUEENS];
intpos1,pos2,tmp;
pos1=rand（）%n;
pos2=rand（）%n;
}while（pos1==pos2）;
if（pos1>
pos2）{tmp=pos1;
pos1=pos2;
pos2=tmp;
for（j=0;
j++）
flag[j]=0;
for（j=pos1;
=pos2;
flag[father.queen[j]]=1;
for（i=0,j=0;
if（i<
pos1||i>
pos2）{
while（flag[mother.queen[j]]）j++;
baby->
queen[i]=mother.queen[j];
j++;
elsebaby->
queen[i]=father.queen[i];
Update（baby）;
voidCrossOver（）
intfather,mother;
Populationp[30+MAX_QUEENS/10];
intcount;
m_totFitness=0;
m_totFitness+=m_population[i].unitFitness;
for（count=0;
count<
m_size-2;
count++）
father=RouletteWheelSelection（）;
mother=RouletteWheelSelection（）;
CrossOverFM（m_population[father],m_population[mother],&
p[count]）;
m_population[count+2]=p[count];
voidinit_queen（Listlist）
intqueen_num=list->
max_queens;
intswap_row1,
升级会员 