4.15 重復(fù)第五階段：版本2的分析

關(guān)于GPS在多個(gè)問題領(lǐng)域內(nèi)的擴(kuò)展性我們已經(jīng)展示過了。重點(diǎn)就在于我們不需要改變程序本身來適應(yīng)新的問題；我們僅僅改變傳遞給GPS的操作符列表就可以了。在不同問題上的經(jīng)驗(yàn)確實(shí)也顯示要做出一些更改，我們也展示了如何去適應(yīng)一些改變。雖然版本2比版本1 有了大的改進(jìn)，仍然還是有很多問題?，F(xiàn)在我們就發(fā)現(xiàn)了一些最棘手的問題。

4.16 不跳就不看的問題

我們解決跳之前看一看問題的方式是引入一些變量來保存一個(gè)未來可能的程序狀態(tài)的表示，而不是僅僅使用單一變量來存儲(chǔ)當(dāng)前的狀態(tài)。這防止了GPS做出一些不好的行為，但是我們也會(huì)看到即使是所有的預(yù)防手段在最后一節(jié)都引入之后，還是不能保證可用的解決方法可以計(jì)算得出。
為了找到這個(gè)問題，在school-ops列表之前加上另一個(gè)操作符，并且把調(diào)試輸出打開。
(use (push (op ‘taxi-son-to-school
:preconds ‘(son-at-home have-money)
:add-list ‘(son-at-school)
:del-list ‘(son-at-home have-money))
*school-ops*))
(debug :gps)

現(xiàn)在設(shè)想一下不適用任何錢就把孩子送到學(xué)校的問題：
> (gps '(son-at-home have-money car-works)
'(son-at-school have-money))
Goal: SON-AT-SCHOOL
Consider: TAXI-SON-TO-SCHOOL
Goal: SON-AT-HOME
Goal: HAVE-MONEY
Action: TAXI-SON-TO-SCHOOL
Goal: HAVE-MONEY
Goal: HAVE-MONEY
Goal: SON-AT-SCHOOL
Consider: TAXI-SON-TO-SCHOOL
Goal: SON-AT-HOME
Goal: HAVE-MONEY
Action: TAXI-SON-TO-SCHOOL
NIL

頭五行輸出顯示成功解決了兒子在學(xué)校這個(gè)目標(biāo)，但是后面遇到還有錢的目標(biāo)是顯示失敗了。下一步就是嘗試換一下順序。這一次，首先嘗試有錢這個(gè)目標(biāo)，成功了，之后孩子在學(xué)校這個(gè)目標(biāo)被行為打出租去學(xué)校行為完成。但是在achieve-all檢查一致性的時(shí)候失敗了，而且沒有挽回的手段。目標(biāo)失敗，即使是說有一個(gè)合法的方法存在：開車去學(xué)校。
問題在于achieve使用some來尋找appropriate-ops。因此，如果有合適的操作符，achieve就完成了。如果僅僅是有一個(gè)目標(biāo)的話，這的確是一個(gè)好方法。然而，如果是有多個(gè)目標(biāo)，就像上面的情況，achieve會(huì)只找到一個(gè)滿足第一個(gè)目標(biāo)的方法，如果這個(gè)方法失敗，為一個(gè)挽救方法就是嘗試修補(bǔ)這個(gè)方法。在如積木世界和迷宮世界的問題中，修補(bǔ)常常是可行的，因?yàn)樗械牟襟E都是可逆的。但是在出租車這個(gè)例子中的話，錢一旦花出去了，就沒有修補(bǔ)方案可以挽回了，整個(gè)計(jì)劃就會(huì)失敗。
解決這個(gè)問題主要有兩種方式，第一種是事先檢測(cè)所有可能的解決方案，而不僅僅是滿足子目標(biāo)的第一個(gè)方案。Prolog語言，會(huì)在第11章討論的內(nèi)容中，就是這么干的。第二種方式是讓achieve和achieve-all追蹤一個(gè)被保護(hù)的目標(biāo)的列表。在出租車這個(gè)例子中，我們先完成了還有錢這個(gè)目標(biāo)之后嘗試完成把孩子送學(xué)校這個(gè)目標(biāo)，但是會(huì)先把還有錢這個(gè)目標(biāo)保護(hù)起來，有所保留。如果一個(gè)操作符僅僅是因?yàn)楸槐Ｗo(hù)目標(biāo)的刪除而合適的話，就會(huì)要求程序進(jìn)行一些修補(bǔ)，檢索更多的方案。

4.17 描述力缺乏的問題

