4.15 重復(fù)第五階段：版本2的分析
關(guān)于GPS在多個問題領(lǐng)域內(nèi)的擴展性我們已經(jīng)展示過了。重點就在于我們不需要改變程序本身來適應(yīng)新的問題续扔；我們僅僅改變傳遞給GPS的操作符列表就可以了攻臀。在不同問題上的經(jīng)驗確實也顯示要做出一些更改，我們也展示了如何去適應(yīng)一些改變纱昧。雖然版本2比版本1 有了大的改進刨啸，仍然還是有很多問題。現(xiàn)在我們就發(fā)現(xiàn)了一些最棘手的問題砌些。
4.16 不跳就不看的問題
我們解決跳之前看一看問題的方式是引入一些變量來保存一個未來可能的程序狀態(tài)的表示呜投，而不是僅僅使用單一變量來存儲當前的狀態(tài)。這防止了GPS做出一些不好的行為存璃，但是我們也會看到即使是所有的預(yù)防手段在最后一節(jié)都引入之后仑荐，還是不能保證可用的解決方法可以計算得出。
為了找到這個問題纵东，在school-ops列表之前加上另一個操作符粘招，并且把調(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é)校這個目標偎球，但是后面遇到還有錢的目標是顯示失敗了洒扎。下一步就是嘗試換一下順序。這一次衰絮，首先嘗試有錢這個目標袍冷，成功了，之后孩子在學(xué)校這個目標被行為打出租去學(xué)校行為完成猫牡。但是在achieve-all檢查一致性的時候失敗了胡诗，而且沒有挽回的手段。目標失敗，即使是說有一個合法的方法存在：開車去學(xué)校煌恢。
問題在于achieve使用some來尋找appropriate-ops骇陈。因此，如果有合適的操作符瑰抵，achieve就完成了你雌。如果僅僅是有一個目標的話，這的確是一個好方法二汛。然而婿崭，如果是有多個目標，就像上面的情況习贫，achieve會只找到一個滿足第一個目標的方法逛球，如果這個方法失敗，為一個挽救方法就是嘗試修補這個方法苫昌。在如積木世界和迷宮世界的問題中，修補常常是可行的幸海，因為所有的步驟都是可逆的祟身。但是在出租車這個例子中的話，錢一旦花出去了物独，就沒有修補方案可以挽回了袜硫，整個計劃就會失敗。
解決這個問題主要有兩種方式挡篓，第一種是事先檢測所有可能的解決方案婉陷，而不僅僅是滿足子目標的第一個方案。Prolog語言官研，會在第11章討論的內(nèi)容中秽澳，就是這么干的。第二種方式是讓achieve和achieve-all追蹤一個被保護的目標的列表戏羽。在出租車這個例子中担神，我們先完成了還有錢這個目標之后嘗試完成把孩子送學(xué)校這個目標，但是會先把還有錢這個目標保護起來始花，有所保留妄讯。如果一個操作符僅僅是因為被保護目標的刪除而合適的話，就會要求程序進行一些修補酷宵，檢索更多的方案亥贸。
4.17 描述力缺乏的問題
在迷宮問題中，如果是有一個操作符可以將我們從這里移到那里浇垦，如果說這里到那里有一個連接存在的話炕置，那么就會顯得簡單高效很多了。對于一些特定問題的輸入也哭了一列出一些合法的連接，我們可以使用單一的操作符來解決迷宮問題讹俊。相似的垦沉，我們可以定義一個操作符在猴子把椅子從門口推向屋里的動作，一般化成吧鄰近的任意位置的可以推的東西推向任意位置仍劈，只要中間沒有障礙物就好了厕倍。這個結(jié)論可以到處操作符中會有變量，所以我們可以這么說：
(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)常性的贩疙，我們廟會一些特征是根據(jù)比一系列的條件更加抽象的事物來描述的讹弯。例如，在下棋問題中这溅，目標是將對手的軍组民，是一種難以用簡單斷言來描述的情況，比如(black king A 4)悲靴，所以我們在結(jié)果狀態(tài)中需要一種常量來能夠做出描述臭胜，而不是僅僅列出它的組件。我們可能希望能夠獲取條件的分離或者否決癞尚，在當前狀態(tài)下只允許一種組合的時候耸三。
在很多問題中，能夠描述處理時間的問題也是很重要的：我們想要在時間T0之前大城目標X浇揩，之后在時間T2之前但是一定要在T1之后仪壮，達成目標Y。時間表在工廠中的應(yīng)用就是個例子胳徽，時間扮演了很重要的角色积锅。
花費，經(jīng)常是和行為有相關(guān)性的养盗，所以我們就尋找最小花費的解決方法缚陷，或者是接近最小花費∽希花費的意思也許就是解決方法所要求的操作符執(zhí)行的數(shù)量蹬跃，在積木世界問題中我們看到一個唄應(yīng)用的操作符可以被馬上忽略，轉(zhuǎn)而被一個需要滿足一些先決條件的操作符取代铆铆〉海或者我們可能只蠻夷一部分的解決方案，如果整體的解決方案不可行或者太火昂貴的話薄货，我們也許會想要花費計算空間來換取時間翁都。
4.18 完美信息問題
我們之前遇到過的所有操作符都有明晰的結(jié)果；從當前狀態(tài)中增加或者刪除指定的東西谅猾，GPS總是準確的知道他要做什么柄慰。在真實世界中鳍悠，事情不是這么明了和干脆的。我們回到變有錢這個問題上來坐搔，一個比較中肯的操作符是去買彩票藏研。這操作符的效果是花費一些鈔票來換取中彩票的幾率。但是這僅僅是幾率概行，小的可憐蠢挡。相似的，我們不能忽視具體事情執(zhí)行的時候凳忙，會發(fā)生意想不到的困難业踏。在送孩子去學(xué)校問題中，我們說的是車子的問題在于電池涧卵，GPS的顯式檢查來看看車子是不是可以工作勤家。或者需要電池柳恐，每一次程序都會考慮開車這個操作符伐脖。在現(xiàn)實世界中，很少會這么小心胎撤，我們坐進車子里晓殊，僅僅是在不能開的時候才會想到是電池的問題。
4.19 相互作用的目標問題
人們往往傾向于同時有多個目標伤提，而不是一次搞定一個再去想下一個。不僅僅是開車送孩子去學(xué)校认烁，還要同時注意不被別的車子撞上肿男，準時上班，搞定工作任務(wù)却嗡，見見朋友舶沛，找點樂子，保持呼吸窗价，等等等等如庭。也是要不得不自己去發(fā)現(xiàn)目標，而不是由其他人來告訴你一些預(yù)先定義好的目標撼港。有一些目標我們可以放在心里好幾年之久坪它，之后等時機成熟了在執(zhí)行完成。沒有一種合適所有目標的標記方法帝牡。但是卻有一中完成一些目標的可持續(xù)過程往毡，完成一部分，放棄或者推遲另外一部分靶溜。
除了達成既有的目標之外开瞭，人們還會注意防止需要避免的情況出現(xiàn)懒震。例如，假設(shè)我有一個朋友住醫(yī)院了嗤详，我想去看望看望他个扰，這就需要我人到醫(yī)院這么一個行為。一個可用的操作符就是走去醫(yī)院葱色，還有另一個操作符是故意把自己弄傷等救護車來送我去递宅，或許會更快。第二個操作符僅僅是達成了目標冬筒，但是去產(chǎn)生了人們不想要的副作用恐锣。這可能會記錄在方案花費的標記中，人們會避免對一些背景的目標有所損害舞痰，比如個人的健康土榴。
Herb Simon提出了術(shù)語滿意度來描述達成一個合理水平的合理目標的策略，也包含了同時推遲或者放棄的其他目標的影響响牛。GPS僅僅知道成功和失敗玷禽，因此僅僅是片面成功的最大化罷了。
4.20 GPS的最后
最后四個小節(jié)的內(nèi)容給出了對于GPS局限的領(lǐng)域的一些暗示呀打。事實上矢赁，GPS并不是一個完全通用的問題解決程序。在算法沒有綁定特定領(lǐng)域問題的層面上贬丛，他的確是個通用的程序撩银；我們也可以通過更改操作符來更改問題領(lǐng)域。但是GPS在無法解決很多有趣的問題的時候就是去了通用性豺憔。限制在一些小的技巧和游戲之中额获。
GPS最終失敗的原因很是微妙，其中一個就是說他出現(xiàn)在不被世人欣賞的1957年恭应，去愛現(xiàn)在成了計算機科學(xué)的核心〕現(xiàn)在一些被認為是計算機無法解決的問題，并不是說理論上正確的程序?qū)懖怀鰜碇玳唬且驗槌绦驁?zhí)行的時間實在是太長境肾。很多問題都被歸類為這類叫做NP困難問題。計算這些問題的時間隨著問題的規(guī)模的增長胆屿，時間呈指數(shù)級增長奥喻。這是因為問題本身的特性導(dǎo)致的，跟程序員本身的質(zhì)素沒有關(guān)系莺掠。指數(shù)級增長的意思是五個輸入會花費幾秒鐘求解的問題衫嵌，100個輸入就需要幾億年的時間來處理了。即使買更快的電腦也無濟于事彻秆。最終來說楔绞，如果你有一個需要幾億年才能解決的問題结闸，買了100臺比現(xiàn)在的電腦快1000倍的電腦來處理，也還是要等上幾百萬年的酒朵。對于理論計算機科學(xué)家來說桦锄，發(fā)現(xiàn)問題是NP困難問題就是答案本身了，但是對于AI來說蔫耽，就以為這被問了錯誤的問題结耀。很多NP困難問題在我們不堅持最佳解決方案，退而求其次的時候就會簡單很多了匙铡。
GPS的輸入基本上就是一個程序图甜，GPS的執(zhí)行也就是程序的執(zhí)行。如果GPS的輸入語言組足夠通用可以用來表達任何程序鳖眼。那他不能解決的問題要么沒有答案要么時間太長『谝悖現(xiàn)代的問題解決程序會辨認這些基礎(chǔ)的制限，或者限制問題的規(guī)模钦讳，或者找一個接近的解決方法或者部分的解決矿瘦。一些問題解決程序也會監(jiān)視執(zhí)行時間，當問題太過困難就會放棄執(zhí)行愿卒。
下面引用的話是出自Drew McDermott的文章《人工智能遇上天然的愚蠢》缚去，概括了當時對于GPS的感覺。記住它琼开，下次你不得不評價一個程序的時候會有用的易结。
GPS？現(xiàn)在柜候，GPS就是一個沒有意義的術(shù)語衬衬，僅僅是給出了一個解謎語的愚蠢程序。但是他既然叫做一般問題解決器改橘，但是僅僅是吊起了人們沒有意義的興奮和好奇。他應(yīng)該叫做LFGNS玉控，本地特定導(dǎo)引萬羅搜索器飞主。
盡管如此，GPS還是一個用來瀏覽編程技巧的有用程序高诺，特別是在AI編程這方面碌识。更重要的是，他會是一個來看純粹的思考的工具虱而。當然我們承認亞里士多德要比你我聰明的多筏餐，用隱喻來說明計算模型的概念，使人們更加欣賞目的手段分析法了牡拇，至少是在計算模型這個方面魁瞪。我們也必須堅持并不是所有的思考都是按照這個模型走的穆律。
AI的吸引力在于一種目的和手段的分離。一個成功的AI項目的結(jié)果可以使一個程序导俘，吧之前能做的事情做的更好更快峦耘。在這意義上來說，GPS是一個失敗之作旅薄，沒有很好地解決特定的問題辅髓。但是他對于問題解決過程的調(diào)查和格式化，從某種程度上來說是陳宮的少梁，讓讀者對整個過程有個更好的理解洛口。
