? ? ? 本章將描述一種基于目標(biāo)的智能體瘟裸，稱為問(wèn)題求解智能體浴韭。將會(huì)提出幾個(gè)通用的搜索算法丘喻，但這些算法是無(wú)信息的，除了問(wèn)題的定義念颈，沒(méi)有其他關(guān)于問(wèn)題的信息泉粉，下一章將探討有信息的搜索算法。
1.問(wèn)題求解智能體
? ? ?通過(guò)評(píng)價(jià)多個(gè)未知的行動(dòng)序列來(lái)選擇最佳行動(dòng)序列的智能體叫做問(wèn)題求解智能體榴芳。尋找這樣序列的過(guò)程叫做搜索嗡靡。一個(gè)簡(jiǎn)單的問(wèn)題求解智能體的算法如下。
function SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns action
inputs percept, a percept
static seq, an action sequence, initially empty
state, some description of the current world state
goal, a goal, initially null
problem, a problem formulation
state <--- UPDATE-STATE(state,percept)
if seq is empty then do
goal <--- FORMULATE-GOAL(state)
problem <--- FORMULATE-PROBLEM(state,goal)
seq <- SEARCH(problem)
action <--- FIRST(seq)
seq <--- RESET(seq)
return action
? ? ?該算法輸入當(dāng)前感知窟感，內(nèi)部靜態(tài)量有行動(dòng)序列讨彼、狀態(tài)、目標(biāo)和問(wèn)題柿祈。行動(dòng)序列初始化為空哈误，目標(biāo)初始化為null。智能體每得到一個(gè)感知躏嚎，就調(diào)用該算法進(jìn)行動(dòng)作求解蜜自。每次進(jìn)入該程序時(shí)首先通過(guò)當(dāng)前狀態(tài)和感知更新狀態(tài)。初始seq為空時(shí)卢佣，先格式化目標(biāo)重荠、完成目標(biāo)遇到的問(wèn)題、通過(guò)問(wèn)題來(lái)搜索出最佳序列虚茶，當(dāng)seq不為空時(shí)省略這一步晚缩。之后將序列的第一個(gè)動(dòng)作賦予action，并將該動(dòng)作從seq中刪除（即重置seq）媳危，最后返回action荞彼。
? ? ? ?該算法相當(dāng)于人類有一個(gè)目標(biāo)之后，分析問(wèn)題待笑，指定計(jì)劃鸣皂，一步步實(shí)施。缺點(diǎn)在于不能通過(guò)當(dāng)前狀態(tài)來(lái)時(shí)時(shí)更新計(jì)劃（即seq）。使用環(huán)境屬性來(lái)描述的話寞缝，該智能體的環(huán)境是：靜態(tài)的癌压、可觀察的、離散的荆陆、確定的滩届。本章剩下的篇幅主要介紹SEARCH函數(shù)。
1.1定義明確的問(wèn)題及解
? ? ? ?一個(gè)問(wèn)題可以形式化地定義為四個(gè)組成部分被啼。
- 初始狀態(tài)帜消。
- 智能體可采納的行動(dòng)的描述，常用的如后繼函數(shù)浓体。
- 目標(biāo)測(cè)試泡挺，用來(lái)測(cè)試給定的狀態(tài)是不是目標(biāo)狀態(tài)。
- 路徑耗散
1.2把問(wèn)題形式化
? ? ? ?狀態(tài)抽象化命浴、行動(dòng)抽象化娄猫、去除無(wú)關(guān)狀態(tài)與行動(dòng)。通俗的話說(shuō)生闲，把握重點(diǎn)媳溺，蝴蝶效應(yīng)顯然不能考慮在內(nèi)。
2.對(duì)解的搜索
? ? ? ?我們把所有可能的解通過(guò)節(jié)點(diǎn)來(lái)連成樹碍讯，求解實(shí)際上就成為在樹中搜索一個(gè)枝褂删。節(jié)點(diǎn)的表示有很多中，我們可以假設(shè)其含有如下幾個(gè)數(shù)據(jù)結(jié)構(gòu)：
- STATE 狀態(tài)空間中與節(jié)點(diǎn)相對(duì)應(yīng)的狀態(tài)冲茸。
- PARENT-NODE 父節(jié)點(diǎn)。
- ACTION 由父節(jié)點(diǎn)產(chǎn)生該節(jié)點(diǎn)所用的行動(dòng)缅帘。
- PATH-COST 路徑耗散
- DEPTH 初始狀態(tài)到達(dá)該節(jié)點(diǎn)路徑上最少的步驟
function TREE-SEARCH(problem,strategy) returns a solution, or failure
initialize the search tree using the initial state of problem
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state the return the corresponding solution
else expand the node and add the resulting nodes to the search tree
? ? ?我們還需要表示生成出來(lái)轴术，但沒(méi)有被擴(kuò)展的節(jié)點(diǎn)，這些點(diǎn)的集合成為邊緣钦无，邊緣的每個(gè)元素都是葉節(jié)點(diǎn)逗栽，即搜索樹中沒(méi)有后繼的節(jié)點(diǎn)。如果使用一個(gè)集合來(lái)表示邊緣失暂，概念上很直接彼宠，但是計(jì)算代價(jià)是昂貴的，因此我們使用隊(duì)列來(lái)實(shí)現(xiàn)弟塞，下面是對(duì)隊(duì)列的一些操作凭峡。
-
MAKE-QUEUE(element, ...) 用給定的元素創(chuàng)建一個(gè)隊(duì)列。
- EMPTY?(queue) 當(dāng)且僅當(dāng)隊(duì)列為空時(shí)返回一真.
- FIRST(queue) 返回隊(duì)列中第一個(gè)元素决记。
- REMOVE-FIRST(queue) 返回FIRST(queue)并將其從queue中刪除摧冀。
- INSERT(element,queue) 在隊(duì)列中插入一個(gè)元素并返回結(jié)果隊(duì)列，在不同隊(duì)列中插入新元素順序是不同的。
- INSERT-ALL(elements,queue) 在隊(duì)列中插入元素集合
function TREE-SEARCH(problem, fringe) returns a solution, or failure
fringe <--- INSERT(MAKE-NODE(INITIAL-STATE[problem]),fringe)
loop do
if EMPTY?(fringe) then return failure
node <--- REMOVE-FIRST(fringe)
if GOAL-TEST[problem] applied to STATE[node] succeeds
then return SOLUTION(node)
fringe <--- INSERT-ALL(EXPAND(node,problem),fringe)
<hr>
function EXPAND(node,problem) returns a set of nodes
successors <--- the empty set
for each(action, result) in SUCCESSOR-FN[problem](STATE[node]) do
s <--- a new node
STATE[s] <--- result
PARENT-NODE[s] <--- node
ACTION[s] <--- action
PATH-COST[s] <--- PATH-COST[node] + STEP-COST(node,action,s)
DEPTH[s] <--- DEPTH[node] + 1
add s to successors
return successors
度量問(wèn)題求解的性能
- 完備性 能否在有解的時(shí)候總能夠到一個(gè)解
- 最有性 能夠總是找到最優(yōu)解
- 時(shí)間復(fù)雜度 找到解需要多長(zhǎng)時(shí)間
- 空間復(fù)雜度 找到解需要多少內(nèi)存
3.無(wú)信息的搜索策略
? ? ? ? 本節(jié)包括無(wú)信息搜索中的五種搜索策略建车。無(wú)信息搜索即除了問(wèn)題定義之外，沒(méi)有狀態(tài)的其他附加信息椒惨。
1.廣度優(yōu)先搜索
? ? ? ? ?廣度優(yōu)先搜索即首先擴(kuò)展根節(jié)點(diǎn)缤至，接著擴(kuò)展根節(jié)點(diǎn)的所有后繼，然后再擴(kuò)展它們的后繼康谆，以此類推领斥。
特點(diǎn)是在下一層任何節(jié)點(diǎn)被擴(kuò)展之前，當(dāng)前層所有節(jié)點(diǎn)都已經(jīng)被擴(kuò)展秉宿。它可以通過(guò)一個(gè)先進(jìn)先出（FIFO）隊(duì)列實(shí)現(xiàn)戒突。
缺點(diǎn)：空間復(fù)雜度高、時(shí)間復(fù)雜度高
2.代價(jià)一致搜索
? ? ? 當(dāng)所有單步耗散相等的時(shí)候描睦，廣度優(yōu)先算法是最優(yōu)的膊存，因?yàn)樗偸菙U(kuò)展深度最淺的未擴(kuò)展節(jié)點(diǎn)。將其延伸忱叭，代價(jià)一致搜索是首先擴(kuò)展路徑耗散最低的節(jié)點(diǎn)隔崎。如果單步耗散一致的話，兩種搜索是一致的韵丑。
3.深度優(yōu)先搜索
? ? ? ? ?深度優(yōu)先搜索總是擴(kuò)展搜索樹的當(dāng)前邊緣的最深的節(jié)點(diǎn)爵卒。搜索直接推進(jìn)到搜索樹的最深層，那里的節(jié)點(diǎn)沒(méi)有后繼節(jié)點(diǎn)撵彻。那些節(jié)點(diǎn)擴(kuò)展完之后钓株，它們被從邊緣中去掉，然后搜索算法“向上回到”下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的 稍淺的節(jié)點(diǎn)陌僵。
? ?這個(gè)搜索策略可以通過(guò)后進(jìn)先出隊(duì)列（LIFO）（棧）來(lái)實(shí)現(xiàn)轴合。
? ?深度優(yōu)先搜索的一個(gè)變形稱之為回溯搜索⊥攵蹋回溯搜素中每個(gè)被部分?jǐn)U展的節(jié)點(diǎn)要記住下一個(gè)要生成的節(jié)點(diǎn)是哪一個(gè)受葛。這兩種算法空間復(fù)雜度小。
4.深度有限搜索
? ? ?即深度優(yōu)先搜索中設(shè)定一個(gè)最大深度偎谁。深度有限搜索可能會(huì)引入不完備总滩，但具體情況通過(guò)給出適合的深度限制，能夠篩除不必要的搜索巡雨。
5.迭代深入深度優(yōu)先搜索
? ? ? 迭代深入搜索是一個(gè)用來(lái)尋找最合適的深度限制的通用策略闰渔。它經(jīng)常和深度優(yōu)先搜索結(jié)合使用。他的做法是不斷的增大深度限制铐望，以此類推澜建，直至找到目標(biāo)節(jié)點(diǎn)向挖。
6.雙向搜索
? ? ? 運(yùn)行兩個(gè)同時(shí)的搜索， 一個(gè)從初始狀態(tài)向前搜索炕舵，一個(gè)從目標(biāo)狀態(tài)向后搜索何之。當(dāng)它們?cè)谥虚g相遇時(shí)終止搜索。
4.去除重復(fù)
? ? ?算法中記錄它訪問(wèn)過(guò)的每一個(gè)狀態(tài)咽筋，相當(dāng)于它直接探索狀態(tài)空間圖溶推。為了做到這一點(diǎn)，我們可以在普通搜索算法中加入一個(gè)數(shù)據(jù)結(jié)構(gòu)奸攻，成為closed表蒜危， 用它儲(chǔ)存每一個(gè)擴(kuò)展過(guò)的節(jié)點(diǎn)，儲(chǔ)存未擴(kuò)展過(guò)的邊緣的表有時(shí)稱之為open表睹耐。如果當(dāng)前節(jié)點(diǎn)與closed表中的某一個(gè)節(jié)點(diǎn)相匹配辐赞，那么它將被放棄而不是被擴(kuò)展。這個(gè)新的算法稱之為圖搜索——GRAPH-SEARCH硝训。圖搜索很有效响委，在最壞的情況下，它的時(shí)間和空間需求和狀態(tài)空間成正比窖梁。
? ? ? 圖搜索算法的優(yōu)異性能給它帶了一個(gè)棘手的問(wèn)題赘风。當(dāng)一個(gè)重復(fù)狀態(tài)被刪除時(shí)，實(shí)際上算法找到了到達(dá)同一狀態(tài)的不同路徑纵刘。GRAPH-SEARCH會(huì)放棄后面找到的路徑邀窃，如果之后找到的路徑其耗散小一些，那么GRAPH-SEARCH就錯(cuò)過(guò)了最佳解假哎。幸運(yùn)的是瞬捕，在單步耗散為常數(shù)的代價(jià)一致搜索和廣度優(yōu)先搜索的情況下這不會(huì)發(fā)生。另一方面舵抹，迭代深入算法使用深度優(yōu)先擴(kuò)展肪虎，很容易在找到最優(yōu)解之前就找到一個(gè)非最優(yōu)解， 因此迭代深入算法需要檢測(cè)新發(fā)現(xiàn)的路徑是否比以前的好掏父，如果是則使用當(dāng)前的代替以前的。
? ? ? ?以下是GRAPH-SEARCH算法的一般版本秆剪。
function GRAPH-SEARCH(problem,fringe) returns a solution, or failure
closed <--- an empty set
fringe <--- INSERT(MAKE-NODE(INITIAL-STATE[problem]),fringe)
loop do
if EMPTY?(fringe) then return failure
node <--- REMOVE-FIRST(fringe)
if GOAL-TEST[problem](STATE[node]) then return SOLUTION(node)
if STATE[node] is not in closed then
add STATE[node] to closed
fringe <--- INSERT-ALL(EXPAND(node,problem),fringe)
5.使用不完全信息的搜索
? ? ? ?不同的不完全會(huì)導(dǎo)致三種不同的情況赊淑。
- 無(wú)傳感問(wèn)題（也稱構(gòu)造問(wèn)題）。
- 偶發(fā)性問(wèn)題仅讽。如果環(huán)境是部分可觀察的或者行動(dòng)不確定的陶缺，那么智能體在感知每個(gè)行動(dòng)之后將會(huì)提供新的信息。每個(gè)可能的感知信息定義了一個(gè)必須提前準(zhǔn)備處理計(jì)劃的偶發(fā)事件洁灵。如果不確定性是由另外一個(gè)智能體引起的饱岸，就稱其為對(duì)抗性的掺出。
- 探索問(wèn)題。當(dāng)感知和行動(dòng)都未知的時(shí)候苫费，稱之為探索問(wèn)題汤锨。探索問(wèn)題可以看做是偶發(fā)性問(wèn)題的一種極端情況。
? ? ?當(dāng)環(huán)境是部分可觀察的百框，智能體可以在信念狀態(tài)空間闲礼，也就是也就是只能所處的可能狀態(tài)集中應(yīng)用搜索算法。在某些情況下铐维，可以構(gòu)造出唯一的序列解柬泽。：而其他情況下，智能體需要一個(gè)偶發(fā)性計(jì)劃來(lái)處理可能出現(xiàn)的未知情況嫁蛇。
以上锨并！
