奧鵬大工20春《人工智能》大作業(yè)題目及要求 - A算法參考答案

1、大工20春人工智能大作業(yè)題目及要求參考答案題目：A*算法談?wù)勀銓Ρ菊n程學(xué)習(xí)過程中的心得體會與建議？人工智能是研究如何利用計算機(jī)來模擬人腦所從事的感知、推理、學(xué)習(xí)、思考、規(guī)劃等人類智能活動，來解決需要用人類智能才能解決的問題，以延伸人們智能的科學(xué)。掌握人工智能的基本概念、基本原理、知識的表示、推理機(jī)制和求解技術(shù)，以及機(jī)器學(xué)習(xí)的技術(shù)方法.掌握人工智能的一個問題和三大技術(shù)，即通用問題求解和知識表示技術(shù)、搜索技術(shù)、推理技術(shù)。人工智能的定義可以分為兩部分，即“人工”和“智能”“人工”比較好理解，爭議性也不大。有時我們會要考慮什么是人力所能及制造的，或者人自身的智能程度有沒有高到可以創(chuàng)造人工智能的地步，等

2、等。但總的來說，“人工系統(tǒng)”就是通常意義下的人工系統(tǒng)。關(guān)于什么是“智能”，就問題多多了。這涉及到其它諸如意識、自我、思維等等問題。人唯一了解的智能是人本身的智能，這是普遍認(rèn)同的觀點(diǎn)。但是我們對我們自身智能的理解都非常有限，對構(gòu)成人的智能的必要元素也了解有限，所以就很難定義什么是“人工”制造的“智能”了。人工智能課程設(shè)計,從以下5個題目中任選其一作答。人工智能課程設(shè)計題目一：A*算法要求：（1）撰寫一份word文檔，里面包括（算法思路、算法程序框圖、重排九宮問題）章節(jié)。（2）算法思路：簡單介紹該算法的基本思想，100字左右即可。算法程序框圖：繪制流程圖或原理圖，從算法的開始到結(jié)束的程序框圖。對于

3、重排九宮問題的啟發(fā)式函數(shù)：f(x)=p(x)+3s(x)p(x)是x結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)相比每個將牌“離家”的最短距離之和；s(x)是：每個將牌和目標(biāo)相比，若該將牌的后繼和目標(biāo)中該將牌的后繼不同，則該將牌得2分，相同則該將牌得0分，中間位置有將牌得1分，沒將牌得0分。對于給定的初始格局和目標(biāo)狀態(tài)請按此啟發(fā)式函數(shù)給出搜索的狀態(tài)空間圖。TI2436初始格局28463目標(biāo)狀態(tài)答:一、問題描述八數(shù)碼問題作為一個經(jīng)典的問題被大家所熟知，該問題是求解如何從開始的一個狀態(tài)(布局)到達(dá)目標(biāo)狀態(tài)所需步數(shù)最少的問題。問題描述如下面第一個圖的九宮格中，放著18的數(shù)字卡片，還有一個格子空著。與空格子相鄰的格子中的卡片可以移

4、動到空格中。經(jīng)過若干次移動，可以形成第二個圖所示的局面。我們把第一個圖的局面記為：12345678.把第二個圖的局面記為：123.46758顯然是按從上到下，從左到右的順序記錄數(shù)字，空格記為句點(diǎn)。本題目的任務(wù)是已知九宮的初態(tài)和終態(tài)，求最少經(jīng)過多少步的移動可以到達(dá)。如果無論多少步都無法到達(dá)，則輸出-1。輸入格式輸入第一行包含九宮的初態(tài)，第二行包含九宮的終態(tài)。輸出格式輸出最少的步數(shù)，如果不存在方案，則輸出-1。樣例輸入12345678.123.46758樣例輸出3樣例輸入13524678.46758123.樣例輸出22二、流程圖三、問題分析將每一個狀態(tài)作為一個結(jié)點(diǎn)容易想到可以用廣搜的方法解決，這種

5、方法簡單，但是就算是加入哈希判重也會搜索很多的無用結(jié)點(diǎn)。我們打算用A*算法解決這個問題，既然確定了用A*算法，那么我們首先應(yīng)該確定估價函數(shù)h(x)，估價函數(shù)的選取直接決定A*算法的效率，一般對于八數(shù)碼問題有三種估價函數(shù)的選法：以不在位的數(shù)碼的個數(shù)為估價函數(shù)以不在位的數(shù)碼歸位所需的最短距離和即曼哈頓距離為估價函數(shù)將逆序?qū)?shù)作為估價函數(shù)可以證明前兩種都是樂觀估計，最后一種不是，因此前兩種都可以作為八數(shù)碼問題的估價函數(shù)，但是你的估計值與真實(shí)值越近所需要搜索的狀態(tài)越少，很明顯第一種方法太樂觀了(估價函數(shù)的選取直接決定算法的效率)，因此我們采用第二種方法作為八數(shù)碼問題的估價函數(shù)解決了估價函數(shù)的問題以后，