在迷宮問題中，如果是有一個(gè)操作符可以將我們從這里移到那里，如果說這里到那里有一個(gè)連接存在的話，那么就會(huì)顯得簡單高效很多了。對(duì)于一些特定問題的輸入也哭了一列出一些合法的連接，我們可以使用單一的操作符來解決迷宮問題。相似的，我們可以定義一個(gè)操作符在猴子把椅子從門口推向屋里的動(dòng)作，一般化成吧鄰近的任意位置的可以推的東西推向任意位置，只要中間沒有障礙物就好了。這個(gè)結(jié)論可以到處操作符中會(huì)有變量，所以我們可以這么說：
(op ‘(push X from A to B)
?:preconds ‘((monkey at A) (X at A) (pushable X) (path A B))
?:add-list ‘((monkey at B) (X at B))
?:del-list ‘((monkey at A) (X at A)))

經(jīng)常性的，我們廟會(huì)一些特征是根據(jù)比一系列的條件更加抽象的事物來描述的。例如，在下棋問題中，目標(biāo)是將對(duì)手的軍，是一種難以用簡單斷言來描述的情況，比如(black king A 4)，所以我們?cè)诮Y(jié)果狀態(tài)中需要一種常量來能夠做出描述，而不是僅僅列出它的組件。我們可能希望能夠獲取條件的分離或者否決，在當(dāng)前狀態(tài)下只允許一種組合的時(shí)候。
在很多問題中，能夠描述處理時(shí)間的問題也是很重要的：我們想要在時(shí)間T0之前大城目標(biāo)X，之后在時(shí)間T2之前但是一定要在T1之后，達(dá)成目標(biāo)Y。時(shí)間表在工廠中的應(yīng)用就是個(gè)例子，時(shí)間扮演了很重要的角色。
花費(fèi)，經(jīng)常是和行為有相關(guān)性的，所以我們就尋找最小花費(fèi)的解決方法，或者是接近最小花費(fèi)?；ㄙM(fèi)的意思也許就是解決方法所要求的操作符執(zhí)行的數(shù)量，在積木世界問題中我們看到一個(gè)唄應(yīng)用的操作符可以被馬上忽略，轉(zhuǎn)而被一個(gè)需要滿足一些先決條件的操作符取代?；蛘呶覀兛赡苤恍U夷一部分的解決方案，如果整體的解決方案不可行或者太火昂貴的話，我們也許會(huì)想要花費(fèi)計(jì)算空間來換取時(shí)間。

4.18 完美信息問題

我們之前遇到過的所有操作符都有明晰的結(jié)果；從當(dāng)前狀態(tài)中增加或者刪除指定的東西，GPS總是準(zhǔn)確的知道他要做什么。在真實(shí)世界中，事情不是這么明了和干脆的。我們回到變有錢這個(gè)問題上來，一個(gè)比較中肯的操作符是去買彩票。這操作符的效果是花費(fèi)一些鈔票來換取中彩票的幾率。但是這僅僅是幾率，小的可憐。相似的，我們不能忽視具體事情執(zhí)行的時(shí)候，會(huì)發(fā)生意想不到的困難。在送孩子去學(xué)校問題中，我們說的是車子的問題在于電池，GPS的顯式檢查來看看車子是不是可以工作?；蛘咝枰姵?，每一次程序都會(huì)考慮開車這個(gè)操作符。在現(xiàn)實(shí)世界中，很少會(huì)這么小心，我們坐進(jìn)車子里，僅僅是在不能開的時(shí)候才會(huì)想到是電池的問題。

4.19 相互作用的目標(biāo)問題

人們往往傾向于同時(shí)有多個(gè)目標(biāo)，而不是一次搞定一個(gè)再去想下一個(gè)。不僅僅是開車送孩子去學(xué)校，還要同時(shí)注意不被別的車子撞上，準(zhǔn)時(shí)上班，搞定工作任務(wù)，見見朋友，找點(diǎn)樂子，保持呼吸，等等等等。也是要不得不自己去發(fā)現(xiàn)目標(biāo)，而不是由其他人來告訴你一些預(yù)先定義好的目標(biāo)。有一些目標(biāo)我們可以放在心里好幾年之久，之后等時(shí)機(jī)成熟了在執(zhí)行完成。沒有一種合適所有目標(biāo)的標(biāo)記方法。但是卻有一中完成一些目標(biāo)的可持續(xù)過程，完成一部分，放棄或者推遲另外一部分。
除了達(dá)成既有的目標(biāo)之外，人們還會(huì)注意防止需要避免的情況出現(xiàn)。例如，假設(shè)我有一個(gè)朋友住醫(yī)院了，我想去看望看望他，這就需要我人到醫(yī)院這么一個(gè)行為。一個(gè)可用的操作符就是走去醫(yī)院，還有另一個(gè)操作符是故意把自己弄傷等救護(hù)車來送我去，或許會(huì)更快。第二個(gè)操作符僅僅是達(dá)成了目標(biāo)，但是去產(chǎn)生了人們不想要的副作用。這可能會(huì)記錄在方案花費(fèi)的標(biāo)記中，人們會(huì)避免對(duì)一些背景的目標(biāo)有所損害，比如個(gè)人的健康。
Herb Simon提出了術(shù)語滿意度來描述達(dá)成一個(gè)合理水平的合理目標(biāo)的策略，也包含了同時(shí)推遲或者放棄的其他目標(biāo)的影響。GPS僅僅知道成功和失敗，因此僅僅是片面成功的最大化罷了。

