一、實驗目的

本實驗課程是計算機、智能、物聯(lián)網(wǎng)等專業(yè)學生的一門專業(yè)課程，通過實驗，幫助學生更好地掌握人工智能相關概念、技術、原理、應用等；通過實驗提高學生編寫實驗報告、總結實驗結果的能力；使學生對智能程序、智能算法等有比較深入的認識。本實驗通過不同知識的表達與推理問題，強化學生對知識表示的了解和應用，為人工智能后續(xù)環(huán)節(jié)的課程奠定基礎。

二、基本要求

1、實驗前，復習《人工智能》課程中的有關內容。

2、準備好實驗數(shù)據(jù)。

3、編程或驗證需要獨立完成，程序應加適當?shù)淖⑨尅?/p>

4、完成實驗報告。

三、實驗軟件

使用C或C++（Visual?studio平臺等）,或其它語言,如matlab或Python。

四、實驗內容：

（一）猴子摘香蕉問題

利用一階謂詞邏輯求解猴子摘香蕉問題：房內有一個猴子，一個箱子，天花板上掛了一串香蕉，其位置如圖1所示，猴子為了拿到香蕉，它必須把箱子搬到香蕉下面，然后再爬到箱子上。請定義必要的謂詞，列出問題的初始化狀態(tài)（即下圖所示狀態(tài)），目標狀態(tài)（猴子拿到了香蕉，站在箱子上，箱子位于位置b）。（附加：從初始狀態(tài)到目標狀態(tài)的謂詞演算過程。）?

1、定義描述環(huán)境狀態(tài)的謂詞。

AT(x,w)：x在w處，個體域：x?{monkey}，w?{a,b,c,box}；

HOLD(x,t)：x手中拿著t，個體域：t?{box,banana}；

EMPTY(x)：x手中是空的；

ON(t,y)：t在y處，個體域：y?{b,c,ceiling}；

CLEAR(y)：y上是空的；

BOX(u)：u是箱子，個體域：u?{box}；

BANANA(v)：v是香蕉，個體域：v?{banana}；

2、使用謂詞、連結詞、量詞來表示環(huán)境狀態(tài)。

問題的初始狀態(tài)可表示為：So：AT(monkey,a)->EMPTY(monkey)->ON(box,c)->ON(banana,ceiling)->CLEAR(b)->BOX(box)->BANANA(banana)

要達到的目標狀態(tài)為：Sg：AT(monkey,box)->HOLD(monkey,banana)->ON(box,b)->CLEAR(ceiling)->CLEAR(c)->BOX(box)->BANANA(banana)

3、從初始狀態(tài)到目標狀態(tài)的轉化, 猴子需要完成一系列操作, 定義操作類謂詞表示其動作。

WALK(m,n)：猴子從m走到n處，個體域：m,n?{a,b,c}；

CARRY(s,r)：猴子在r處拿到s，個體域：r?{c,ceiling}，s?{box,banana}；

CLIMB(u,b)：猴子在b處爬上u；

這3個操作也可分別用條件和動作來表示。條件直接用謂詞公式表示，是為完成相應操作所必須具備的條件；當條件中的事實使其均為真時，則可激活操作規(guī)則，于是可執(zhí)行該規(guī)則中的動作部分。動作通過前后狀態(tài)的變化表示，即通過從動作前刪除或增加謂詞公式來描述動作后的狀態(tài)。

4、按照行動計劃, 一步步進行狀態(tài)替換, 直至目標狀態(tài)

AT(monkey,a)?EMPTY(monkey)?ON(box,c)?ON(banana,ceiling)?CLEAR(b)?BOX(box)?

BANANA(banana)

AT(monkey,c)?EMPTY(monkey)?ON(box,c)?ON(banana,ceiling)?CLEAR(b)?BOX(box)?

BANANA(banana)

AT(monkey,c)?HOLD(monkey,box)?ON(banana,ceiling)?CLEAR(b)?CLEAR(c)?BOX(box)?

BANANA(banana)

AT(monkey,b)?HOLD(monkey,box)?ON(banana,ceiling)?CLEAR(b)?CLEAR(c)?BOX(box)?

BANANA(banana)