6、第二個需要解決的問題就是判重，我們首先想到的是用集合set,這種方法最簡單，但是很不幸這種方法耗時也是最多的，如果時間要求比較高的話，這種情況很容易超時。這里我們不用這種方法，判重問題自然而然想到的是哈希表，好了現(xiàn)在問題又來了，如何創(chuàng)建哈希表，也就是哈希函數(shù)怎么寫，這個東西比較有技巧，還好對于這種問題有一種現(xiàn)成的方法解決，那就是康托展開，還有一個問題就是有些問題是無解的，這種情況我們不希望進(jìn)行很大力氣的搜索之后發(fā)現(xiàn)無解，最好是能提前預(yù)知，值得慶幸的是八數(shù)碼無論怎么移動逆序的奇偶性不變，因此我們可以直接通過O(1)的時間判斷開始和目標(biāo)結(jié)點(diǎn)的逆序奇偶性是否相同就可以了。有了上面的分析之后，程序就可

7、以寫出來了/*A*算法解決八數(shù)碼問題(九宮重排)*程序看起來比較長，核心只有intAstar(intCOL,intCOL,int,int);函數(shù)*其它函數(shù)供Astar函數(shù)調(diào)用，起輔助作用，還有幾個函數(shù)僅僅是為了使界面更友好所有函數(shù)均有注釋說明其中可行性判斷函數(shù)需要對八數(shù)碼問題進(jìn)行數(shù)學(xué)上的簡單分析，hash函數(shù)的設(shè)計有些技巧，其他函數(shù)的原理都是顯然的程序運(yùn)行有問題可以和我聯(lián)系*/#include#include#include#include#include#defineCOL3#defineMAXSTEP70usingnamespacestd;voidoutput(intCOL);/*輸出函數(shù)

8、*/voidinput(intCOL);/*輸出函數(shù)*/intAstar(intCOL,intCOL,int,intpath);/*核心函數(shù)，起始，終止，深度，方向*/booleq(intfromC0L,inttoCOL);/*判斷起始與終止是否相同*/boolchange(intfromCOL,constinti,constintj,constintstep);/*判斷當(dāng)前狀態(tài)是否可以進(jìn)行相應(yīng)移動，并進(jìn)行狀態(tài)轉(zhuǎn)變*/intvalue(constintfromCOL,constinttoCOL);/*估價函數(shù)*/voidoutput_tow(intfromCOL,inttoCOL);/*輸出函

9、數(shù)，和上面的outpput函數(shù)差不多*/boolpossible(intfromCOL,inttoCOL);/*可行性判斷*/inth9=40320,5040,720,120,24,6,2,l,l;/*hash函數(shù)用到的數(shù)據(jù)8-0的階乘*/boolha400000;structNodeintpathMAXSTEP;/*路徑信息*/intexpend;/*權(quán)重*/intdeep;/*深度*/intxCOLCOL;/*狀態(tài)信息*/;structcmpbooloperator()(constNodeA,constNodeB)returnA.expendB.expend;intpaMAXSTEP;pr