4.20 GPS的最后

最后四個(gè)小節(jié)的內(nèi)容給出了對(duì)于GPS局限的領(lǐng)域的一些暗示。事實(shí)上，GPS并不是一個(gè)完全通用的問題解決程序。在算法沒有綁定特定領(lǐng)域問題的層面上，他的確是個(gè)通用的程序；我們也可以通過更改操作符來更改問題領(lǐng)域。但是GPS在無法解決很多有趣的問題的時(shí)候就是去了通用性。限制在一些小的技巧和游戲之中。
GPS最終失敗的原因很是微妙，其中一個(gè)就是說他出現(xiàn)在不被世人欣賞的1957年，去愛現(xiàn)在成了計(jì)算機(jī)科學(xué)的核心。現(xiàn)在一些被認(rèn)為是計(jì)算機(jī)無法解決的問題，并不是說理論上正確的程序?qū)懖怀鰜恚且驗(yàn)槌绦驁?zhí)行的時(shí)間實(shí)在是太長。很多問題都被歸類為這類叫做NP困難問題。計(jì)算這些問題的時(shí)間隨著問題的規(guī)模的增長，時(shí)間呈指數(shù)級(jí)增長。這是因?yàn)閱栴}本身的特性導(dǎo)致的，跟程序員本身的質(zhì)素沒有關(guān)系。指數(shù)級(jí)增長的意思是五個(gè)輸入會(huì)花費(fèi)幾秒鐘求解的問題，100個(gè)輸入就需要幾億年的時(shí)間來處理了。即使買更快的電腦也無濟(jì)于事。最終來說，如果你有一個(gè)需要幾億年才能解決的問題，買了100臺(tái)比現(xiàn)在的電腦快1000倍的電腦來處理，也還是要等上幾百萬年的。對(duì)于理論計(jì)算機(jī)科學(xué)家來說，發(fā)現(xiàn)問題是NP困難問題就是答案本身了，但是對(duì)于AI來說，就以為這被問了錯(cuò)誤的問題。很多NP困難問題在我們不堅(jiān)持最佳解決方案，退而求其次的時(shí)候就會(huì)簡單很多了。
GPS的輸入基本上就是一個(gè)程序，GPS的執(zhí)行也就是程序的執(zhí)行。如果GPS的輸入語言組足夠通用可以用來表達(dá)任何程序。那他不能解決的問題要么沒有答案要么時(shí)間太長?，F(xiàn)代的問題解決程序會(huì)辨認(rèn)這些基礎(chǔ)的制限，或者限制問題的規(guī)模，或者找一個(gè)接近的解決方法或者部分的解決。一些問題解決程序也會(huì)監(jiān)視執(zhí)行時(shí)間，當(dāng)問題太過困難就會(huì)放棄執(zhí)行。
下面引用的話是出自Drew McDermott的文章《人工智能遇上天然的愚蠢》，概括了當(dāng)時(shí)對(duì)于GPS的感覺。記住它，下次你不得不評(píng)價(jià)一個(gè)程序的時(shí)候會(huì)有用的。
GPS？現(xiàn)在，GPS就是一個(gè)沒有意義的術(shù)語，僅僅是給出了一個(gè)解謎語的愚蠢程序。但是他既然叫做一般問題解決器，但是僅僅是吊起了人們沒有意義的興奮和好奇。他應(yīng)該叫做LFGNS，本地特定導(dǎo)引萬羅搜索器。
盡管如此，GPS還是一個(gè)用來瀏覽編程技巧的有用程序，特別是在AI編程這方面。更重要的是，他會(huì)是一個(gè)來看純粹的思考的工具。當(dāng)然我們承認(rèn)亞里士多德要比你我聰明的多，用隱喻來說明計(jì)算模型的概念，使人們更加欣賞目的手段分析法了，至少是在計(jì)算模型這個(gè)方面。我們也必須堅(jiān)持并不是所有的思考都是按照這個(gè)模型走的。
AI的吸引力在于一種目的和手段的分離。一個(gè)成功的AI項(xiàng)目的結(jié)果可以使一個(gè)程序，吧之前能做的事情做的更好更快。在這意義上來說，GPS是一個(gè)失敗之作，沒有很好地解決特定的問題。但是他對(duì)于問題解決過程的調(diào)查和格式化，從某種程度上來說是陳宮的，讓讀者對(duì)整個(gè)過程有個(gè)更好的理解。