資源簡介
z1. 綜合應用“深度優先搜索”、“寬度優先搜索”、“啟發式搜索”這三種人工智能搜索技術的基本知識以及程序設計的相關知識。
z2. 通過設計一個八數碼問題求解程序，學習、了解狀態空間搜索的思想，進一步加深對人工智能課程相關啟發式搜索的理解。
z實驗內容 1. 針對八數碼問題，在Windows環境下用C/C++語言(Java語言)實現幾種搜索算法(最好是圖形界面)：
y深度優先搜索 P23
y寬度優先搜索 P24
y啟發式搜索算法（h1(n) =W(n) “不在位”的將牌數）P28
y啟發式搜索算法（h2(n) = P(n)將牌“不在位”的距離和）P40
y啟發式搜索算法（h3(n) = h(n)＝P(n)+3S(n)） P46
2. 隨機產生或手動輸入初始狀態，對于同一個初始狀態，分別用上面的5種方法進行求解，并對比結果
代碼片段和文件信息
#include“8puzzle.h“
?
//主函數
int?main（）{
eightdigit?e;
e.init（）;
return?0;
}
//查找空格位置
int?eightdigit::findpos（int?a）{
int?pos?=?9;
while?（a?%?10?!=?0）{
pos--;
a?/=?10;
}
return?pos;
}
//下移操作
int?eightdigit::mDown（int?a?int?pos）{
if?（pos?>=?7）?return?0;//表明空格在第三一行，不能下移，返回0
int?b?=?a?/?p[pos?+?3];
b?=?b?%?10;????????????//空格下面的數碼位置為pos+3，找出對應位置的數碼值b
a?-=?b?*?p[pos?+?3];???//移動空格0到位置pos+3
a?+=?b?*?p[pos];???????//移動數碼值b到位置pos
if?（exist[a]?==?0）????
return?a;??????????//如果是新狀態，返回該狀態a，否則返回0
else?return?0;
}
//上移操作
int?eightdigit::mUp（int?a?int?pos）{
if?（pos?<=?3）?return?0;//表明空格在第一行，不能上移，返回0
int?b?=?a?/?p[pos?-?3];
b?=?b?%?10;????????????//空格上面的數碼位置為pos-3，找出對應位置的數碼值b
a?-=?b?*?p[pos?-?3];???//移動空格0到位置pos-3
a?+=?b?*?p[pos];???????//移動數碼值b到位置pos
if?（exist[a]?==?0）
return?a;??????????//如果是新狀態，返回該狀態a，否則返回0
else?return?0;
}
//左移
int?eightdigit::mLeft（int?a?int?pos）{
if?（pos?%?3?==?1）?return?0;//表明空格在第一列，不能左移，返回0
int?b?=?a?/?p[pos?-?1];????
b?=?b?%?10;????????????????//空格左面的數碼位置為pos-1，找出對應位置的數碼值b
a?-=?b?*?p[pos?-?1];???????//移動空格0到位置pos-1
a?+=?b?*?p[pos];???????????//移動數碼值b到位置pos
if?（exist[a]?==?0）?????????
return?a;??????????????//如果是新狀態，返回該狀態a，否則返回0
else?return?0;
}
//右移
int?eightdigit::mRight（int?a?int?pos）{
if?（pos?%?3?==?0）?return?0;//表明空格在第三列，不能右移，返回0
int?b?=?a?/?p[pos?+?1];????
b?=?b?%?10;????????????????//空格右面的數碼位置為pos+1，找出對應位置的數碼值b
a?-=?b?*?p[pos?+?1];???????//移動空格0到位置pos+1
a?+=?b?*?p[pos];???????????//移動數碼值b到位置pos
if?（exist[a]?==?0）
return?a;??????????????//如果是新狀態，返回該狀態a，否則返回0
else?return?0;
}
//深度優先搜索，遞歸調用
bool?eightdigit::dfs（int?a）{
if?（a?==?aim）?return?true;//找到目標狀態，返回ture
int?b;
expand[0]?+=?1;???????????//擴展結點數
int?pos?=?findpos（a）;?????//查找狀態a空格所在的位置pos
b?=?mDown（a?pos）;????????//當前空格下移，得到新狀態b
if?（b）{
exist[b]?=?a;?????????//映射，狀態a生成狀態b
create[0]?+=?1;???????//生成結點數
if?（dfs（b））?return?true;//遞歸調用
}
b?=?mUp（a?pos）;????????
if?（b）{
exist[b]?=?a;
create[0]?+=?1;
if?（dfs（b））?return?true;
}
b?=?mLeft（a?pos）;
if?（b）{
exist[b]?=?a;
create[0]?+=?1;
if?（dfs（b））?return?true;
}
b?=?mRight（a?pos）;
if?（b）{
exist[b]?=?a;
create[0]?+=?1;
if?（dfs（b））?return?true;
}
return?false;
}
//寬度優先搜索，隊列處理
bool?eightdigit::bfs（int?a）{
int?b;
while?（!qopen.empty（））
qopen.pop（）;
qopen.push（a）;
while?（!qopen.empty（））{
a?=?qopen.front（）;????//取狀態a進行擴展
qopen.pop（）;
if?（a?==?aim）{
return?true;??????//找到目標狀態，返回ture
}
expand[1]++;??????????//擴展結點數
int?pos?=?findpos（a）;?//查找狀態a空格所在的位置pos
b?=?mDown（a?pos）;????//當前空格下移，得到新狀態b
if?（b）{
exist[b]?=?a;?????//映射，狀態a生成狀態b
create[1]?+=?1;???//生成狀態數
qopen.push（b）;????//新狀態b入棧
}
b?=?mUp（a?pos）;
if?（b）{
exist[b]?=?a;
create[1]?+=?1;
qopen.push（b）;
}
b?=?mLeft（a?pos）;
if?（b）{
exist[b]?=?a;
create[1]?+=?1;
qopen.push（b）;
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????3537834??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\8?puzzle?solution?path.txt
?????文件???????8120??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\8?puzzle.cpp
?????文件???????3993??2017-05-30?17:45??【170518】8?puzzle\8?puzzle\8?puzzle.vcxproj
?????文件???????1066??2017-05-30?17:45??【170518】8?puzzle\8?puzzle\8?puzzle.vcxproj.filters
?????文件????????143??2017-05-06?22:33??【170518】8?puzzle\8?puzzle\8?puzzle.vcxproj.user
?????文件???????1815??2017-05-30?17:50??【170518】8?puzzle\8?puzzle\8puzzle.h
?????文件????????406??2017-05-18?09:02??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.exe.em
?????文件????????472??2017-05-18?10:41??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.exe.em
?????文件????????381??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.exe.intermediate.manifest
?????文件?????????69??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.lastbuildstate
?????文件???????2604??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.log
?????文件?????594806??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.obj
?????文件????????713??2017-05-27?10:51??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.vcxprojResolveAssemblyReference.cache
?????文件??????????0??2017-05-18?10:41??【170518】8?puzzle\8?puzzle\Debug\8?puzzle.write.1.tlog
?????文件????????206??2017-05-18?09:02??【170518】8?puzzle\8?puzzle\Debug\8?puzzle_manifest.rc
?????文件???????1434??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\cl.command.1.tlog
?????文件??????25358??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\CL.read.1.tlog
?????文件????????858??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\CL.write.1.tlog
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件??????????2??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件???????3266??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
?????文件???????6128??2017-05-31?11:06??【170518】8?puzzle\8?puzzle\Debug\li
............此處省略25個文件信息
- 上一篇：網上購物系統+畢業設計（完整版）
- 下一篇：獎學金管理系統源碼
評論
共有 條評論
川公網安備 51152502000135號