10、iority_queueNode,vector,cmpq;/*優(yōu)先隊(duì)列*/Nodemake(intfromCOL,intdeep,intv,intpath,intstep);/*轉(zhuǎn)換函數(shù)*/intmain()intfromCOLCOL;inttoCOLCOL;intk=0,c;memset(ha,0,sizeof(ha);memset(pa,-1,sizeof(pa);printf(請按行輸入原始九宮格，空白的輸入0n);input(from);printf(原始九宮格為：n);output(from);printf(請按行輸入目標(biāo)九宮格，空白的輸入0n);input(to);printf(目

11、標(biāo)九宮格為：n);output(to);printf(按任意鍵顯示執(zhí)行步驟：n);fflush(stdin);getchar();if(!possible(from,to)cout目標(biāo)狀態(tài)不可達(dá)，請換一組數(shù)據(jù)測試！endl;return0;intd=Astar(from,to,0,pa);cout最優(yōu)路徑到目標(biāo)位置需要d步endl;cout當(dāng)前狀態(tài)t目標(biāo)狀態(tài)endl;while(c=pa+k)!=-1)inti,j;/*記錄當(dāng)前狀態(tài)，白板位置*/cout第k步endl;for(i=0;i3;i+)for(j=0;j3;j+)if(fromij=0)gotoo;o:change(from,i,j

12、,pak);output_tow(from,to);coutendl;return0;voidoutput(intaCOL)inti,j;for(i=0;iCOL;i+)for(j=0;jCOL;j+)printf(%d,aij);putchar(n);voidoutput_tow(intfromCOL,inttoCOL)inti,j;for(i=0;iCOL;i+)for(j=0;jCOL;j+)printf(%d,fromij);couttt;for(j=0;jCOL;j+)printf(%d,toij);putchar(n);voidinput(intaCOL)inti,j,c;s:in

13、tg9;memset(g,0,sizeof(g);for(i=0;iCOL;i+)for(j=0;jCOL;j+)scanf(%d,&aij);c=aij;if(gc|c8)cout輸入有誤，請重新輸入endl;gotos;gc+;intAstar(intfromCOL,inttoCOL,intdeep,intpath)if(eq(from,to)memcpy(pa,path,sizeof(pa);returndeep;inti,j;/*記錄當(dāng)前狀態(tài)，白板位置*/int*a=from0;intb9;intm=0;for(i=0;i9;i+)bi=ai;for(i=0;i9;i+)for(j=0

14、;jaj)bi-;m+=hi*bi;ham=1;for(i=0;i3;i+)for(j=0;j3;j+)if(fromij=0)gotook;ok:for(intstep=0;step4;step+)if(change(from,i,j,step)intv=value(from,to)+deep+1;Noden;n=make(from,deep+1,v,path,step);q.push(n);change(from,i,j,step);Nodep=q.top();intflag=0;while(!flag)a=p.x0;m=0;for(i=0;i9;i+)bi=ai;for(i=0;i9;i

15、+)for(j=0;jaj)bi-;m+=hi*bi;if(!ham)q.pop();break;q.pop();p=q.top();returnAstar(p.x,to,p.deep,p.path);booleq(intfromCOL,inttoCOL)/*判斷起始與終止是否相同*/for(inti=0;i3;i+)for(intj=0;j3;j+)if(fromij!=toij)return0;return1;boolchange(intfromCOL,constinti,constintj,constintstep)/*判斷當(dāng)前狀態(tài)是否可以進(jìn)行相應(yīng)移動*/if(i=0&step=0)|(

16、i=2&step=1)|(j=0&step=2)|(j=2&step=3)return0;inta=fromij;switch(step)case0:fromij=fromi-1j;fromi-1j=a;break;case1:fromij=fromi+1j;fromi+1j=a;break;case2:fromij=fromij-1;fromij-1=a;break;case3:fromij=fromij+1;fromij+1=a;break;default:coutWRONG!endl;break;return1;intvalue(constintfromCOL,constinttoCOL

17、)/*古價函數(shù)*/inti,j,m,n;intv=0;for(i=0;i3;i+)for(j=0;j3;j+)for(m=0;m3;m+)for(n=0;n3;n+)if(fromij=tomn)gotop;p:if(fromij!=0)v+=(abs(i-m)+abs(j-n);returnv;Nodemake(intfromCOL,intdeep,intv,intpath,intstep)/*轉(zhuǎn)換函數(shù)*/Nodep;for(inti=0;i3;i+)for(intj=0;j3;j+)p.xij=fromij;p.deep=deep;p.expend=v;memcpy(p.path,path

18、,sizeof(int)*MAXSTEP);p.pathdeep=step;returnp;boolpossible(intfromC0L,inttoCOL)/*可行性判斷*/intm=0,n=0;inti,j,k,l;intaCOL*COL,bCOL*COL;for(i=0;iCOL;i+)for(j=0;jCOL;j+)ai*COL+j=fromij;bi*COL+j=toij;for(k=0;kCOL*COL;k+)for(l=k+1;lCOL*COL;l+)if(alak&al!=0)m+;if(blbk&bl!=0)n+;return(n%2)=(m%2);題目二：回歸算法要求：(1)撰寫一份word文檔，里面包括(常見的回歸算法、基于實(shí)例的算法具體細(xì)節(jié))章節(jié)。常見的回歸算法包括：最小二乘法(OrdinaryLeastSquare)，邏輯回歸(LogisticRegression)，逐步式回歸(StepwiseRegression)，多元自適應(yīng)回歸樣條(M