人工智能實(shí)驗(yàn)2傳教士過河問題.docx

1、人工智能實(shí)驗(yàn)報(bào)告班級(jí)：計(jì)研 -12 班學(xué)號(hào)： 25姓名：孔德星實(shí)驗(yàn)二知識(shí)表示方法1實(shí)驗(yàn)?zāi)康模?1）了解知識(shí)表示相關(guān)技術(shù)；（ 2）掌握問題規(guī)約法或者狀態(tài)空間法的分析方法。2實(shí)驗(yàn)內(nèi)容（ 2 個(gè)實(shí)驗(yàn)內(nèi)容可以選擇1 個(gè)實(shí)現(xiàn)）（ 1）梵塔問題實(shí)驗(yàn)。熟悉和掌握問題規(guī)約法的原理、實(shí)質(zhì)和規(guī)約過程；理解規(guī)約圖的表示方法；（ 2）狀態(tài)空間法實(shí)驗(yàn)。從前有一條河，河的左岸有m 個(gè)傳教士、m 個(gè)野人和一艘最多可乘n 人的小船。約定左岸，右岸和船上或者沒有傳教士，或者野人數(shù)量少于傳教士，否則野人會(huì)把傳教士吃掉。搜索一條可使所有的野人和傳教士安全渡到右岸的方案。3實(shí)驗(yàn)報(bào)告要求（ 1）簡(jiǎn)述實(shí)驗(yàn)原理及方法，并請(qǐng)給出程序設(shè)計(jì)流程

2、圖。實(shí)驗(yàn)原理：假設(shè)開始時(shí)傳教士、野人和船都在右岸，用數(shù)組(a,b,c)分別表示右岸傳教士個(gè)數(shù)、右岸野人個(gè)數(shù)、船的位置，則可分為三種情況討論:A 、nm/2 。此種情況下，先把所有的野人度過去，每次返回一個(gè)野人，當(dāng)出現(xiàn)(m,0,0)情況時(shí)， 返回 m-n 個(gè)野人 (若 m=n,返回 1 個(gè)野人 )。然后渡 n 個(gè)傳教士， 此時(shí)野人 =傳教士，然后返回一個(gè)野人和傳教士，再開始最大限度的渡傳教士，每次返回一個(gè)野人,最終直到a=b=c=0 ；B 、n=3&n=4&nm/2N遞歸執(zhí)行Y右岸傳教士遞歸執(zhí)行載的人數(shù) n個(gè)數(shù)是否為 0YN是否 (m=3船是否在右是否已經(jīng)成分情況遞歸執(zhí)& nm/2Y岸功行| n

3、=1YYN失敗結(jié)束成功結(jié)束遞歸執(zhí)行（ 2）源程序清單：本程序用C+ 語(yǔ)言編寫。#includeiostreamusingnamespace std;boolflag =false ;/標(biāo)記是否有解boolaf =false;/標(biāo)記 a是否為 0boolbf =false;/當(dāng) b變?yōu)?0后賦值為 true;boolef =false;/ 當(dāng) a=b后賦值為 trueboolf =false ;/判斷 n是否大于 m/2intm; /傳教士野人的個(gè)數(shù)intn; /船一次能裝載的人數(shù)voidmc( inta, int b, int c);intmain()cout 傳教士與野人過河問題。n 假設(shè)最

4、初時(shí)傳教士與野人在河的右岸。 n ;coutm;coutn;cout 右岸傳教士人數(shù) t 右岸野人個(gè)數(shù) t 船的位置（ 1. 右岸 0 左岸） endl;if (m=3 & n=m/2) | n=1)/ 此種情況無(wú)解cout m/2)f = true ;mc(m,m,1);if (flag =true )cout Success!n;else cout No solution!n;system( pause );return0;void mc( inta, intb, intc)if (flag= true )return ;if ( c = 1)cout tattif (f= true )b

5、ttcm/2if (bf!= true )/b未達(dá)到過 0if ( a+b=n)/ 如果 a+b= 0;j-)if ( b = j)mc(a, b-j,1-c);if (flag= true )return ;/ 遞歸elseif (ef!= true & af= false )for ( inti = n;i=0;i-)if ( a=i)mc(a-i,b,1- c);if (flag= true )/ 遞歸return ;if (ef =true & af= false )if ( a=n)mc(a-n, b,1- c);/ 遞歸elseif ( a+b=n)elseelse mc(a-n/

6、2, b-n/2,1-c);mc(a,mc(a,0,1-/ 遞歸b-n,1- c); c);/ 遞歸if ( c = 0)cout tattbttcm/2if ( b=0)bf =true ;if (m = n)mc(a, b+1,1- c);/ 遞歸elsemc(a, b+m-n,1- c);if ( a=b)ef =true ;mc(a+1, b+1,1- c);/ 遞歸if ( a = 0)af =true ;mc(a, b+1,1- c);/ 遞歸while (bf!=true )mc(a, b+1,1- c);/ 遞歸else/k3mc(a+1, b+1,1- c);/ 遞歸（ 3）實(shí)驗(yàn)結(jié)果及分析。程序?qū)嶒?yàn)結(jié)果如下圖。當(dāng)然，傳教士與野人個(gè)數(shù)為3，船一次能載兩個(gè)人，這是最經(jīng)典的例子。本程序也可輸入其它數(shù)據(jù)，同樣可以得到正確結(jié)果。本程序主要采用狀態(tài)空間法和遞歸調(diào)用來(lái)解決問題。程序在一開始就排除了不可能會(huì)成功的狀態(tài)空間， 也對(duì)剩下的狀態(tài)空間也進(jìn)行了分類，這樣直接減少了問題的復(fù)雜程度。另外，本程序大量采用遞歸調(diào)用的思想，減少了編程代碼的工作