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

奧鵬大工20春《人工智能》大作業(yè)題目及要求-A算法參考答案大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)大工20春《人工智能》大作業(yè)題目及要求參考答案題目：A*算法1.談?wù)勀銓Ρ菊n程學(xué)習(xí)過程中的心得體會與建議？人工智能是研究如何利用計(jì)算機(jī)來模擬人腦所從事的感知、推理、學(xué)習(xí)、思考、規(guī)劃等人類智能活動，來解決需要用人類智能才能解決的問題，以延伸人們智能的科學(xué)。掌握人工智能的基本概念、基本原理、知識的表示、推理機(jī)制和求解技術(shù)，以及機(jī)器學(xué)習(xí)的技術(shù)方法.掌握人工智能的一個(gè)問題和三大技術(shù)，即通用問題求解和知識表示技術(shù)、搜索技術(shù)、推理技術(shù)。人工智能的定義可以分為兩局部，即“人工”和“智能”。“人工”比擬好理解，爭議性也不大。有時(shí)我們會要考慮什么是人力所能及制造的，或者人自身的智能程度有沒有高到可以創(chuàng)intmain()intfrom[COL][COL];intto[COL][COL];intk=O,c;memset(ha,0,sizeof(ha));memset(parl,sizeof(pa));printf("請按行輸入原始九宮格，空白的輸入0W)input(from);printf("原始九宮格為：\n");output(from);printf("請按行輸入目標(biāo)九宮格，空白的輸入0\n");input(to);大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)printf("目標(biāo)九宮格為：\nn);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)"<<n<<"目標(biāo)狀態(tài)"<<endl;while((c=pa[++k])!=-1){inti,j;/*記錄當(dāng)前狀態(tài)，白板位置*/cout?"第"?k?"步"?endl;for(i=0;i<3;i++)for(j=0;j<3;j++)if(from[i][j]=0)gotoo;o:change(from,i,j,pa[k]);output_tow(from,to);cout?""?endl;)return0;)voidoutput(inta[][COL])大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)inti,j;for(i=0;i<COL;i++){for(j=0;j<COL;j++)printf("%dn,a[i][j]);putchar('\n');))voidoutput_tow(intfrom[][COL],intto[][COL])(inti,j;for(i=0;i<COL;i++){for(j=0;j<COL;j++)printf("%dn,from[i][j]);cout?,\t'?'\t';for(j=0;j<COL;j++)printf("%d",to[i][j]);putchar('\n');voidinput(inta[][COL])inti,j,c;s:intg[9];memset(g,0,sizeof(g));for(i=0;i<COL;i++)for(j=0;j<COL;j++){scanf("%d",&a[i][j]);c=a[i][j];if(g[c]||c<0||c>8){大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)cout<〈”輸入有誤，請重新輸入"<<endl;gotos;)g[c]++；})intAstar(intfrom[][COL],intto[][COL]Jntdeepjntpath[])if(eq(from,to)){memcpy(pa,path,sizeof(pa));returndeep;)inti,j;/*記錄當(dāng)前狀態(tài)，白板位置*/int*a=from[0];intb[9];intm=0;for(i=0;i<9;i++)b[i]=a[i];for(i=0;i<9;i++){for(j=0;j<i;j++)if(b[i]>a[j])b[i]-；m+=h[i]*b[i];)ha[m]=l;for(i=0;i<3;i++)for(j=0;j<3;j++)if(from[i][j]==0)大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)gotook;ok:for(intstep=0;step<4;step++){if(change(fromJj9step)){intv=value(from,to)+deep+l;Noden;n=make(from,deep+1path,step);q.push(n);change(fromJj,step);))Nodep=q.top();intflag=0;while(!flag){a=p.x[0];m=0;for(i=0;i<9;i++)b[i]=a[i];for(i=0;i<9;i++){for(j=0;j<i;j++)if(b[i]>a[j])b[i]-；m+=h[i]*b[i];)if(!ha[m]){q.popO;break;)q.popO;p=q.top();大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì))returnAstar(p.x,to,p.deep,p.path);)booleq(intfrom[][COL],intto[][COL])/*判斷起始與終止是否相同*/for(intj=0;j<3;j++){if(from[i][j]!=to[i][j])return0;)return1;)boolchange(intfrom[][COL],constinti,constintj,constintstep)/*判斷當(dāng)前狀態(tài)是否可以進(jìn)行相應(yīng)移動*/(if((i=0&&step=0)||(i=2&&step==l)||(j=0&&step==2)||(j=2&&step=3))return0;inta=from[i皿；switch(step){case0:from[i][j]=from[i-1][j];from[i-l][j]=a;break;from[i][j]=from[i+l][j];from[i+l][j]=a;break;大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)from[i][j]=from[i][j-1];from[i][j-l]=a;break;from[i][j]=from[i][j+l];from[i][j+l]=a;break;default:cout?"WRONG!n?endl;break;)return1;)intvalue(constintfrom[][COL],constintto口[COL])/*估價(jià)函數(shù)*/intintv=0;for(i=0;i<3;i++)for(j=0;j<3;j++){for(m=0;m<3;m++)for(n=0;n<3;n++)if(from[i][j]==to[m][n])gotop;P-if(from[i][j]!=0)v+=(abs(i-m)+abs(j-n));)returnv;大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì))Nodemake(intfrom[][COL]JntdeepJntv,intpath[]Jntstep)/*轉(zhuǎn)換函數(shù)*/(Nodep;造人工智能的地步，等等。但總的來說，“人工系統(tǒng)”就是通常意義下的人工系統(tǒng)。關(guān)于什么是“智能”，就問題多多了。這涉及到其它諸如意識、自我、思維等等問題。人唯一了解的智能是人本身的智能，這是普遍認(rèn)同的觀點(diǎn)。但是我們對我們自身智能的理解都非常有限，對構(gòu)成人的智能的必要元素也了解有限，所以就很難定義什么是“人工”制造的“智能”了。2.《人工智能》課程設(shè)計(jì),從以下5個(gè)題目中任選其一作答?！度斯ぶ悄堋氛n程設(shè)計(jì)題目一：A*算法要求：(1)撰寫一份word文檔，里面包括(算法思路、算法程序框圖、重排九宮問題)章節(jié)。(2)算法思路：簡單介紹該算法的基本思想，100字左右大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)即可。for(intj=0;j<3;j++){p.x[i][j]=from[i][j];)p.deep=deep;p.expend二v;memcpy(p.path,path,sizeof(int)*MAXSTEP);p.path[deep]=step;returnp;)boolpossible(intfrom[][COL],intto[][COL])/*可行性判斷*/(intm=0,n=0;intinta[COL*COL],b[COL*COL];for(i=0;i<COL;i++)for(j=0;j<COL;j++){a[i*COL+j]=from[i][j];b[i*COL+j]=to[i][j];}for(l=k+l;l<COL*COL;l++){if(a[l]<a[k]&&a[l]!=O)m++;if(b[l]<b[k]&&b[l]!=O)大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)n++;)return(n%2)==(m%2);)題目二:歸算法題目二:歸算法要求：(1)撰寫一份word文檔，里面包括(常見的回歸算法、基于實(shí)例的算法具體細(xì)節(jié))章節(jié)。常見的回歸算法包括：最小二乘法(常見的回歸算法包括：最小二乘法(OrdinaryLeastSquare)(LogisticRegression)(OrdinaryLeastSquare)(OrdinaryLeastSquare)(LogisticRegression)邏輯逐步式(StepwiseRegression)(StepwiseRegression)(StepwiseRegression)多元自適應(yīng)回歸樣條(MultivariateAdaptiveRegressionSpIines)以及本地散點(diǎn)平滑估計(jì)(LocaIlyEstimatedScatterplotSmoothing),請選擇一個(gè)算法描述下算法核心思想(3)隨意選用一個(gè)實(shí)例實(shí)現(xiàn)你所選擇的回歸算法。題目三：深度優(yōu)先搜索算法要求：(1)撰寫一份word文檔，里面包括(算法思路、算法程序框圖、主要函數(shù)代碼)章節(jié)。(2)算法思路:簡單介紹該算法的基本思想,至少100字。(3)(2)算法思路:簡單介紹該算法的基本思想,至少(4)主要函數(shù)代碼：列出算法的具體代碼。大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)(5)簡單描述在人工智能的哪些領(lǐng)域需要使用深度優(yōu)先搜索算法。

題目四：博弈樹要求：(1)撰寫一份word文檔，里面包括(基本概計(jì)算倒推值、剪枝技術(shù))章節(jié)。計(jì)算倒推值、剪枝技術(shù))章節(jié)。(2)基本概念：簡單描述博弈樹，至少200字。(3)簡單描述-剪枝技術(shù)。(4)圖示博弈樹，其中末一行的數(shù)字為假設(shè)的估值,請對博弈樹作如下工作：計(jì)算各節(jié)點(diǎn)的倒推值。利用-剪枝技術(shù)剪去不必要的分支。(可在節(jié)點(diǎn)分支上直接加注釋)題目五：廣度優(yōu)先搜索算法要求：(1)撰寫一份word文檔，里面包括(算法思路、算法程序框圖、主要函數(shù)代碼)章節(jié)。(2)算法思路：簡單介紹該算法的基本思想，至少100字。(3)算法程序框圖：繪制流程圖或原理圖,從算法的開始大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)到結(jié)束的程序框圖。（4）主要函數(shù)代碼：列出算法的具體代碼。(3)算法程序框圖：繪制流程圖或原理圖，從算法的開始到結(jié)束的程序框圖。(4)對于重排九宮問題的啟發(fā)式函數(shù)：f(x)=p(x)+3s(x)p(x)是x結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)相比每個(gè)將牌“離家”的最短距離之和；s(x)是：每個(gè)將牌和目標(biāo)相比，假設(shè)該將牌的后繼和目標(biāo)中該將牌的后繼不同，那么該將牌得2分，相同那么該將牌得分，中間位置有將牌得1分，沒將牌得分。對于給定的初始格局和目標(biāo)狀態(tài)請按此啟發(fā)式函數(shù)給出搜索的狀態(tài)空間圖。8124376512384765答：初始格局目標(biāo)狀態(tài)一、問題描述八數(shù)碼問題作為一個(gè)經(jīng)典的問題被大家所熟知，該問題是求解如何從開始的一個(gè)狀態(tài)（布局）到達(dá)目標(biāo)狀態(tài)所需步數(shù)最少的問題。問題描述如下面第一個(gè)圖的九宮格中，放著1?8的數(shù)字卡片，還有一個(gè)格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。經(jīng)過假設(shè)干次移動，可以形成第二個(gè)圖所示的局面。大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)我們把第一個(gè)圖的局面記為：12345678.把第二個(gè)圖的局面記為：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二、流程圖大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)三、問題分析將每一個(gè)狀態(tài)作為一個(gè)結(jié)點(diǎn)容易想到可以用廣搜的方法解決，這種方法簡單，但是就算是加入哈希判重也會搜索很多的無用結(jié)點(diǎn)。我們打算用A*算法解決這個(gè)問題，既然確定了用A*算法,那么我們首先應(yīng)該確定估價(jià)函數(shù)h(x),估價(jià)函數(shù)的選取直接決定A*算法的效率，一般對于八數(shù)碼問題有三種估價(jià)函數(shù)的選法：以不在位的數(shù)碼的個(gè)數(shù)為估價(jià)函數(shù)以不在位的數(shù)碼歸位所需的最短距離和即曼哈頓距離為估價(jià)函數(shù)將逆序?qū)?shù)作為估價(jià)函數(shù)可以證明前兩種都是樂觀估計(jì)，最后一種不是，因此前兩種都可以作為八數(shù)碼問題的估價(jià)函數(shù)，但是你的估計(jì)值與真實(shí)值越近所需要搜索的狀態(tài)越少，很明顯第一種方法太樂觀了（估價(jià)函數(shù)的選取直接決定算法的效率），因此我們采用第二種方法作為八數(shù)碼問題的估價(jià)函數(shù)解決了估價(jià)函數(shù)的問題以后，第二個(gè)需要解決的問題就是判重，我們首先想到的是用集合set,這種方法最簡單，但是很不幸這種方法耗時(shí)也是最多的，如果時(shí)間要求比擬高的話，這種情況很容易超時(shí)。這里我們不用這種方法，判重問題自然而然想到的是哈希表，好了現(xiàn)在問題又來了，如何創(chuàng)立哈希表,也就是哈希函數(shù)怎么寫，這個(gè)東西比擬有技巧，還好對于這種問題有一種現(xiàn)成的方法解決，那就是康托展開，還有一個(gè)問題就是有些問題是無解的，這種情況我們不希望進(jìn)行很大力氣的搜索之后發(fā)現(xiàn)無解，最好是能提前預(yù)知，值得慶幸的是八數(shù)碼無論怎么移動逆序的奇偶性不變，因此我們可以直接通過0（1）的時(shí)間判斷開始和目標(biāo)結(jié)點(diǎn)的逆序奇偶性是否相同就可以了。有了上面的分析之后，程序就可以寫出來了/**A*算法解決八數(shù)碼問題（九宮重排）程序看起來比擬長，核心只有intAstar（int[][COL],int大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)[][COL],int,int）;函數(shù)其它函數(shù)供Astar函數(shù)調(diào)用，起輔助作用，還有幾個(gè)函數(shù)僅僅是為了使界面更友好所有函數(shù)均有注釋說明其中可行性判斷函數(shù)需要對八數(shù)碼問題進(jìn)行數(shù)學(xué)上的簡單分析，hash函數(shù)的設(shè)計(jì)有些技巧，其他函數(shù)的原理都是顯然的程序運(yùn)行有問題可以和我聯(lián)系/#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<queue>defineCOL3defineMAXSTEP70usingnamespacestd;voidoutput(int口[COL]);/*輸出函數(shù)*/voidinput(int[][COL]);/*輸出函數(shù)*/intAstar(int[][COL],int[][COL],int,intpath[]);/*核心函數(shù)，起始，終止，深度，方向*/b