AT(monkey,box)?EMPTY(monkey)?ON(box,b)?ON(banana,ceiling)?CLEAR(c)?BOX(box)?

BANANA(banana)

AT(monkey,box)?HOLD(monkey,banana)?ON(box,b)?CLEAR(ceiling)?CLEAR(c)?BOX(box)?

BANANA(banana)（目標得解）

猴子行動的規(guī)則序列是：WALK(a,c)→CARRY(c,box)→WALK(c,b)→CLIMB(box,b)→

CARRY(banana,ceiling)

5、參考代碼：

#include <stdio.h>
struct State
{int monkey; /*-1:Monkey at A;0: Monkey at B;1:Monkey at C;*/int box; /*-1:box at A;0:box at B;1:box at C;*/int banana; /*Banana at B,Banana=0*/int monbox; /*-1: monkey on the box;1: monkey  the box;*/
};
struct State States [150];
char* routesave[150];
/*function monkeygoto,it makes the monkey goto the other place*/
void monkeygoto(int b,int i)
{  int a;a=b;if (a==-1){routesave[i]="Monkey go to A";States[i+1]=States[i];States[i+1].monkey=-1;}else if(a==0){routesave[i]="Monkey go to B";States[i+1]=States[i];States[i+1].monkey=0;}else if(a==1){routesave[i]="Monkey go to C";States[i+1]=States[i];States[i+1].monkey=1;}else{printf("parameter is wrong");}
}
/*end function monkeyygoto*/
/*function movebox,the monkey move the box to the other place*/
void movebox(int a,int i)
{  int B;B=a;if(B==-1){routesave[i]="monkey move box to A";States[i+1]=States[i];States[i+1].monkey=-1;States[i+1].box=-1;}else if(B==0){routesave[i] = "monkey move box to B";States[i+1]=States[i];States[i+1].monkey=0;States[i+1].box=0;}else if(B==1){routesave[i] = "monkey move box to C";States[i+1]=States[i];States[i+1].monkey=1;States[i+1].box=1;}else{printf("parameter is wrong");}
}
/*end function movebox*/
/*function climbonto,the monkey climb onto the box*/
void climbonto(int i)
{routesave[i]="Monkey climb onto the box";States[i+1]=States[i];States[i+1].monbox=1;
}
/*function climbdown,monkey climb down from the box*/
void climbdown(int i)
{  routesave[i]="Monkey climb down from the box";States[i+1]=States[i];States[i+1].monbox=-1;
}
/*function reach,if the monkey,box,and banana are at the same place,the monkey reach banana*/
void reach(int i)
{   routesave[i]="Monkey reach the banana";
}
/*output the solution to the problem*/
void showSolution(int i)
{int c;printf ("%s \n", "Result to problem:");for(c=0; c<i+1; c++){printf ("Step %d : %s \n",c+1,routesave[c]);}printf("\n");
}
/*perform next step*/
void nextStep(int i)
{int c;int j;if(i>=150){printf("%s  \n", "steplength reached 150,have problem ");return;}for (c=0; c<i; c++) /*if the current state is same to previous,retrospect*/{if(States[c].monkey==States[i].monkey&&States[c].box==States[i].box&&States[c].banana==States[i].banana&&States[c].monbox==States[i].monbox){return;}}if(States[i].monbox==1&&States[i].monkey==0&&States[i].banana==0&&States[i].box==0){showSolution(i);printf("Press any key to continue \n");getchar();/*to save screen for user,press any key to continue*/return;}  j=i+1;    if(States[i].monkey==0){ if(States[i].box==0){if(States[i].monbox==-1){climbonto(i);reach(i+1);nextStep(j);/*monkeygoto(-1,i);nextStep(j);monkeygoto(0,i);nextStep(j);movebox(-1,i);nextStep(j);movebox(0,i);nextStep(j);*/}else{reach(i+1);nextStep(j);/*climbdown(i);nextStep(j);*/}}else if(States[i].box==1){/*monkeygoto(-1,i);nextStep(j);*/monkeygoto(1,i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}else /*box==-1*/{monkeygoto(-1,i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}}/*end if*/if(States[i].monkey==-1){ if(States[i].box==-1){if(States[i].monbox==-1){ movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}else{climbdown(i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}}else if(States[i].box==0){ monkeygoto(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}else{monkeygoto(1,i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}}/*end if*/if(States[i].monkey==1){	if (States[i].box==1){if(States[i].monbox==-1){     movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}else{climbdown(i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);          }}else if(States[i].box==-1){        monkeygoto(-1,i);nextStep(j);movebox(0,i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}else{monkeygoto(0,i);nextStep(j);movebox(0,i);nextStep(j);climbonto(i);reach(i+1);nextStep(j);}}/*end if*/
}/*end nextStep*/
int main()
{States[0].monkey=-1;States[0].box=1;States[0].banana=0;States[0].monbox=-1;nextStep(0);
}

（二）傳教士(牧師)與野人問題

問題描述：

有n個牧師和n個野人準備渡河，但只有一條能容納c個人的小船，為了防止野人侵犯牧師，要求無論在何處，牧師的人數(shù)不得少于野人的人數(shù)(除非牧師人數(shù)為0)，且假定野人與牧師都會劃船，試設計一個算法，確定他們能否渡過河去，若能，則給出小船來回次數(shù)最少的最佳方案。

實驗步驟：

輸入：牧師人數(shù)(即野人人數(shù))：n；小船一次最多載人量：c。 ?

輸出：若問題無解，則顯示Failed，否則，顯示Successed輸出所有可行方案，并標注哪一組是最佳方案。用三元組(X1, X2, X3)表示渡河過程中的狀態(tài)。并用箭頭連接相鄰狀態(tài)以表示遷移過程：初始狀態(tài)->中間狀態(tài)->目標狀態(tài)。???

例：當輸入n=2，c=2時，輸出：221->200->211->010->021->000； ?

其中：X1表示起始岸上的牧師人數(shù)；X2表示起始岸上的野人人數(shù)；X3表示小船現(xiàn)在位置(1表示起始岸，0表示目的岸)。

要求：寫出算法的設計思想和源程序，并有用戶界面實現(xiàn)人機交互（控制臺或者窗口都可以），進行輸入和輸出結果，如：

Please input n: 2 ????????Please input c: 2

Optimal Procedure: 221->200->211->010->021->000

Successed or Failed?: Successed ?? ?

五、學生實驗報告要求

（1）對于猴子摘香蕉問題根據(jù)自己編寫代碼或者參考代碼，用不同的初始狀態(tài)測試代碼，記錄每種初始狀態(tài)下的輸出結果，并對每個結果進行解釋。

（2）完善猴子摘香蕉問題參考代碼，參考代碼中有什么問題？應該如何修改會更好。

問題：

1. 數(shù)組索引和函數(shù)調用：

???使用數(shù)組索引i訪問和更新狀態(tài)。確保數(shù)組索引在范圍內，以避免潛在的內存問題。

???考慮將狀態(tài)數(shù)組封裝在結構體內部或將其作為參數(shù)傳遞給函數(shù)，而不是使用全局數(shù)組。

2. 字符串賦值：

???避免直接將字符串賦值給 routesave[i]，例如 routesave[i] = "Monkey go to A";，使用strcpy或類似的函數(shù)進行字符串賦值，以避免潛在的問題。

3. 未使用的變量：

???movebox函數(shù)中聲明了變量int B;但未使用。移除它以避免混淆。

4. 遞歸函數(shù)：

???nextStep 函數(shù)是遞歸的，它一直調用自身。這可能會導致大量步驟時發(fā)生堆棧溢出。考慮使用迭代方法，或者根據(jù)需要增加堆棧大小。

5. 內存管理：

???代碼使用一個固定大小的數(shù)組 (States[150]) 存儲狀態(tài)。如果狀態(tài)數(shù)量不能事先確定，考慮使用動態(tài)內存分配或其他數(shù)據(jù)結構。

（3）傳教士(牧師)與野人問題，寫出狀態(tài)表示的數(shù)據(jù)結構，還有每種解的狀態(tài)遷移圖示。

struct State {int m;//傳教士int c;//野人int dep;//已劃船次數(shù)int boat;//左岸是否有船bool friend operator <(const struct State& a, const struct State& b)//為實現(xiàn)自定義類型的set提供排序規(guī)則{return a.dep < b.dep;//升序排序}
};

例：n=2,c=2時：

1.(2,2,1) -> (2,0,0) -> (2,1,1) -> (0,1,0) -> (0,2,1) -> (0,0,0)

2.(2,2,1) -> (2,0,0) -> (2,1,1) -> (0,1,0) -> (1,1,1) -> (0,0,0)

3.(2,2,1) -> (1,1,0) -> (2,1,1) -> (0,1,0) -> (0,2,1) -> (0,0,0)

4.(2,2,1) -> (1,1,0) -> (2,1,1) -> (0,1,0) -> (1,1,1) -> (0,0,0)

（4）寫出傳教士(牧師)與野人問題的程序清單(語言不限)

#include<iostream>
#include<set>
#include<vector>
using namespace std;int n, c;//傳教士的人數(shù)及船的載客量
int min_deep = INT_MAX;//船的最小來回次數(shù)
int path = 0;//可達路徑的數(shù)量struct State {int m;//傳教士int c;//野人int dep;//已劃船次數(shù)int boat;//左岸是否有船bool friend operator <(const struct State& a, const struct State& b)//為實現(xiàn)自定義類型的set提供排序規(guī)則{return a.dep < b.dep;//升序排序}
};
set<State> Set;//自定義類型State實現(xiàn)set
vector<vector<State>> res;//保存所有路徑//判斷狀態(tài)是否已經(jīng)在當前路徑中，避免重復加入
bool isExist(State next)
{for (auto it = Set.begin(); it != Set.end(); it++)if (it->m == next.m && it->c == next.c && it->boat == next.boat)return true;return false;
}
//輸出路徑
void output()
{for (int i = 0; i < res.size(); i++){if (res[i].size() == min_deep + 1)//判斷是否為最優(yōu)路徑cout << "optimal" << endl;cout << "Solution" << i + 1 << endl;for (int j = 0; j < res[i].size(); j++)//依次輸出路徑上的各個狀態(tài)cout << "(" << res[i][j].m << "," << res[i][j].c << "," << res[i][j].boat << ")" << endl;cout << endl;}
}
//用深度優(yōu)先進行搜索
void dfs(State s)
{Set.insert(s);//加入當前路徑的集合中(已按狀態(tài)的先后順序排序）if (s.m == 0 && s.c == 0)//目標狀態(tài){if (s.dep < min_deep)//記錄最短路徑的劃船次數(shù)min_deep = s.dep;path++;vector<State> v(Set.begin(), Set.end());res.push_back(v);//保存該路徑Set.erase(--Set.end());//已達終點，進行回退return;}if (s.boat == 1)//左岸{for (int i = c; i >= 1; i--)//船載i從左往右劃{if (i > s.m + s.c)//i多于左岸的總人數(shù)continue;for (int j = i; j >= 0; j--)//船上有j個野人{if (j > s.c || i - j > s.m)//多于左岸傳教士、野人的實際人數(shù)continue;if (j != i && j > i - j)//船上傳教士的人數(shù)少于野人的人數(shù)continue;if (s.m - (i - j) != 0 && s.m - (i - j) != n && s.m - (i - j) != s.c - j)//左岸剩下的傳教士與野人的人數(shù)不相等continue;State next;next.boat = 0;next.m = s.m - (i - j);next.c = s.c - j;next.dep = s.dep + 1;if (!isExist(next))//判斷當前路徑是否存在該狀態(tài)dfs(next);}}}else//右岸{for (int i = c; i >= 1; i--)//船載i個人從右往左劃{if (i > (n - s.m) + (n - s.c))//i多于右岸的總人數(shù)continue;for (int j = i; j >= 0; j--)//船上有j個野人{if (j > n - s.c || i - j > n - s.m)//多于右岸傳教士、野人的實際人數(shù)continue;if (j != i && j > i - j)//船上野人的數(shù)量大于傳教士的數(shù)量continue;if (n - s.m - (i - j) != 0 && n - s.m - (i - j) != n && n - s.m - (i - j) != n - s.c - j)//右岸剩下的傳教士人數(shù)與野人不相等continue;State next;next.boat = 1;next.m = s.m + (i - j);next.c = s.c + j;next.dep = s.dep + 1;if (!isExist(next))//判斷當前路徑是否存在該狀態(tài)dfs(next);}}}Set.erase(--Set.end());//無路可走，進行回退
}int main()
{cout << "請輸入傳教士（野人）人數(shù):";cin >> n;cout << endl;cout << "請輸入船的載人量：";cin >> c;State start;//初始狀態(tài)start.m = start.c = n;start.boat = 1;start.dep = 0;dfs(start);cout << "Successed or Failed?:";if (path == 0)cout << "failed" << endl;else{cout << "Successed" << endl;output();cout << "共有" << path << "條路徑。" << endl;cout << "min_deep=" << min_deep << endl;}
}

（5）實驗結果討論。

這是n=2,c=2的情況，共有四種情況的最短路徑，最短路徑為5

這是n=3,c=2的情況，共有四種情況的最短路徑，最短路徑為11

3 漢諾塔問題

漢諾塔問題來自一個古老的傳說：在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A),其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當牧師們完成任務時，世界末日也就到了。

? 采用問題歸約法把漢諾塔問題分成以下三個步驟實現(xiàn)：

1. 將塔A上的n-1個碟子借助塔C先移到塔B上
2. 把塔A上剩下的一個碟子移到塔C上
3. 把n-1個碟子從塔B借助于塔A移到塔C上

實驗要求：?

1. 讓盤子數(shù)從2?開始到7進行實驗，記錄程序運行時間和遞歸調用次數(shù)。

2.畫出盤子數(shù)n和運行時間t?、遞歸調用次數(shù)m的關系圖，并進行分析

分析：

運行時間 vs 盤子數(shù)（n）： 通常來說，漢諾塔問題的解決時間呈指數(shù)增長。圖表中應該看到一個指數(shù)曲線，顯示隨著盤子數(shù)的增加，解決問題所需的時間迅速增加。但是運行時間都太短了，看不出明顯趨勢。

遞歸調用次數(shù) vs 盤子數(shù)（n）： 遞歸調用次數(shù)也是指數(shù)級增長的，因為每增加一個盤子，遞歸調用次數(shù)就翻倍。這與漢諾塔問題的遞歸性質相一致。

在解決類似指數(shù)級增長問題時，遞歸算法可能會面臨的性能挑戰(zhàn)。

實驗代碼：

import timedef hanoi(n, source, target, auxiliary):global recursive_callsif n > 0:recursive_calls += 1hanoi(n - 1, source, auxiliary, target)# 移動盤子# print(f"Move disk {n} from {source} to {target}")hanoi(n - 1, auxiliary, target, source)def run_experiment(n):global recursive_callsrecursive_calls = 0start_time = time.time()hanoi(n, 'A', 'C', 'B')end_time = time.time()execution_time = end_time - start_timereturn execution_time, recursive_calls# 實驗
results = []
for i in range(2, 8):time_taken, calls_made = run_experiment(i)results.append((i, time_taken, calls_made))# 打印結果
print("n\tTime(s)\tRecursive Calls")
for result in results:print(f"{result[0]}\t{result[1]:.6f}\t{result[2]}")import matplotlib.pyplot as pltdef plot_results(results):n_values = [result[0] for result in results]time_values = [result[1] for result in results]calls_values = [result[2] for result in results]# Plotting time vs nplt.figure(figsize=(10, 5))plt.subplot(1, 2, 1)plt.plot(n_values, time_values, marker='o')plt.title('Time vs Number of Disks')plt.xlabel('Number of Disks (n)')plt.ylabel('Time (s)')# Plotting recursive calls vs nplt.subplot(1, 2, 2)plt.plot(n_values, calls_values, marker='o', color='r')plt.title('Recursive Calls vs Number of Disks')plt.xlabel('Number of Disks (n)')plt.ylabel('Recursive Calls')plt.tight_layout()plt.show()# 實驗
results = []
for i in range(2, 8):time_taken, calls_made = run_experiment(i)results.append((i, time_taken, calls_made))# 繪制圖表
plot_results(results)