1
| 本文作者： 章敏 | 2016-07-20 18:07 |
聯(lián)合編譯：章敏、陳圳
現(xiàn)有的啟發(fā)式搜索算法不能在找到完整的解決方案之前采取行動(dòng)，所以它們不適用于實(shí)時(shí)應(yīng)用。因此我們提出了一種極大極小前向搜索（minimax lookahead search）的特殊情況來處理這一問題，還提出了一種能顯著提升該算法的效率的類似于 α-β 剪枝的算法。此外，我們還提出了一種名為 Real-Time-A* 的新算法，該算法能用在動(dòng)作必須被確實(shí)執(zhí)行而不僅僅是模擬時(shí)來進(jìn)行搜索。最后，我們檢查了計(jì)算和執(zhí)行成本之間的權(quán)衡的性質(zhì)。
啟發(fā)式搜索是人工智能領(lǐng)域一個(gè)基礎(chǔ)的問題解決方法。對(duì)于大多數(shù)AI問題，解決方法所需的步驟序列可以是不知道先驗(yàn)的，但它必須由一個(gè)系統(tǒng)反復(fù)試驗(yàn)決定探索替代方法。所有的這些要求構(gòu)造一個(gè)搜索問題——一系列的狀態(tài)，一系列狀態(tài)映射到狀態(tài)的操作員，一個(gè)初始狀態(tài)，和一系列目標(biāo)狀態(tài)。這個(gè)任務(wù)典型的問題是：找到一個(gè)最廉價(jià)的操作員將初始狀態(tài)映射到目標(biāo)狀態(tài)。使用啟發(fā)式評(píng)估函數(shù)（一般不會(huì)犧牲最優(yōu)解），很大程度上降低了搜索算法的復(fù)雜性。計(jì)算和評(píng)估從給定狀態(tài)到目標(biāo)狀態(tài)最實(shí)惠方法的支出時(shí)，啟發(fā)式函數(shù)相對(duì)來說更實(shí)惠。
AI文學(xué)界在搜索問題方面共同的例子是Eight Puzzle和其相對(duì)較大的Fifteen Puzzle。Eight Puzzle由一個(gè)3x3的序列框組成，包含8個(gè)編號(hào)棋子和一個(gè)稱為“空白”的空位置。法定操作人員水平或垂直從相鄰的位置滑動(dòng)棋子。其任務(wù)是在一個(gè)隨機(jī)的初始狀態(tài)下重新排列棋子到所需的設(shè)定。該問題有一個(gè)共同的啟發(fā)式函數(shù)稱為“曼哈頓距離”（（Manhattan Distance）。它以計(jì)數(shù)的方式進(jìn)行計(jì)算，對(duì)于每一個(gè)不再其目標(biāo)位置的棋子，沿著網(wǎng)格移動(dòng)的數(shù)量是遠(yuǎn)離它的目標(biāo)位置，并且總計(jì)所有棋子的值，不包括空白的。
一個(gè)實(shí)時(shí)的例子如網(wǎng)絡(luò)路徑自動(dòng)導(dǎo)航，或在任意地形從一個(gè)初始位置到所需的目標(biāo)位置。這是典型的找出目標(biāo)和初始位置之間最短路徑問題。針對(duì)該問題的一個(gè)典型的啟發(fā)式評(píng)估函數(shù)是，從給定位置到目標(biāo)位置的空間直線。
最著名的啟發(fā)式搜索算法是A*。A*是計(jì)算哪一個(gè)點(diǎn)f（n）是最好的首選最優(yōu)搜索算法，g（n）是搜索該點(diǎn)的實(shí)際總支出，而h（n）是搜索該點(diǎn)解決方法的評(píng)估支出。當(dāng)啟發(fā)式函數(shù)可被采納時(shí)，A*有著一個(gè)特性，即它總是可以找到問題的最優(yōu)解決方案。例如，從來都不會(huì)高估解法的實(shí)際支出。
Iterative-Deepening-A*( IDA*)是改良版的A*，它降低了從指數(shù)到線性實(shí)踐的空間復(fù)雜度。IDA*進(jìn)行了一系列深度優(yōu)先搜索（depth-first searches），當(dāng)邊界點(diǎn)的支出超過終止閾值時(shí)，它的分支被截?cái)?，f（n）=g（n）+h（n）。這個(gè)閾值始于初始狀態(tài)的啟發(fā)式評(píng)估，并增加每個(gè)迭代到最小值（超過原來的閾值）。IDA*在最優(yōu)解法方面和A*有著相同的特性，并且擴(kuò)展相同實(shí)例的點(diǎn)，進(jìn)一步說，就像是在一個(gè)指數(shù)樹上的A*，但是它僅使用線性空間。
A*和IDA*共同的缺點(diǎn)是：他們?cè)趯?shí)踐中運(yùn)行所發(fā)費(fèi)的時(shí)間非常多。這是獲得最優(yōu)解法不可避免的支出。如Simon所注意到的一樣，然而，最優(yōu)解法雖然相對(duì)稀少，但對(duì)于大多數(shù)的實(shí)時(shí)問題接近最優(yōu)或者“滿意”的解法通常也能被完全接受。
還有一個(gè)相關(guān)的A*和 IDA*的共同缺點(diǎn)是：他們?cè)谶M(jìn)行第一步之前必須搜索所有的解法。原因是直到找到整個(gè)解法，且證明它至少和其它解法一樣好時(shí)，才可以保住第一步是最優(yōu)的。因此，在現(xiàn)實(shí)世界中執(zhí)行產(chǎn)生的解決方案的第一步之前，A*和IDA*就在計(jì)劃或模擬階段運(yùn)行完成。這大大限制了這些算法應(yīng)用于實(shí)時(shí)應(yīng)用。
在該部分，我們展示了幾個(gè)實(shí)時(shí)問題非常重要的特性，這些特性在任何的實(shí)時(shí)啟發(fā)式搜索算法中都要被考慮到。
第一個(gè)特性是：在實(shí)際問題中，問題解決者必須面對(duì)有限的范圍。這主要是由計(jì)算或者信息的限制造成。例如，由于Fifteen Puzzle的組合方式猛增，在DEC20使用“曼哈頓距離”（Manhattan Distance）的IDA*算法時(shí)，每一個(gè)問題平均發(fā)費(fèi)的時(shí)間為5個(gè)小時(shí)。在大規(guī)模一點(diǎn)的難題將無法解決。為了防止沒有完全細(xì)節(jié)映射的消極影響，搜索范圍（迭代，在該情況下）取決于信息的限制——視覺相同能夠看到多遠(yuǎn)。盡管有著精準(zhǔn)的映射，細(xì)節(jié)的等級(jí)仍然受到限制。這引發(fā)了“fuzzy horizon”，其中地形知識(shí)的細(xì)節(jié)等級(jí)是到問題解決者距離的遞減函數(shù)。
一個(gè)相關(guān)的特性是：在實(shí)時(shí)設(shè)置中，在他們的最終結(jié)果已知之前必須采取行動(dòng)。例如，下棋時(shí)，要求棋子必須移動(dòng)以延長(zhǎng)方向選擇的搜索范圍。
最后最重要的一個(gè)特性是：行動(dòng)的支出和計(jì)劃的支出可以用相同的發(fā)生表達(dá)，引起了兩個(gè)之間的權(quán)衡。例如，如果Fifteen Puzzle的目標(biāo)是，以最短時(shí)間解決問題的同時(shí)移動(dòng)數(shù)量最少，那么相對(duì)于在機(jī)器中模擬運(yùn)動(dòng)，我們會(huì)量化時(shí)間進(jìn)行實(shí)際的物理運(yùn)動(dòng)，然后原則上我們會(huì)找到一個(gè)算法，通過平衡“思考”時(shí)間和“行動(dòng)”時(shí)間最小化解法的總時(shí)間。
在該部分，我們展示了一個(gè)簡(jiǎn)單的算法，用于在單代理（single-agent）問題的啟發(fā)式搜索（將前面所有的特性包括其中）。這相當(dāng)于雙玩家游戲（two-player game）極小極大值算法的情況。這并不新奇，因?yàn)殡p玩家游戲分享有限搜索范圍的實(shí)時(shí)特性，并且在最終結(jié)果已知之前采取行動(dòng)。首先我們?cè)O(shè)想所有的操作者有著相同的支出。
算法從當(dāng)前狀態(tài)向前搜索到固定深度（取決于計(jì)算或者信息可利用的單體信息），并且應(yīng)用啟發(fā)式評(píng)估函數(shù)到搜索前沿的點(diǎn)。在雙玩家游戲中值會(huì)被極小極大化到樹中，致使玩家之間交替移動(dòng)。在單代理（single-agent）設(shè)置中，由于單代理控制所有的運(yùn)動(dòng)，所以每一個(gè)點(diǎn)的備份值是它下一步點(diǎn)的極小值。一旦當(dāng)前狀態(tài)的下一步備份值被決定，就會(huì)在該方向上進(jìn)行單獨(dú)的最優(yōu)下一步運(yùn)動(dòng)，并且這個(gè)過程都是這樣重復(fù)的。不直接移動(dòng)到前沿點(diǎn)極小極大值的原因是：遵循最小承諾的策略。在該設(shè)想下，在安排第一步行動(dòng)之后，增加的信息（來自于擴(kuò)展搜索前沿）或許會(huì)比第一搜索更能影響到第二步的選擇。為了與極小極大值搜索對(duì)比，我們稱該算法為極小值搜索。
注意：除了交錯(cuò)模型，兩個(gè)方法的搜索過程完全不同。極小極小前瞻搜索在模擬模型中進(jìn)行，其中假設(shè)的移動(dòng)不會(huì)實(shí)際執(zhí)行，僅僅在機(jī)器中進(jìn)行模擬。在一個(gè)完整的前瞻搜索之后，找到最優(yōu)移動(dòng)由問題解決者在現(xiàn)實(shí)中進(jìn)行運(yùn)動(dòng)。隨后在當(dāng)前狀態(tài)進(jìn)行另一個(gè)前瞻搜索，和實(shí)際運(yùn)動(dòng)。
在很多普遍的情況中，操作者有著不統(tǒng)一的支出，我們必須計(jì)算目前為止路徑的支出，以便啟發(fā)式評(píng)估剩余支出。為了進(jìn)行該計(jì)算，我們采用了A*支出函數(shù)f（n）=g（n）+（h）。算法隨后前進(jìn)固定量的移動(dòng)，并且備份每一個(gè)前沿點(diǎn)的最小值f。替代方案向前搜索固定量的移動(dòng)，同時(shí)會(huì)向前搜索一個(gè)固定的g（n）支出。我們?cè)谠撛O(shè)想下采用原先的算法，即在計(jì)劃階段計(jì)算支出是移動(dòng)數(shù)量的函數(shù)，而不是實(shí)際執(zhí)行移動(dòng)支出的函數(shù)。
為了確保終止，必須注意防止問題解決者實(shí)際所走過的路徑無限循環(huán)。這已經(jīng)被完成了， 通過維持這些狀態(tài)（問題解決者實(shí)際訪問過和移動(dòng)過的狀態(tài)）的CLOSED表，和從初始狀態(tài)到當(dāng)前路徑點(diǎn)的OPEN堆棧。移動(dòng)到CLOSED狀態(tài)是結(jié)果輸出，隨后OPEN堆棧用于反向追蹤直到移動(dòng)可以用于一個(gè)新狀態(tài)。這種保守的策略禁止算法毀滅以前的運(yùn)動(dòng)，除非它遇到一個(gè)死胡同。該限制在后文中將被移除。
到這一步自然而然的會(huì)問道：是否每一個(gè)前沿點(diǎn)都必須被檢測(cè)以便找到極小值支出，或者是否存在一個(gè) α-β 剪枝的算法，在探索本質(zhì)上更少的點(diǎn)時(shí)，允許同樣的決定。如果我們的算法只使用前沿點(diǎn)評(píng)估，然后一個(gè)簡(jiǎn)單的反觀點(diǎn)可確定沒有這樣的剪枝算法存在，因?yàn)闆Q定最小值支出前沿點(diǎn)要求檢測(cè)每一個(gè)點(diǎn)。
然而，如果我們?cè)试S啟發(fā)式評(píng)估內(nèi)部點(diǎn)，且支出函數(shù)是單調(diào)函數(shù)，那么本質(zhì)上的剪枝是可行的。如果支出函數(shù)f（n）不會(huì)遞減到初始狀態(tài)，那么它就是單調(diào)函數(shù)。f（n）=g（n）+h（n）的單調(diào)性和h（n）一樣，或遵循三角形不等式，滿足最自然產(chǎn)生的啟發(fā)式函數(shù)的屬性，包括曼哈頓距離（Manhattan Distance）和空間線距離（air-line distance）。此外，如果啟發(fā)式函數(shù)是容許的但不單調(diào)，那么一個(gè)容許的，單調(diào)的函數(shù)f（n）可以顯然是以其路徑的最大值進(jìn)行構(gòu)建。
一個(gè)單調(diào)f函數(shù)允許我們應(yīng)用分支界定法（branch-and-bound）在不影響決定的情況下，大量減少檢測(cè)點(diǎn)的數(shù)量。類比于α-β 剪枝算法我們稱該算法為α剪枝算法，如下：在生成樹的過程中，保持在一個(gè)變量α（它是搜索范圍中目前所有遇到點(diǎn)的f最低值）。當(dāng)每一個(gè)內(nèi)部點(diǎn)生成時(shí)計(jì)算f的值，并在f的值等于α?xí)r切斷相應(yīng)的分支?？梢赃@樣做的原因是因?yàn)楹瘮?shù)是單調(diào)的，前沿點(diǎn)f的值只能從更好或者等于該點(diǎn)支出的點(diǎn)開始遞減，并且不可以影響到運(yùn)動(dòng)，因?yàn)槲覀儍H移向最小值的前沿點(diǎn)。當(dāng)每一個(gè)前沿點(diǎn)生成時(shí)，同樣計(jì)算f值，如果它小于α，就用更小的值代替α，并且進(jìn)行搜索。
在使用曼哈頓距離（Manhattan Distance）評(píng)估函數(shù)的Fifteen Puzzle實(shí)驗(yàn)中，α剪枝算法通過遠(yuǎn)遠(yuǎn)多于蠻力分支因子（brute-force branching factor從2.13到1.41）的平方根減少了有效分支因子。在相同數(shù)量的計(jì)算時(shí)，它的效果比兩倍的搜索范圍效果還好。例如，如果計(jì)算源允許在移動(dòng)時(shí)檢測(cè)上百萬的點(diǎn)，那么β壓迫算法可以搜索深度為18的移動(dòng)，而α剪枝算法允許搜索將近兩倍的深度（40步移動(dòng)）。
α剪枝算法中，α剪枝算法的效率可以通過node ordring進(jìn)行提升。該想法命令每一個(gè)內(nèi)部點(diǎn)的繼承點(diǎn)增加f值的次序，希望找到更早的找到前沿點(diǎn)的最低支出，并更快的裁剪跟多的分支。
盡管這兩種算法是各自發(fā)展的，最小化α剪枝算法非常類似于iterative-deepening-A*的單獨(dú)迭代。唯一的不同點(diǎn)是在α剪枝算法中，中止閾值由前沿點(diǎn)最小值動(dòng)態(tài)決定和調(diào)整的，而不是由先前在IDA *中迭代預(yù)先靜止和設(shè)置的。
目前為止我們?cè)O(shè)想了，行為一旦被執(zhí)行除非遇到死胡同，不然它不會(huì)被逆轉(zhuǎn)。——主要的動(dòng)機(jī)是阻止問題解決者無限循環(huán)。我們現(xiàn)在解決的問題是：如何在它有用進(jìn)行返回，而不是死胡同時(shí)返回，同時(shí)仍然反正無效循環(huán)?；鞠敕ǚ浅：?jiǎn)單。從狀態(tài)（加返回的支出）到狀態(tài)（少于從當(dāng)前狀態(tài)向前移動(dòng)的評(píng)估支出）評(píng)估解決方法時(shí)，它應(yīng)該返回到原來的狀態(tài)。Real-Time-A*是實(shí)施這一基本想法非常有效的一個(gè)算法。
最小值前瞻算法是控制搜索仿真階段的算法，RTA *是控制搜索執(zhí)行階段的算法。因此，它獨(dú)立于所選擇的模擬算法。簡(jiǎn)單的說，我們假設(shè)：極小極小前瞻深度是封裝在計(jì)算h（n）內(nèi)部的，因此，變得簡(jiǎn)單，更準(zhǔn)確，和更昂貴的方式計(jì)算h（n）。
RTA *中，點(diǎn)n的優(yōu)點(diǎn)是f（n）=g（n）+h（n），如A *中的一樣。然而，不像A *的是，RTA *中g(shù)（n）的理解是點(diǎn)n到問題解決者當(dāng)前狀態(tài)的距離，而不是原來的初始狀態(tài)。RTA *只不過是給出略有不同支出函數(shù)的最好的第一搜索。原則上，它可以通過儲(chǔ)存原先所有訪問過的點(diǎn)的h值OPEN表實(shí)現(xiàn)，并且每一次移動(dòng)，都會(huì)更新OPEN上所有狀態(tài)的g值，以便準(zhǔn)確反映它們到新的當(dāng)前狀態(tài)的實(shí)際距離。然后在每一個(gè)移動(dòng)循環(huán)，問題解決者通過g+h的最小值選擇下一個(gè)狀態(tài)，向它移動(dòng)，并且再一次更新OPEN上所有狀態(tài)的g值。
這種單純實(shí)現(xiàn)的缺點(diǎn)是：1）在OPEN列表中時(shí)間的大小是進(jìn)行線性移動(dòng)的。2）不是非常的清楚如何更新g的值，3）不清楚如何如何從OPEN中選擇下一個(gè)目標(biāo)節(jié)點(diǎn)的路徑。有趣的是，在恒定的時(shí)間中，每次只使用圖中本地的信息移動(dòng)就可以解決這些問題。想法如下：從給定的當(dāng)前狀態(tài)，相鄰的狀態(tài)可以產(chǎn)生，啟發(fā)式函數(shù)通過前向搜索增強(qiáng)（這適用于所有情況）然后，每一個(gè)鄰近狀態(tài)的邊緣支出會(huì)增加這個(gè)值，產(chǎn)生當(dāng)前狀態(tài)每一個(gè)鄰域的f值。有著極小f值的點(diǎn)是從新的當(dāng)前狀態(tài)和移動(dòng)（已經(jīng)被執(zhí)行的狀態(tài)）中選擇出來的。與此同時(shí)，下一個(gè)f值儲(chǔ)存在以前的當(dāng)前狀態(tài)。
這代表了通過回到原狀態(tài)來解決此類問題所需的代價(jià)h。接下來，新狀態(tài)下的新鄰近點(diǎn)就產(chǎn)生了，而它們的h值也就此進(jìn)行計(jì)算，并且所有新狀態(tài)下的鄰近點(diǎn)的邊成本包括之前的狀態(tài)的都會(huì)加入h值中，導(dǎo)致了所有鄰近狀態(tài)一系列的f值。再一次，節(jié)點(diǎn)值最小的會(huì)被除去，第二優(yōu)的節(jié)點(diǎn)值會(huì)儲(chǔ)存在舊狀態(tài)的h值中。
注意到RTA不需要吧OPEN和CLOSED列表分開，之前評(píng)價(jià)過的節(jié)點(diǎn)值的單一列表就以足夠。表的規(guī)模與移動(dòng)的步數(shù)成線性關(guān)系，因?yàn)榍梆佀阉鲀H僅只會(huì)保留根節(jié)點(diǎn)值。并且運(yùn)行時(shí)間也與步數(shù)成線性關(guān)系。原因在于盡管前饋研究所需時(shí)間與研究的深度成指數(shù)增長(zhǎng)的關(guān)系，但研究深度會(huì)受到常數(shù)的約束。
有趣的是，人能夠創(chuàng)建一個(gè)例子證明RTA*在在同一領(lǐng)域內(nèi)追溯任意次數(shù)。例如，在圖1中最簡(jiǎn)單的strighthne圖，最開始的狀態(tài)是節(jié)點(diǎn)a，所有的edge有一個(gè)總體的值，而在每一個(gè)節(jié)點(diǎn)下的數(shù)值就代表了這些節(jié)點(diǎn)的啟發(fā)式評(píng)價(jià)。因?yàn)榍梆佒粫?huì)讓例子變得更加復(fù)雜，我們會(huì)假設(shè)沒有前饋能去計(jì)算h值。并在節(jié)點(diǎn)a開始，f(b)=g(b)+h(b)=1+1=2，但f(c)=g(c)+h(c)=1+2=3。因此，問題求解程序移向節(jié)點(diǎn)b，并把節(jié)點(diǎn)a遺留在h(a)=3的信息狀態(tài)。接下來，節(jié)點(diǎn)d會(huì)在f(d)=g(d)+h(d)=1+4=5結(jié)果下進(jìn)行評(píng)價(jià)，所以節(jié)點(diǎn)a就變成了f(a)=g(a)+h(a)=1+3=4的結(jié)果。因此問題求解程序就移回了節(jié)點(diǎn)a，而在節(jié)點(diǎn)b之后的h(b)=5?；诖它c(diǎn)，f(b)=g(b)+h(b)=1+5=6，并且f(c)=g(c)+h(c)=1+2=3，導(dǎo)致問題求解程序又移到了節(jié)點(diǎn)c，讓在節(jié)點(diǎn)a之后的h(a)=6。閱讀者會(huì)迫不及待的把實(shí)例繼續(xù)進(jìn)行下去以見證問題求解程序不斷地往返，直到達(dá)到目標(biāo)。其原理不是在于它是一個(gè)無限的環(huán)，而是在于當(dāng)它每改變一次方向，就能比之前更深入一步，就能收集到更多關(guān)于空間的信息。這看似不合理的行為是由合理的行為在有限的探索界限和病理空間內(nèi)產(chǎn)生的。
不幸的是，RTA*的追溯能力不能作為Fifteen Puzzle和Manhattan Distance評(píng)價(jià)函數(shù)。因?yàn)樵谟贛anhattan Distance在一次移動(dòng)中只會(huì)改變一次，而這會(huì)讓RTA*在追溯一次就終止。
除了算法的效率之外，由最小前饋搜索所帶來的解決方法長(zhǎng)度也是關(guān)注的焦點(diǎn)。最正常的期待是希望隨著解決長(zhǎng)度的減少而深度卻會(huì)增加。在帶有Fifteen Puzzle的實(shí)驗(yàn)中使用Manhattan Distance，結(jié)果顯示是期待是正確的，但并不一致。
Fifteen Puzzle的一千個(gè)原始解決狀態(tài)是隨機(jī)產(chǎn)生的。對(duì)于每一個(gè)原始狀態(tài)，阿爾法剪枝算法的最小值是在搜索深度在1步到30步之間。為找到解決方法，會(huì)不停的進(jìn)行移動(dòng)，所以步數(shù)達(dá)到一千步也是有可能的，所以為防止步數(shù)過長(zhǎng)，會(huì)對(duì)所有的結(jié)果步數(shù)進(jìn)行記錄。圖2顯示的是在所有超過千步的解決方法中平均解決的長(zhǎng)度以及搜索限制的深度。底部的線顯示的是在100個(gè)不同的原始狀態(tài)中53個(gè)平均最優(yōu)步驟。最優(yōu)解決方法的長(zhǎng)度是使用IDA*進(jìn)行計(jì)算的，需要幾周的CPU時(shí)間去解決上百的原始狀態(tài)。
曲線的大體形狀肯定了最初的假設(shè)增加搜索范圍限制能減少解決運(yùn)算成本。在深度為25時(shí)，平均的解決方法的長(zhǎng)度只在一個(gè)因素上優(yōu)于最優(yōu)解決方案的平均長(zhǎng)度。這一結(jié)果的實(shí)現(xiàn)是通過只在每一步只搜索6000個(gè)節(jié)點(diǎn)，或是整個(gè)解決過程只搜索6000,000個(gè)節(jié)點(diǎn)。這一過程能在Hewlett-Packard HP-9000工作站中只需CPU一分鐘的運(yùn)行時(shí)間。
但是在深度為3,10或是11時(shí)，增加的搜索限制會(huì)導(dǎo)致解決方法長(zhǎng)度的輕微增加。這一現(xiàn)象首先是在有兩個(gè)玩家的游戲中和Dana Nau命名的Pathology中發(fā)現(xiàn)的。他發(fā)現(xiàn)在某些游戲中，增加搜索深度但游戲結(jié)果還是較差。直到，在真實(shí)游戲中進(jìn)行路徑觀察。
盡管在涉及到大量問題時(shí)路徑的影響會(huì)相對(duì)來說較小，但在單個(gè)問題上，其影響還是很重要的。在多數(shù)案例中，通過一步來增加搜索的深度會(huì)讓解決方法的長(zhǎng)度增加上百步。
為更好的理解這一現(xiàn)象，我們對(duì)“決定質(zhì)量”進(jìn)行試驗(yàn)，這與解決方法質(zhì)量是相對(duì)應(yīng)的。它們之間的區(qū)別在于一個(gè)解決方法包括大量的個(gè)別決定。解決方法的質(zhì)量是由解決方法的長(zhǎng)度決定的，決定的質(zhì)量是由最優(yōu)步選擇所花的時(shí)間決定的。因?yàn)樵谝粋€(gè)狀態(tài)下必須知道最優(yōu)步才能確定決定的質(zhì)量，所以要選擇較小或是叫溫順的Eight Puzzle，并用相同的Manhattan Distance評(píng)價(jià)函數(shù)。
圖2：搜索限制VS 解決長(zhǎng)度
在這個(gè)情況下，成千上萬原始狀態(tài)是隨機(jī)產(chǎn)生的。我們不會(huì)探索整個(gè)解決方法，因?yàn)檫@是由最小算法產(chǎn)生的；我們僅僅最考慮原始狀態(tài)下的第一步移動(dòng)。在不同的搜索限制和不同起始狀態(tài)下，第一步的最優(yōu)步的決定時(shí)間都會(huì)被記錄下來。搜索限制的范圍從一步到低于最優(yōu)選擇的步數(shù)。圖3展示的是錯(cuò)誤率和搜索限制。隨著搜索限制的增加，最優(yōu)步數(shù)也會(huì)隨之增加。因此，pathology并未在決定質(zhì)量方面出現(xiàn)。
如果決定的質(zhì)量能隨著搜索的深度而增加，那為什么解決方法的質(zhì)量會(huì)如此飄忽不定？其中一個(gè)原因是當(dāng)犯錯(cuò)的幾率增加時(shí)，就整體解決成本而言，個(gè)別錯(cuò)誤的代價(jià)就會(huì)變高。這一點(diǎn)在追溯僅在遇到死胡同才會(huì)發(fā)生時(shí)表現(xiàn)的尤為明顯。
圖3：搜索限制VS.決定質(zhì)量
另一個(gè)錯(cuò)誤的根源在于節(jié)點(diǎn)位于備選方案之中。當(dāng)信息不確定是必須確定移動(dòng)，但連接不應(yīng)隨意破壞。更加普遍一點(diǎn)，當(dāng)基于不準(zhǔn)確的啟發(fā)評(píng)價(jià)時(shí)進(jìn)行處理，兩個(gè)數(shù)值更加接近函數(shù)的準(zhǔn)確度不應(yīng)該被認(rèn)為是虛擬的連接，而對(duì)于這一的處理也應(yīng)是把它們看做是無法區(qū)分的。為解決這一問題，連接和虛擬連接必須在第一眼就認(rèn)出來。這也就意味著當(dāng)數(shù)值超過最初由錯(cuò)誤因素所影響的最好結(jié)果之后，阿爾法剪枝算法必須改變。這會(huì)導(dǎo)致由此產(chǎn)生的節(jié)點(diǎn)的增加。
一旦確認(rèn)節(jié)點(diǎn)之后，必須破壞它。最理想的方法是在候選方案之中實(shí)施更深度的二次搜索，直到連接崩壞。然而，這一二次搜索也有深度的限制。如果二次搜索達(dá)到了深度限制，而連接沒有崩壞，虛擬連接會(huì)在較低成本下解體。
用前饋搜索檢查啟發(fā)式評(píng)價(jià)函數(shù)，根據(jù)搜索的深度不同，更準(zhǔn)確的啟發(fā)式函數(shù)能生出一系列啟發(fā)式函數(shù)。而這一系列的函數(shù)計(jì)算復(fù)雜性和準(zhǔn)確度都不一樣，但一般更加昂貴的函數(shù)就算的要更準(zhǔn)確一些。
選擇哪一個(gè)評(píng)價(jià)函數(shù)去平衡搜索成本和決定成本。時(shí)間最小化依賴于相關(guān)的計(jì)算成本和決定，但一個(gè)合理的模式是彼此都是相互成線性關(guān)系。換一種說法如果我們假設(shè)在實(shí)際中運(yùn)用一個(gè)運(yùn)算操作的成本是在所有模擬實(shí)驗(yàn)中運(yùn)用的總和。
圖4顯示出與圖2相同的數(shù)據(jù)，但是水平軸線與每一步節(jié)點(diǎn)的產(chǎn)生數(shù)量成線性關(guān)系，這與搜索的深度也有很大的關(guān)系。這一曲線圖顯示了計(jì)算—執(zhí)行在最初某種程度上是有利的，例如小量的計(jì)算增加會(huì)帶來大量的決定成本減少。但是，當(dāng)達(dá)到減少轉(zhuǎn)折點(diǎn)時(shí)，決定成本上的減少需要大量的計(jì)算。這一影響還有可能比當(dāng)初的還要大，因?yàn)殚L(zhǎng)度決定過程需要任意一百步。不同的計(jì)算成本和執(zhí)行之間的關(guān)系會(huì)改變兩個(gè)軸之間的關(guān)系，但不會(huì)改變基本的曲線的基本形狀L。
現(xiàn)存的單代理啟發(fā)式算法不能在實(shí)際中進(jìn)行運(yùn)用，因?yàn)橛?jì)算成本在停止計(jì)算之前都無法預(yù)知。最小化的前饋搜索是對(duì)于這類問題的最好解決方法。此外，α剪枝算法能提高算法的有效性，但卻不影響決定的執(zhí)行。此外，實(shí)時(shí)α算法解決了當(dāng)遇見更有希望的算法而放棄當(dāng)前算法的問題。大量的模擬顯示搜索深度增加一般會(huì)提高決定的質(zhì)量，但是出現(xiàn)與之相反的情況也是正常的。為避免虛擬連接對(duì)于決定質(zhì)量產(chǎn)生決定性影響，附加算法也是很必要的。最后，前饋算法能看成是產(chǎn)生一系列具有不同準(zhǔn)確度和計(jì)算難度的搜索。決定質(zhì)量和計(jì)算成本之間最初是相互支持的關(guān)系，但到同時(shí)也會(huì)迅速達(dá)到一個(gè)收益遞減的點(diǎn)。
via：論文原址
哈爾濱工業(yè)大學(xué)李衍杰副教授的點(diǎn)評(píng)：由于傳統(tǒng)單智能體啟發(fā)式搜索算法，如A*算法，計(jì)算量比較大，且需要搜索完最終結(jié)果后才能執(zhí)行，因而不適用于實(shí)時(shí)性要求比較高的場(chǎng)合，為此，這篇論文研究了實(shí)時(shí)啟發(fā)性搜索的問題，文中利用最小最小（minimin）前瞻搜索來避免傳統(tǒng)啟發(fā)式搜索所存在的前面所述問題，同時(shí)利用alpha剪枝方法來改進(jìn)算法的效率，這兩種思路的結(jié)合實(shí)際上是IDA*算法的一個(gè)自適應(yīng)版本，即剪枝閾值隨搜索節(jié)點(diǎn)的變化自適應(yīng)地動(dòng)態(tài)調(diào)整，而非像IDA*算法那樣靜態(tài)預(yù)先設(shè)定。此外，文中給出了一種實(shí)時(shí)的A*算法來實(shí)現(xiàn)當(dāng)前搜索路徑到更好的路徑的轉(zhuǎn)換。
PS : 本文由雷鋒網(wǎng)(搜索“雷鋒網(wǎng)”公眾號(hào)關(guān)注)獨(dú)家編譯，未經(jīng)許可拒絕轉(zhuǎn)載！
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
