人工智能实验报告大全.doc

人工智能课内实验报告
(８次）
学　 院： 　自动化学院 　　 　　
班 　　 级： 　智能１５01 　 　　　
姓 名：　 刘少鹏(34) 　
学 　号:　 　　　
　 　 　　目 录
课内实验1:猴子摘香蕉问题得VC编程实现……………………1
课内实验2:编程实现简单动物识别系统得知识表示………5
课内实验3:盲目搜索求解８数码问题………………………18
课内实验4：回溯算法求解四皇后问题………………………33
课内实验5:编程实现一字棋游戏……………………………37
课内实验6:字句集消解实验…………………………………４６
课内实验7：简单动物识别系统得产生式推理………………6６
课内实验8:编程实现D-S证据推理算法……………………７8

人工智能课内实验报告
实验1:猴子摘香蕉问题得VC编程实现
学 院: 　 自动化学院 　
班　 级: 智能15０１　 　 　
姓 名: 刘少鹏 (33)　　
学 号: 　 0615３0３4 　 　
日 　 期:　２017—3—8　10:１5－12：00
实验1:猴子摘香蕉问题得VC编程实现
一、 实验目得
(１）熟悉谓词逻辑表示法;
（2）掌握人工智能谓词逻辑中得经典例子—-猴子摘香蕉问题得编程实现．
二、编程环境
VC语言
三、 问题描述
房子里有一只猴子（即机器人),位于a处。在ｃ处上方得天花板上有一串香蕉,猴子想吃，但摘不到。房间得b处还有一个箱子，如果猴子站到箱子上,就可以摸着天花板。如图1所示,对于上述问题，可以通过谓词逻辑表示法来描述知识。要求通过VC语言编程实现猴子摘香蕉问题得求解过程。

图1　 猴子摘香蕉问题
四、 源代码
#iｎｃlude〈stdiｏ、ｈ〉
unsignｅd iｎｔ　i；
ｖoid Monkey_Go_Box(unsｉgned ｃhａr ｘ，　uｎsｉgned cｈar　y)
｛
ﻩ 　 　　ｐｒinｔf("Sｔep ％d：ｍoｎkeｙ从％ｃ走到%ｃ\n"， +＋ｉ，　x, ｙ);／／x表示猴子得位置,ｙ为箱子得位置
｝
vｏid Ｍoｎkey_Move_Box(chaｒ ｘ, ｃhar y)
{
　　 printf("Sｔeｐ　%d：monkey把箱子从%c运到%c\n",　+＋i， x, y);／／x表示箱子得位置,y为香蕉得位置
}
ｖoiｄ Ｍｏnｋｅｙ＿Ｏn＿Box()
{
　 　 pｒintｆ（”Ｓtep %ｄ：ｍonkey爬上箱子＼n",　++i）;
}
voiｄ Monkey_Get_Banａnａ（)
{
　 prｉntｆ(”Step　%d:monkey摘到香蕉\n", ++i）;
｝
ｖoid　maiｎ（)
{
ﻩ　 　 uｎｓigned char　　Mｏnkey, Box, Banana;
ﻩ pｒinｔf(”＊*******智能1501班*＊**＊*＊**＊＼n");
　 ｐriｎtf（”＊*＊＊**＊*061530３4＊＊＊**＊*＊**＊*＼n”）；
ﻩ　 　 ｐrintf（”＊*＊＊*＊＊＊刘少鹏*******＊*＊＊***\n")；
ﻩ pｒinｔｆ（"请用ａ　ｂ c来表示猴子箱子香蕉得位置\n");
ﻩ 　　 printｆ(”Moｎkeｙ\ｔboｘ\tbanana\n”);
scanf(”％c”, ＆Mｏnkeｙ)；
ﻩ 　 　ｇetｃhaｒ();
ﻩ 　pｒintｆ（”\t”)；
scanf(”％c＂, &Box);
getchaｒ();
ﻩ 　　　ｐrｉｎtf("\t＼ｔ"）；
ﻩ scanf("%ｃ”, &Bａnａna）;
　　 gｅｔcｈar();
　 pｒintｆ("＼ｎ操作步骤如下＼ｎ”）;
ﻩ 　 if （Monkey !＝ Box）
｛
ﻩ 　 Mｏｎｋey＿Go_Ｂox（Ｍonｋey,　Ｂｏｘ)；
　 }
　 　 ｉｆ （Box ！=　Banａna）
ﻩ {
ﻩ Ｍonkeｙ＿Ｍoｖe_Ｂox(Box,　Bａnana）;
ﻩ 　 }
　 　 　 Ｍｏnkey＿On_Box(）；
ﻩ 　 　 Monkeｙ_Ｇeｔ＿Ｂaｎａna（）;
　 　 ｐrｉntf(”\n")；
ﻩ 　 gｅtｃｈar（)；
｝
五、 实验结果相关截图

六、心得体会
　 　　 通过本次实验,我初步了学会了使用ＶＣ得新建工程，并且进行简单得程序编写。此外我还学会如何使用一些谓词来解决生活中得一些简单问题,并且用ＶC编程给出具体得操作步骤,感觉对VC编程有了新得认识。在实验中我也遇到过许多问题,比如在我写完代码进行编译时总就是会出现一个错误“ ｆataｌ eｒｒor C1010:　在查找预编译头时遇到意外得文件结尾,就是否忘记了向源中添加“#iｎｃluｄｅ ‘ｓtdafｘ、ｈ’”关于这个错误我我问了几个同学得不出答案后,我决定通过上网查找,最终找到了解决方法，需要在该项目得每一个ｃpｐ结尾得文件属性中设置不使用预编译头即可。在这个过程中也锻炼了自己解决问题得能力。

人工智能课内实验报告
实验2:编程实现简单动物识别系统得知识表示
学 院： 自动化学院　 　　 　
班 级: 智能１501 　 　　
姓 　　名: 刘少鹏(3３) 　　
学　　 　号：　　061５3034　 　 　 　
日 　 期: ２0１7－3—13 10：15—1２：00 　　
实验２：编程实现简单动物识别系统得知识表示
一、实验目得
1、理解与掌握产生式知识表示方法；
2、能够通过VC编程语言实现产生式系统得规则库。
二、实验内容
１、以动物识别系统得产生式规则为例；
2、用选定得编程语言建造规则库与综合数据库，并能对它们进行增加、删除与修改操作.
三、 实验步骤
1、 确定需要识别得动物及其属性
本次实验得简单动物识别系统总共能识别7种动物，即:老虎、金钱豹、斑马、长颈鹿、企鹅、鸵鸟与信天翁。
2、 建立识别七种动物识别系统得规则
3、 选定编程语言并确定综合数据库与规则库结构
（1） 选用Ｃ语言作为编程语言
　 (２)综合数据库得建立
(3）规则库得建立
四、程序源代码
#inｃｌuｄe 〈iostream〉
#incｌuｄe <stｒiｎg>
usｉng　ｎameｓpａcｅ std;
struｃｔ RULESﻩﻩ ﻩ
{
　　 iｎt cｏunt;
ﻩ char　pre[2５5]；
ﻩ 　　 chaｒ　back[２55];
　int maｒｋ；
}；
ｖoｉd chｅcｋ();
RULES　ｒ[1００］　= {
ﻩ 　 ｛ 1，”有毛发＂,＂哺乳动物＂,0 }, ﻩ //所有规则静态数据库
ﻩ　 　 　｛ １,”有奶",”哺乳动物",0　},
ﻩ 　　 　｛ 1，"有羽毛”，”鸟＂，０　},
ﻩ 　 　 　｛ ２，”会飞&下蛋＆"，"鸟"，0 },
　 　 　 { 1,”吃肉","食肉动物”，０ ｝,
ﻩ 　 　　 　{ 3，”有锋利得牙齿&有爪&眼睛盯着前方＆”,"食肉动物”,０ }，
ﻩ 　 　 　 { 2,"哺乳动物&有蹄&”,”有蹄类哺乳动物”,0 },
ﻩ 　 　 { 2,”哺乳动物&反刍&”，”有偶蹄类哺乳动物”,0 },
ﻩ 　 　 { ４,”哺乳动物＆食肉动物&黄褐色＆有暗斑&"，”金钱豹"，0 },
　 　 { ４,"哺乳动物&食肉动物&黄褐色&黑色条纹&”,＂老虎”,0　},
　 　 { ４，＂有蹄类哺乳动物&有长脖子＆有长腿&有暗斑&＂,"长颈鹿",0 ｝,
ﻩ 　　 ｛ 2，”有蹄类哺乳动物&黑条纹&",＂斑马",0 ｝，
{ 5，"鸟＆不会飞&有长脖子＆有长腿&黑白色＆","鸵鸟"，0 },
ﻩ　 　　 { 4,"鸟&不会飞&会游泳＆黑白色&"，”企鹅”，0 ｝,
　　 { 2,"鸟&会飞&"，"信天翁”,0 ｝,
ﻩ 　 　 {　1,”反刍","哺乳动物",0　}
};
inｔ numbeｒ;
int　m;
ｉnt cat = １5；
iｎt　a；
int lengｔh;ﻩﻩ ﻩ ／/输入得事实长度
sｔrinｇ f[２55］； ﻩﻩﻩ/／输入得事实数组
ｖoiｄ　inｐut(）
｛
　 wｈile (1)
　 　　　{
ﻩ cat++;
cout 〈〈 ”number＂ <〈　endｌ；
ﻩ ｃｉｎ 〉> r[cat］、cｏunt；
　cｏut 〈< "输入事实,两种以上得事实请在每个事实后加上‘&’符号＂　〈< endl；
　ciｎ 〉>　r［caｔ]、prｅ;
ﻩ 　 ｃout 〈< ”输入结果” 〈〈 endl;
ｃiｎ ＞〉 r［cat]、ｂack;
ﻩﻩ r[cａt]、ｍａrk = 0；
ﻩﻩ 　whilｅ （1）
ﻩ 　{
ﻩﻩ cｏut ＜< ”输入“1"继续添加规则，输入“2”查瞧规则库＂ 〈< ｅnｄl;
ﻩﻩﻩint p;
ﻩcｉn 〉> p;
ﻩﻩif （p ＝=　1)
ﻩﻩ {
ﻩ ﻩ ｉｎpｕt（)；
ﻩﻩﻩ｝
ﻩ else
ﻩﻩﻩ{
ﻩ ｉf (p ＝=　2）
ﻩﻩ {
ﻩﻩ ﻩ ｃheck(）；
ﻩ ｝
ﻩ ﻩﻩｅlｓe
ﻩ ﻩ {
ﻩ ﻩcｏut　＜〈 "输入错误，重新输入＂ 〈〈 ｅndl;
ﻩﻩﻩﻩ}
ﻩﻩﻩ }
ﻩ 　　 　}
　 }
} 　　 　
vｏiｄ ｄelate()
｛
cout 〈< "输入要删除得条数" 〈< endl;
ﻩ 　 int bar;
ﻩ 　ｃｉn　>＞ bａr;
　　 for (ｉnt ｔ = 0； ｔ 〈=　caｔ; t++)
ﻩ 　　｛
ﻩ r［ｂaｒ — 1] =　r[baｒ]；
bａr+＋;
}
ﻩ 　cat——;
ﻩ 　 cheｃｋ();
}
voｉd ｃｈeｃk()
｛
cout 〈< endl　<〈 ”规则库如下” 〈< endl;
for （int ｉ = 0; i　〈= cａt; i＋+)
ﻩ {
cｏｕt <<　i + １ <＜ ”、” ＜＜ "由＂ 〈〈 ｒ[i]、pｒｅ 〈< ”可得" 〈< r[i］、ｂacｋ　<〈　endｌ;
}
ﻩ　 cｏut ＜< endl;
ﻩ　 ｗｈiｌe (1)
　　{
ｃout <〈　”输入“1”继续添加规则，输入“3”删除选定得规则" ＜〈　endｌ;
ﻩ cin　>> m;
ﻩﻩ if (ｍ　== １)
ﻩ {
ﻩ input(）;
}
ﻩﻩ　elｓｅ
ﻩ 　{
ﻩ ｉf　(m == 3)
ﻩ ﻩdｅlａｔｅ（);
}
ﻩ　 ｝
｝
iｎt find_ｒule(iｎt　s) ﻩ//查找规则库中就是否还有可使用得规则
{
ﻩfｏr (int i = ０; ｉ <＝ 15; ｉ++)
ﻩﻩs = s*ｒ［ｉ］、mａrk;
/／ｃout<〈”ｆind＿rule结果”＜<ｓ<<endl;
ﻩｒeturｎ s；
}
inｔ paｒe1（RULES r） 　//当前提条件为1时
{
int j ＝ 0，　i =　1;
sｔring str, ｓｔｒ２；
sｔr = r、pｒe；
ｗhile (i　〈= length)
ﻩ{
ﻩ ｉf　(f［i] == sｔｒ)
ﻩ {
ﻩ sｔr2　=　r、ｂａｃk；
f[ｌength +　1]　＝ stｒ2；ﻩ //加入事实库
ﻩﻩﻩlｅｎgtｈ++; ﻩ ／/事实库得长度加1
ﻩ ﻩr、mａrk　＝　１； ﻩﻩ/／标记规则已使用过
ﻩﻩ breａk；
ﻩ｝
elsｅ
ﻩ ﻩi＋＋;
}
ﻩrｅturｎ r、mark;
}
int pare2(RULＥS r） ﻩ/／前提条件不为1
{
striｎg b[1０];
sｔｒinｇ str， ｓｔr2;
ﻩint i， j ＝　1, num = 0;
ﻩint a = ０;
str = r、pre;
ﻩfor (i ＝ 0; i ！= 10； ＋+ｉ) 　/／转换数组
ﻩ{
b［ｉ］ =　”"；
}
ﻩfor (i =　0; i !＝ str、lenｇth()； ++i)
ﻩ｛
ﻩﻩif　(sｔr、aｔ（ｉ) !＝　'&')
{
ﻩﻩﻩｂ［ｊ] += str、ａｔ(ｉ);
ﻩ｝
ﻩﻩｅlse
ﻩ ｛
j++;
ﻩ ｝
ﻩ}
ﻩi = 1；
ﻩｗhile　（ｉ　<＝ r、ｃoｕｎt）
{
ﻩfｏr (j ＝ １; j　！= ｌengｔh　+　1; j＋+)
ﻩ｛
ﻩﻩ if　(ｆ[j]　==　b[i])
ﻩﻩﻩ｛
ﻩ ａ += 1;
ﻩﻩﻩ｝
ﻩ ｝
ﻩi+＋；
ﻩ｝
ﻩｉｆ （a　==　r、count）
{
sｔr2 ＝ r、bacｋ;
ﻩﻩf[leｎgtｈ +　1］ ＝ ｓｔr２; ﻩ ／/加入事实库
ﻩ lenｇth++；ﻩ ﻩﻩ ／/事实库得长度加1
ﻩr、mark ＝ 1; //标记规则已使用过
}
ﻩrｅturn　r、marｋ;
}
void　result(）
{
ﻩint i = 1，　m ＝ 0；
whｉｌｅ (i !＝ length + 1)
{
ﻩﻩiｆ　(f[ｉ］　＝= ”金钱豹")
ﻩ｛
ﻩ ｃｏuｔ <〈 ”该动物就是金钱豹" ＜〈 endl;
ﻩ ﻩm = 1；
ﻩ ﻩbreａk;
ﻩ }
ﻩ elｓｅ
ﻩﻩiｆ (f［i] ＝＝ "老虎”）
ﻩﻩ｛
ﻩ ﻩ cout 〈＜ "该动物就是老虎" 〈〈　endl;
ﻩﻩｍ　＝ １；
ﻩ ﻩﻩbｒｅak;
ﻩ ﻩ｝
ﻩ elsｅ
ﻩﻩﻩﻩiｆ (f［i] == ”长颈鹿")
ﻩ ｛
ﻩ cout 〈< "该动物就是长颈鹿" <〈　endl；
ﻩﻩm = 1;
ﻩ ﻩbｒeａｋ;
ﻩ }
ﻩﻩﻩelｓe
ﻩ ﻩ if (f[i] ==　"斑马”)
ﻩﻩ ｛
ﻩ ﻩcｏｕt << "该动物就是斑马" << ｅndl；
ﻩﻩ ﻩ ﻩm = １;
ﻩ break;
ﻩ ﻩ ﻩ｝
ﻩﻩﻩﻩelse
ﻩ ﻩ if （f[i］　=＝ ＂鸵鸟")
ﻩﻩ ﻩﻩ {
ﻩ ﻩ ﻩｃout　〈〈 "该动物就是鸵鸟" 〈〈　ｅnｄl;
ﻩﻩﻩﻩ ﻩｍ ＝ 1;
ﻩﻩ ﻩbreak；
ﻩﻩﻩﻩ }
ﻩﻩﻩ ﻩelse
ﻩﻩﻩ ﻩﻩﻩiｆ (ｆ[i］ ==　”企鹅"）
ﻩ ﻩ ﻩﻩﻩ{
ﻩ ﻩ ﻩｃout 〈〈 ”该动物就是企鹅" <〈 endl;
ﻩﻩﻩ m ＝ 1;
ﻩﻩ ﻩ break；
ﻩ ﻩ ﻩﻩ}
ﻩﻩ ﻩﻩｅlse
ﻩﻩ ﻩﻩﻩ ﻩif　(f[ｉ] ==　＂信天翁"）
ﻩ ﻩﻩ ﻩﻩ {
ﻩ ﻩ ﻩ cｏut　<< "信天翁" 〈〈　enｄｌ;
ﻩﻩ ﻩﻩ ﻩm =　１；
ﻩﻩ ﻩﻩﻩ ﻩ break；
ﻩ ﻩ }
ﻩﻩﻩﻩﻩ else
ﻩ ﻩ ﻩ i++;
}
ﻩiｆ (ｍ　==　０)
ﻩ cｏut ＜<　”没有符合得动物，请确认特征，重新输入”　＜< ｅndl;
｝
ｖｏid ｉｄetify()
｛
ﻩint　i = 0, u = 0;
ﻩｉf　(ｆind＿ｒule（ｕ) == 0) 　 　 　//如果规则库中还有未使用得规则
ﻩ{／/cout〈〈＂还有未使用得规则＂<＜eｎdl;
ﻩﻩint nuｍ =　lengｔh；
ﻩﻩwhｉlｅ （i〈１6)ﻩﻩﻩﻩﻩ/／从第一条规则开始遍历
｛
ﻩﻩﻩif (r［ｉ]、marｋ =＝　0)ﻩ ﻩ//如果该条规则未使用
ﻩ ｛
if　(ｒ［i]、cｏunt ==　1) ﻩ //该条规则前提数为1
ﻩﻩﻩ {
ﻩﻩ u = pare1(ｒ[i]）;
ﻩ if （ｕ =＝ 1)
ﻩﻩﻩﻩﻩr[ｉ]、mark　=　１；
ﻩ ﻩ ｉf (r[i]、ｍaｒk == 1)
ﻩﻩﻩ{
ﻩ ｃout << ”使用规则＂ <〈 ｉ +　1；
ﻩ ﻩcｏuｔ 〈〈　”且加入得新事实为”　〈〈 r［i]、ｂaｃｋ ＜〈 endl；
ﻩﻩﻩ ｝
ﻩ ﻩ ｝
ﻩ ﻩｅlse
ﻩ ﻩ{
ﻩﻩﻩ ﻩu = pare2(r[i]);
ﻩ ﻩﻩiｆ　（ｕ ==　1)
ﻩ ﻩﻩ r［i］、mａrk = 1;
if （r[i］、mａｒk == 1)
ﻩﻩ ﻩ {
ﻩﻩﻩ ｃoｕt << ”使用规则”　<<　i + 1;
ﻩﻩ ﻩ ｃoｕｔ 〈< "且加入得新事实为" <〈 ｒ[i]、bacｋ　〈< endl；
ﻩﻩ ｝
ﻩ ﻩ }
ﻩ }
ﻩ if （i == 15)
ﻩ ﻩ{
ﻩﻩ ｉf (nuｍ !=　ｌength)
ﻩ｛
ﻩ ﻩﻩﻩｉ = 0；
ﻩﻩﻩﻩﻩnum　＝ length;
ﻩ}
ﻩ elsｅ
ﻩﻩﻩ i =　１6；
ﻩ }
ﻩﻩ eｌｓｅ
ﻩﻩ {
ﻩ ｉ++;
ﻩ }
}
}
ﻩelse
ﻩ{
cｏut　〈〈　”所有得规则都已使用”　〈〈 ｅｎｄl；
ﻩ｝
ﻩｒesult（);
｝
/*主函数*／
void ｍain(）
｛
ﻩcｏuｔ　<〈 "＊*****智能1５01班＊＊＊*****”　〈〈 endl；
ﻩcｏuｔ <〈 "***＊＊＊061５3０34****＊＊＊*＊*” <〈 endl；
cout <〈　”*＊****刘少鹏＊**＊*＊******” <<　enｄｌ;
cｏut 〈＜ ”进行动物识别请输入7” 〈＜ endl;
ｃｏut　〈〈 ”进行规则库操作请输入8"　<< eｎｄｌ;
ﻩciｎ　＞〉 a；
ﻩwhile (a == 8)
｛ 　 while (１）
ﻩ ｛
ﻩﻩcｏｕｔ　〈〈 ”添加规则输入‘1’,查瞧已有规则输入‘2'”　〈〈 ｅｎdｌ；
ﻩ cin　>> m;
ﻩ ｉｆ （ｍ ==　１)
ﻩ｛
ﻩ iｎｐｕｔ（);
}
ﻩﻩelse
ﻩ {
ﻩﻩﻩif (ｍ == 2)
ﻩ {
ﻩ ｃheck();
ﻩ ﻩ｝
ﻩ ﻩ elｓe
ﻩ ﻩcout 〈< ”输入错误请重新输入” 〈<　ｅndl;
ﻩ }
｝
｝
　 if （ａ == 7)
ﻩ{
inｔ u = 0;
ﻩcout 〈＜ "请输入动物得特征数" <〈 endl;
ﻩ ｃin 〉〉 length;
ﻩ cout << ＂请输入动物得特征”　〈＜　eｎdｌ;
ﻩfor （ｉnt i = 1; ｉ 〈＝ lengｔh； i++)
ﻩ ﻩｃｉｎ 〉〉 ｆ［ｉ］；
ﻩ idetiｆy();
}
ﻩsystem（”ｐauｓe”);
｝
五、 实验结果相关截图
1、程序总体结构

2、 规则库操作→查瞧规则库

3、 规则库操作→添加规则→添加袋鼠规则

4、 规则库操作→删除规则→删除袋鼠规则

5、动物识别→识别长颈鹿

六、心得体会
　 通过本次实验我深刻得理解与掌握产生式知识表示方法，并且能够通过VC编程语言实现产生式系统得规则库.本次实验我同样遇到许多问题,我通过自己查阅资料,与同学们讨论,逐步得将自己得问题解决,在这个过程中提高了我得问题解决能力。最后因为本次实验只有对数据库有清楚得掌握,同时熟悉规则才能合理编程，因此我在平时得学习中应当加大数据库与数据结构得学习力度，提高自己得编程能力。

人工智能课内实验报告
实验3:盲目搜索求解八数码问题
学 　院:　　　　 自动化学院　　 　 　 　
班 　 级: 　 智能150１ 　　 　 　
姓 　名: 　 刘少鹏 (3３） 　
学　 　 号: 　 061５3034 　 　 　 　
日 期： ２0１7-03—３0 １0：１５—１2：０0
人工智能课内实验3:盲目搜索求解8数码问题
1、 实验目得
(1) 熟悉人工智能系统中得问题求解过程；
(2) 熟悉状态空间中得盲目搜索策略;
(3) 掌握盲目搜索算法,重点就是宽度优先搜索与深度优先搜索算法.
2、 实验要求
用VC语言编程，采用宽度优先搜索与深度优先搜索方法,求解8数码问题
3、 实验内容
（1） 采用宽度优先算法,运行程序,要求输入初始状态
假设给定如下初始状态S0
2 　8　 3
1 ６ 4
7 ０　 5
　 　 与目标状态Sg
　 　 2 　1 　6
　　 　 　 4 0 8
　 ７ 5 3
　 　 验证程序得输出结果,写出心得体会。
　　 (2)对代码进行修改(选作),实现深度优先搜索求解该问题
提示:每次选扩展节点时,从数组得最后一个生成得节点开始找，找一个没有被扩展得节点。这样也需要对节点添加一个就是否被扩展过得标志。
4 源代码及实验结果截图
（1） 实验源代码
＃incｌｕｄe 〈sｔdlｉb、h〉
＃ｉｎｃlｕｄe <stdio、ｈ>
Ｔyｐedef strｕｃｔ Ｎｏｄe { inｔ　nｕm［9]； //棋盘状态
　 　 　 ｉｎt　dｅepth; //派生得深度　g（n)
　　　 　 　 　 inｔ　diffnum；　//不在位得数目 h(n)
　　 　 　　 　inｔ ｖalｕe; /／耗散值 f(n)=g(n)＋h(n)
　 stｒucｔ Ｎｏde　* ｐrｅ;
ﻩ 　　 　　 　 　 　 　 ｓtruct Noｄe ＊ next;
　 　　 　 　 　 strucｔ Nｏde ＊ pａｒent;
}ｎuｍＮodｅ；　　 /*　-- ｅnd of strｕｃt nuｍNｏde　—— ＊／
inｔ oｒiｇiｎ[9］; //棋盘初始状态
int ｔargeｔ[9];　//棋盘目标状态
ｉnt nuｍNoｄe_num, totaｌ_ｓtep；
numNode *opeｎ, ＊close; //Oｐeｎ表与Close表
ｎｕmNoｄe *create_nｕmNoｄe()
{
ﻩ rｅtｕrn （ｎumNｏｄe　*)mａｌｌoｃ(sizｅof（nｕｍNode））;
｝
nuｍNoｄe ＊ｏpｅｎ＿ｇetｆｉrst（ｎumNoｄe *head）； //返回第一项，并从Opｅｎ表中删除
ｖoiｄ　oｐen＿insert(numNodｅ ＊heａd, numNoｄe *itｅm）; ／/向Opeｎ表中按序插入新节点
ｖｏｉd　cloｓe_aｐｐeｎｄ(numNode　＊heａd， nｕmNode *itｅｍ); //向Cｌｏｓe表中插入新节点
int exｐaｎｄ（numＮodｅ ＊item）; //扩展节点
int pｒｉnt_resｕlt（numＮｏde *itｅm）； ／/打印结果
nuｍＮｏｄｅ ＊copy_ｎｕmNｏde(numNode ＊ｏｒｇｉn);
char　ｉsNewNode（nｕmNoｄe *open,　numNoｄe *cｌosｅ, ｉｎｔ num［9]);　//就是否在Open表或Clｏsｅ表中
voiｄ prinｔ_num(int ｎuｍ［9］）; //打印棋盘状态
int　ｄiｆf(ｉｎt nｕm[9]）; ／/求不在位棋子得个数
voｉｄ ｉniｔ（); ／／初始化，获得棋盘初始状态与目标状态
voｉd s　*ａ， ｉnt　＊ｂ);
ｉnt opｅrate(int ｎum［]， int ｏｐ）;
voｉd fｒee_list（nuｍＮode *heaｄ）;
//* Naｍｅ:　主函數
//* Description： 程序入口
int mａｉｎ(int aｒgc,　chaｒ　＊argv［］）
｛
//初始化Oｐeｎ表与Ｃloｓe表
ﻩ　 printf（”＊****智能1501**＊*\n");
　　ｐrｉntｆ("*＊＊**刘少鹏*＊*＊**\ｎ”)；
ﻩ pｒｉｎtf("****＊０６1５3034****＼n”)；
ﻩ ｏpen ＝ create_nuｍNｏdｅ（);
clｏse = creaｔe_nuｍNoｄe(）；
ﻩ open－〉pre　= open-＞next　＝ close—>pre　= ｃlose—〉ｎext =　NULL；
ﻩ　 ｉnit（); /／由用户输入初始与目标状态
ﻩ ﻩ//初始化初始节点
ﻩ　 numＮodｅ *p1;
ﻩ　 p１ = create_numNｏｄｅ（);
ﻩ 　p1-〉pａｒｅnt ＝ NULＬ;
ﻩ 　p1—〉deｅpｔh　=　0;
ﻩ iｎｔ i =　0；
　ｆor　(ｉ = 0; i〈９； i++)
ﻩ {
ﻩﻩ p1—>nuｍ[i］ = orｉｇiｎ［ｉ];
ﻩ　 }
ｏpeｎ_ｉｎsert(ｏpｅn, p1）；
ｎuｍNｏde＿ｎum = 1;
　ｐ１ ＝ opeｎ_ｇeｔfirsｔ(ｏｐen）；
whiｌe (p１　！= NUＬＬ）
｛
ﻩﻩ close＿aｐｐenｄ（ｃｌose, p1);
ﻩ if （expand(p１))
ﻩreturn EXＩＴ_ＳＵＣCESＳ；
p１ = oｐeｎ＿gｅtｆiｒst(open);
　}
ﻩ priｎｔf（”No ｓｏlｕtion!＼ｎ＂);
rｅtuｒn ＥXＩT_SUＣＣEＳＳ;
} 　 　 　　 ／* -—--－-—--- eｎd of fuｎctｉon maiｎ -——--——－-— */
vｏｉd iｎit(）
{
whilｅ （1）
ﻩ｛
priｎtf（”Ｐｌease ｉnput oprｉginａl sｔatus：\nFor example:123456780 stanｄs fｏr\n＂
ﻩ”1 2 　　 3\n”
ﻩ ”４　　 　5 6\ｎ”
ﻩ ﻩ”7 　 8 　0＼ｎ”）;
ﻩcｈar temp[10];
ﻩﻩｓｃanｆ（”％ｓ", &tｅｍp);
int i =　０;
ﻩfoｒ （i = 0； i〈9　&& ｔemp[ｉ］ － ’0’　〉＝ 0 &＆ temp[ｉ］　- '0’ 〈=　8; i++)
ﻩﻩ{
orｉgin[i] =　ｔeｍp[ｉ］　- '0＇;
ﻩ }
ｐrintf("Please inｐut　target sｔatus:\n”)；
ﻩscaｎf("%s＂,　&temp）；
ﻩﻩint j =　０；
ﻩﻩfoｒ (ｊ =　0； ｊ〈9　&＆ ｔemp[ｊ] - '0' 〉= 0　&& temｐ[j]　- ＇0＇　<= ８;　j+＋)
ﻩ {
ﻩﻩtａrget[j］ = temp[j] — ’0’；
ﻩ}
ﻩsｙsｔem（＂cｌs");
ｉｆ (i ＝＝ 9 ＆& j == ９）
｛
ﻩ ﻩbreak；
}
｝
｝ 　 　 /* —--—— ｅｎｄ ｏf function ｉｎit　—－—-—　＊/
void　opeｎ_inｓert（numNode *head, numNｏde ＊iｔeｍ）
{
ﻩnｕmNoｄe *p, *q；
ﻩp　＝ head—>next;
ｑ = hｅａd;
ﻩwhile （ｐ　!= NUＬL ＆＆ ｉtｅm—>vａlue　〉 p－〉value）
｛
ﻩﻩq = ｐ;
ﻩｐ = p-〉next;
}
ｑ—>neｘt = item;
ﻩiteｍ-〉prｅ = ｑ;
ﻩiteｍ-＞next　= ｐ；
ｉf （ｐ ！= NＵＬL）
ﻩ{
ﻩﻩp—>prｅ = ｉtem；
ﻩ}
}　 　 /* —－—-— end　oｆ　fｕｎｃtiｏn　opｅn_insｅrt —--—- ＊/
nｕｍNode *oｐｅｎ＿getfirst(ｎuｍNodｅ *head)
{
ﻩnumNoｄe ＊p；
ﻩif　(ｈｅaｄ-〉next　== ＮＵＬL)
ﻩ{
ﻩretuｒn ＮＵLＬ；
ﻩ}
p = heａd—〉nexｔ;
ﻩｈeaｄ-＞ｎｅxt　＝ ｐ->next；
if (p—〉neｘt != ＮULＬ)
ﻩ{
ﻩ p—>neｘｔ—〉pre = ｈead；
｝
p—〉pｒｅ ＝　NULL;
p-＞nexｔ　= NULＬ;
ﻩｒeturn p;
} /*　－—-——　eｎd　of funcｔion　ｏpen_getfirst -———— ＊/
void ｃlosｅ_appeｎd(nuｍＮoｄe　＊heａd， nuｍNｏde ＊item）
{
ﻩiｔem-〉nｅxt ＝ head—〉next;
ﻩitem—＞ｐｒe ＝ ｈeaｄ;
ｈｅａd－〉ｎｅxt = item；
ﻩiｆ (item－＞nexｔ ！= NULL)
{
ﻩﻩitem->nｅxt—＞ｐre = ｉtｅm；
ﻩ｝
} 　 　 /＊ ————- eｎd　of fｕnｃtion close_append　-—－—－ *／
iｎｔ　eｘpand（numNｏde ＊p１)
｛
numNｏｄe ＊ p２;
int op = １;
ﻩfｏr (op ＝ 1; ｏp ＜=　4； op++）
ﻩ｛
p２ ＝ ｃopy_numNoｄe（ｐ１）;
ﻩﻩｏpeｒａte(p2—〉nuｍ, op);
if (isNewＮode(open, cloｓｅ,　p2－〉num） ==　’N')
ﻩﻩ{
ﻩﻩﻩp2—〉parent　= ｐ1;
ﻩ p2-＞dｅepｔｈ　=　p1—＞dｅepth + １;
ﻩ ﻩp２-〉diｆfｎｕm = diｆｆ(p2->num);
ﻩp2—〉vａlue = ｐ2—>deｅpth ＋ p2—〉ｄiffnum;
ﻩﻩﻩｉf (ｐ2－〉diffnum　== 0）
ﻩ｛
ｔotal_stｅp　＝ pｒｉnt＿resulｔ(p２）;
ﻩ ﻩｐrintf（"Total step: %d＼n", total_ｓteｐ）;
ﻩｆree_list（open);
ﻩﻩ fｒee_lisｔ(ｃlｏｓe）；
ﻩ reｔurn 1；
ﻩ ﻩ}
ﻩﻩ elｓｅ
ﻩﻩﻩ{
ﻩｎumNode_num++;
opeｎ_ｉｎsｅｒt(ｏpｅn， p2）；
ﻩﻩ ｝
ﻩ}
ﻩ else
free(p2）；
｝
ｒeturn 0；
｝ 　　/＊ ——--— end ｏf fuｎｃｔiｏn expand　-—-—- */
inｔ operate(int　m[], int oｐ)
｛
ﻩint blank;
blank = 0;
ｗhile （ｍ[ｂlａnｋ］ != 0 &＆　ｂlａnk<9)
ﻩ ++blａnk;
if （bｌank == 9）
ﻩﻩreturn １;
ﻩsｗiｔch （ｏｐ) ｛
casｅ 1：　/* up */
ﻩif (blaｎk〉2）
ﻩswａｐ(m + blａnk， m +　ｂlａnk - ３）;
ｂreak；
case 2: /* ｄoｗｎ ＊／
ﻩﻩif (blank〈6）
ﻩﻩﻩswaｐ(m + blank, ｍ +　blａｎk + 3);
ﻩ ｂreａk;
ﻩcａse　3： /* lｅft　＊／
ｉf　（ｂlａnk !=　0 && blank　！＝ 3 && blank != 6）
ﻩ swap（m + blａｎk, m ＋ blanｋ — 1)；
ﻩbreak;
ｃase 4： /* ｒight ＊／
if　(ｂｌaｎk ！=　2 ＆＆ blank ！= 5　&＆　ｂlａnk != 8)
ﻩﻩﻩｓwap（m + blank, m ＋ blａnk + 1）;
ﻩ brｅaｋ;
defaｕｌｔ: ｒｅtｕrn 1;
}
ｒetｕrｎ 0;
}
void　s ＊a， int　*b）
{
inｔ　c;
c　＝ *a;
*a =　＊b；
ﻩ*b　=　c；
}
nｕmNoｄe ＊ copy_nuｍNoｄe(numNodｅ *ｏrigｉn)
{
nuｍNoｄe ＊ｐ;
ﻩp　＝ ｃreate＿numNode(）；
p—>ｄeepth　= oriｇin—〉deｅpth；
ｐ-〉diffnum = ｏrｉgin—>dｉffｎum;
ﻩｐ－〉vａlue =　origin-〉vａlue;
ｉnt ｉ;
ﻩfoｒ (i = ０; i<9; i++）
{
ﻩ (p->nuｍ)［i］　= (oriｇin－>ｎum)[ｉ]；
}
ﻩretｕrｎ p;
｝ 　　 /* -—－—— enｄ of fｕｎcｔion coｐy_nｕmNode ——-－— */
int
diff(ｉｎt　ｎum[9]）
{
ﻩint i， dｉｆfｎum = 0;
ﻩfｏｒ (ｉ ＝ 0； i〈9; i++)
ﻩｉf （ｎum［ｉ]　！＝ tａｒgｅt[i］)
ﻩ diｆｆnum++;
return diｆfnum;
｝ 　　 /* ——－-— end of　fｕnctiｏｎ ｄiｆf —－-—- ＊/
chａr
isＮｅwNoｄe(numNode ＊oｐen, ｎｕmＮodｅ ＊close， ｉnｔ nｕm［