人工智能實(shí)驗(yàn)報(bào)告模板

PAGE人工智能實(shí)驗(yàn)報(bào)告姓名孫博宇學(xué)號(hào)20112434班級(jí)數(shù)字1201指導(dǎo)教師于瑞云開設(shè)學(xué)期2015-2015第一學(xué)期實(shí)驗(yàn)題目實(shí)驗(yàn)一A*搜索解決羅馬尼亞度假問題實(shí)驗(yàn)日期2015/05/05—2015/05/11評(píng)定成績(jī)?cè)u(píng)定人簽字評(píng)定日期東北大學(xué)軟件學(xué)院人工智能實(shí)驗(yàn)報(bào)告第2頁共2頁實(shí)驗(yàn)?zāi)康腁*搜索也使用啟發(fā)式函數(shù)計(jì)算搜索空間。A*搜索與最佳優(yōu)先搜索不同的是，它既是最優(yōu)的，也是完備的。A*搜索解決羅馬尼亞度假問題：實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟圖結(jié)構(gòu)——地圖#include"graph.h"優(yōu)先隊(duì)列——OPEN表#include"pqueue.h"數(shù)組或隊(duì)列——CLOSED表#include"queue.h"堆?！獑栴}的最終解#include"stack.h"問題的最終解存在堆棧中。首先對(duì)地圖中的點(diǎn)進(jìn)行初始化，地址信息存放在OPEN表里，CLOSE表設(shè)置為空。當(dāng)OPEN表中沒滿時(shí)循環(huán)操作A*搜索。A_Star_Search：A*算法最為核心的部分，就在于它的一個(gè)估值函數(shù)的設(shè)計(jì)上：f(n)=g(n)+h(n)其中f(n)是每個(gè)可能試探點(diǎn)的估值，它有兩部分組成：一部分，為g(n)，它表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià)。另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值。A*算法最為核心的過程，就在每次選擇下一個(gè)當(dāng)前搜索點(diǎn)時(shí)，是從所有已探知的但未搜索過點(diǎn)中(可能是不同層，亦可不在同一條支路上)，選取f值最小的結(jié)點(diǎn)進(jìn)行展開。而所有“已探知的但未搜索過點(diǎn)”可以通過一個(gè)按f值升序的隊(duì)列(即優(yōu)先隊(duì)列)進(jìn)行排列。這樣，在整體的搜索過程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊(duì)列中彈出隊(duì)首元素（f值），對(duì)其可能子結(jié)點(diǎn)計(jì)算g、h和f值，直到優(yōu)先隊(duì)列為空(無解)或找到終止點(diǎn)為止。首先將起始結(jié)點(diǎn)S放入OPEN表，CLOSE表置空，算法開始時(shí)：1、如果OPEN表不為空，從表頭取一個(gè)結(jié)點(diǎn)n，如果為空算法失敗。2、n是目標(biāo)解嗎？是，找到一個(gè)解（繼續(xù)尋找，或終止算法）。3、將n的所有后繼結(jié)點(diǎn)展開，就是從n可以直接關(guān)聯(lián)的結(jié)點(diǎn)（子結(jié)點(diǎn)），如果不在CLOSE表中，就將它們放入OPEN表，并把S放入CLOSE表，同時(shí)計(jì)算每一個(gè)后繼結(jié)點(diǎn)的估價(jià)值f(n)，將OPEN表按f(x)排序，最小的放在表頭，重復(fù)算法，回到1。A*算法流程圖：三、實(shí)驗(yàn)過程與分析//OPEN-->CLOSE，起點(diǎn)-->任意頂點(diǎn)g(n)-->目標(biāo)頂點(diǎn)h(n)closedset:=theemptyset//已經(jīng)被估算的節(jié)點(diǎn)集合openset:=setcontainingtheinitialnode//將要被估算的節(jié)點(diǎn)集合g_score[start]:=0//g(n)h_score[start]:=heuristic_estimate_of_distance(start,goal)//h(n)f_score[start]:=h_score[start]whileopensetisnotempty//若OPEN表不為空x:=thenodeinopensethavingthelowestf_score[]value//x為OPEN表中最小的ifx=goal//如果x是一個(gè)解returnreconstruct_path(came_from,goal)//removexfromopensetaddxtoclosedset//x放入CLSOE表foreachyinneighbor_nodes(x)ifyinclosedsetcontinuetentative_g_score:=g_score[x]+dist_between(x,y)ifynotinopensetaddytoopensettentative_is_better:=trueelseiftentative_g_score<g_score[y]tentative_is_better:=trueelsetentative_is_better:=falseiftentative_is_better=truecame_from[y]:=xg_score[y]:=tentative_g_scoreh_score[y]:=heuristic_estimate_of_distance(y,goal)//x-->y-->goalf_score[y]:=g_score[y]+h_score[y]returnfailurefunctionreconstruct_path(came_from,current_node)ifcame_from[current_node]issetp=reconstruct_path(came_from,came_from[current_node])return(p+current_node)elsereturntheemptypath實(shí)驗(yàn)結(jié)果總結(jié)一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：1、搜索樹上存在著從起始點(diǎn)到終