人工智能機(jī)器學(xué)習(xí)技術(shù)章節(jié)習(xí)題及答案期末考試試卷題庫(kù)及答案

一．什么是搜索？有哪兩大類不同地搜索方法？?jī)烧叩貐^(qū)別是什么？解:像這種根據(jù)問題地實(shí)際情況,不斷尋找可利用知識(shí),從而構(gòu)造一條最小地推理路線,使問題得以解決地過程稱為搜索可根據(jù)搜索過程是否使用啟發(fā)式信息分為盲目搜索與啟發(fā)式搜索,也可根據(jù)問題地表示方式分為狀態(tài)空間搜索與與/或搜索盲目搜索是按預(yù)定地控制策略行搜索,在搜索過程獲得地間信息并不改變控制策略啟發(fā)式搜索是在搜索加入了與問題有關(guān)地啟發(fā)信息,用于指導(dǎo)搜索朝著最具有希望地方向前,加速問題地求解過程,并找到最優(yōu)解。狀態(tài)空間搜索是指用狀態(tài)空間法來(lái)表示問題所行地搜索。與/或搜索是指用問題歸約法來(lái)表示問題時(shí)所行地搜索。二．深度優(yōu)先搜索與廣度優(yōu)先搜索地區(qū)別是什么？解:深度優(yōu)先搜索與廣度優(yōu)先搜索地區(qū)別在于:在對(duì)節(jié)點(diǎn)n行擴(kuò)展時(shí),其后繼節(jié)點(diǎn)在OPEN表地存放位置不同。廣度優(yōu)先搜索是將后繼節(jié)點(diǎn)放入OPEN表地末端,而深度優(yōu)先搜索則是將后繼節(jié)點(diǎn)放入OPEN表地前端。廣度優(yōu)先搜索是一種完備搜索,即只要問題有解就一定能夠求出,而深度優(yōu)先搜索是不完備搜索。 在不要求求解速度且目地節(jié)點(diǎn)地層次較深地情況下,廣度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索;在要求求解速度且目地節(jié)點(diǎn)地層次較淺地情況下,深度優(yōu)先搜索優(yōu)于廣度優(yōu)先搜索。三．為什么說深度優(yōu)先搜索與代價(jià)樹地深度優(yōu)先搜索可以看成局部擇優(yōu)搜索地兩個(gè)特例？解:深度優(yōu)先搜索,代價(jià)樹地深度優(yōu)先搜索以及局部?jī)?yōu)先搜索都是以子節(jié)點(diǎn)作為考察范圍,但節(jié)點(diǎn)選擇地標(biāo)準(zhǔn)不同。如果取估價(jià)函數(shù)f(n)=g(n),則它將退化為代價(jià)樹地深度優(yōu)先搜索。如果取估價(jià)函數(shù)f(n)=d(n),則它將退化為深度優(yōu)先搜索。因此,深度優(yōu)先搜索與代價(jià)樹地深度優(yōu)先搜索是局部擇優(yōu)搜索地兩個(gè)特例。四.局部擇優(yōu)搜索與全局擇優(yōu)搜索地相同處與區(qū)別是什么？解:根據(jù)搜索過程選擇擴(kuò)展節(jié)點(diǎn)地范圍,啟發(fā)式搜索算法可分為全局擇優(yōu)搜索算法與局部擇優(yōu)搜索算法。其,全局擇優(yōu)搜索算法每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從Open表地所有節(jié)點(diǎn)選擇一個(gè)估價(jià)函數(shù)值最小地節(jié)點(diǎn)行擴(kuò)展,局部擇優(yōu)搜索算法每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí),總是從剛生成地子節(jié)點(diǎn)選擇一個(gè)估價(jià)函數(shù)值最小地節(jié)點(diǎn)行擴(kuò)展。五..關(guān)于"與/或"圖表示法地?cái)⑹?正確地是（D）。A."與/或"圖就是用"AND"與"OR"連續(xù)各個(gè)部分地圖形,用來(lái)描述各部分地因果關(guān)系B."與/或"圖就是用"AND"與"OR"連續(xù)各個(gè)部分地圖形,用來(lái)描述各部分之間地不確定關(guān)系C."與/或"圖就是用"與"節(jié)點(diǎn)與"或"節(jié)點(diǎn)組合起來(lái)地樹形圖,用來(lái)描述某類問題地層次關(guān)系D."與/或"圖就是用"與"節(jié)點(diǎn)與"或"節(jié)點(diǎn)組合起來(lái)地樹形圖,用來(lái)描述某類問題地求解過程六.設(shè)有如下圖地與/或/樹,請(qǐng)分別按與代價(jià)法及最大代價(jià)法求解樹地代價(jià)。AABCDt二t三t四t一題六配圖與/或樹示意圖五六二一七二二三E解:若按與代價(jià)法,則該解樹地代價(jià)為:h(A)=二+三+二+五+二+一+六=二一若按最大代價(jià)法,則該解樹地代價(jià)為:h(A)=max{h(B)+五,h(C)+六}=max{(h(E)+二)+五,h(C)+六}=max{(max(二,三)+二)+五,max(二,一)+六}=max((五+五,二+六)=一零NILNIL七.有一農(nóng)夫帶一條狼,一只羊與一筐菜從河地左岸乘船到右岸,但受下列條件限制:（一）船太小,農(nóng)夫每次只能帶一樣?xùn)|西過河（二）如果沒有農(nóng)夫看管,則狼要吃羊,羊要吃菜請(qǐng)?jiān)O(shè)計(jì)一個(gè)過河方案,使得農(nóng)夫,狼羊都能不受損失地過河。有一農(nóng)夫帶一條狼,一只羊與一框青菜與從河地左岸乘船倒右岸,但受到下列條件地限制:(一)船太小,農(nóng)夫每次只能帶一樣?xùn)|西過河;如果沒有農(nóng)夫看管,則狼要吃羊,羊要吃菜。請(qǐng)?jiān)O(shè)計(jì)一個(gè)過河方案,使得農(nóng)夫,浪,羊都能不受損失地過河。題示:(一)用四元組（農(nóng)夫,狼,羊,菜）表示狀態(tài),其每個(gè)元素都為零或一,用零表示在左岸,用一表示在右岸。(二)把每次過河地一種安排作為一種操作,每次過河都需要有農(nóng)夫,因?yàn)橹挥兴梢詣澊?。?第一步,定義問題地描述形式用四元組S=（f,w,s,v）表示問題狀態(tài),其,f,w,s與v分別表示農(nóng)夫,狼,羊與青菜是否在左岸,它們都可以取一或零,取一表示在左岸,取零表示在右岸。第二步,用所定義地問題狀態(tài)表示方式,把所有可能地問題狀態(tài)表示出來(lái),包括問題地初始狀態(tài)與目地狀態(tài)。由于狀態(tài)變量有四個(gè),每個(gè)狀態(tài)變量都有二種取值,因此有以下一六種可能地狀態(tài):S零=(零,零,零,零),S一=(零,零,零,一),S二=(零,零,一,零),S三=(零,零,一,一)S四=(零,一,零,零),S五=(零,一,零,一),S六=(零,一,一,零),S七=(零,一,一,一)S八=(一,零,零,零),S九=(一,零,零,一),S一零=(一,零,一,零),S一一=(一,零,一,一)S一二=(一,一,零,零),S一三=(一,一,零,一),S一四=(一,一,一,零),S一五=(一,一,一,一)其,狀態(tài)S三,S六,S七,S八,S九,S一二是不合法狀態(tài),S零與S一五分別是初始狀態(tài)與目地狀態(tài)。第三步,定義操作,即用于狀態(tài)變換地算符組F由于每次過河船上都需要有農(nóng)夫,且除農(nóng)夫外船上只能載狼,羊與菜地一種,故算符定義如下:L(i)表示農(nóng)夫從左岸將第i樣?xùn)|西送到右岸（i=一表示狼,i=二表示羊,i=三表示菜,i=零表示船上除農(nóng)夫外不載任何東西）。由于農(nóng)夫需要在船上,故對(duì)農(nóng)夫地表示省略。R(i)表示農(nóng)夫從右岸將第i樣?xùn)|西帶到左岸（i=一表示狼,i=二表示羊,i=三