（英文：theory.stanford.edu
譯文：伯樂在線 - 土豆粉ss
鏈接：http://blog.jobbole.com/90681/
本系列：
關于尋路算法的一些思考（1）：A* 算法介紹
關于尋路算法的一些思考（2）：Heuristics 函數
關于尋路算法的一些思考（3）：A* 算法的實現
關于尋路算法的一些思考（4）：A* 算法的變體
關于尋路算法的一些思考（5）：處理移動中的障礙物
關于尋路算法的一些思考（6）：預先計算好的路徑的所用空間
關于尋路算法的一些思考（7）：地圖表示
關于尋路算法的一些思考（8）：長期和短期目標
關于尋路算法的一些思考（9）：尋路者的移動成本
關于尋路算法的一些思考（10）：最短路徑的用戶體驗
關于尋路算法的一些思考（11）：尋路算法的其他應用
AI技術 尋路問題常常會和人工智能（AI） 聯系在一起，原因是 A*算法和許多其他尋路算法是由 AI 研究者開發出來的。一些生物啟發式的 AI 技術目前十分流行，我也收到一些為何不使用這類技術的咨詢。神經網絡是依據實例的大腦學習建模——給定一個正解的集合，它會學習出一個一般的解決問題模式。強化學習是依據經驗的大腦學習建模——給定一些行為的集合和最終獎懲結果，它會學習出哪種行為是正確或錯誤的。遺傳算法根據自然選擇的進化規律建模——給定一些agent 集合，優勝劣汰。通常情況下，遺傳算法不允許 agent 在他們的生存時間內進行學習。強化學習則不但允許 agent 在生存時間內學習，還可以和其他 agent 分享知識。（譯注：agent：智能體，正文保留未翻）
神經網絡
神經網絡是這樣構建的：它受到訓練，來對輸入進行模式識別。他們是一種用來處理函數近似的方法:給定 y1 = f(x1),y2 = f(x2), …, yn = f(xn)，構建一個函數 f’使得 f’逼近 f。近似函數 f’一般都是光滑的：對于接近 x 點的 x’，我們希望 f’(x)也能接近f’(x’)。
函數近似方法可以滿足以下兩個目的：
規模：近似函數的表達可以明顯小于真實的函數規模。
泛化：未知函數值的輸入數據可以使用近似函數
神經網絡典型做法是使用一組輸入值向量，產生一組輸出值向量。在算法內部，訓練“神經元”(neurons)的權重。神經網絡使用監督學習，即輸入和輸出都是已知的，學習的目標是建立一個可以近似輸入輸出映射的函數表達。
在尋路問題中，函數 f(start,goal)=path。我們并不知道輸出路徑是什么。我們可以使用一些方法，可能是 A*算法，來計算它們。但是如果我們能根據(start, goal)計算路徑，那么我們就已經知道了函數 f，那么為什么還要自找麻煩的找它的近似函數呢？因為我們已經完全知道了函數 f，再歸納 f 就沒有用了。用函數近似的唯一潛在的好處可能會降低 f 的表達規模。但f 表達的是個相當簡潔幾乎不占用空間的算法，所以我認為神經網絡在這里也沒有什么用。另外，神經網絡輸出規模是固定的，而尋路問題規模是可變的。
但另一方面，函數近似可能對構建尋路的一些組成部分有用。比如移動的成本函數是未知的。例如，沒有實際移動操作和戰役的情況下，穿越怪獸聚集森林的成本，我們可能并不知道。使用函數近似的方法的話，每次穿越森林時，移動成本函數f(number of orcs, size of forest)可以測量出來并裝入神經網絡模型中（注：這里移動成本f的自變量是怪獸數量和森林規模）。對于未來的尋路部分，根據算出的未知移動成本，我們可以找到更好的路線。
另一個可以從歸功于近似計算的函數是啟發式函數。A*算法中的啟發式函數可以計算到達目的地的最小成本，如果一個單元沿著路徑 P=p1,p2,…,pn移動，當每穿過一段路徑的時候，我們可以更新 n到近似函數 h 中，其中g(pi,pn)=（從i到 n 的實際移動成本）。當啟發函數優化了，A*算法也會運行的更快。
神經網絡盡管對于尋路算法本體不太實用，但對 A*算法使用的函數可以起到作用。移動函數和啟發式函數都可以測算，因此能給函數近似反饋。
遺傳算法
根據適應度函數（fitness function），遺傳算法允許開發參數空間來求得效果良好的解。他們是一種用來處理函數優化的方法：給定一個函數g(x)（x 是一組典型的參數值向量），求得能最大化（或最小化）g(x)的 x 值。這是一種非監督學習——問題的正確答案預先并不知道。
對于尋路問題，給定一個起始位置和一個目標位置，x 是這兩點間的路徑，g(x)是穿越這路徑的成本。簡單的優化方法，比如爬山算法會以增加g(x)為代價的方法改變 x。不幸的是，在一些問題中，會遇到“局部最大值”，x 值周圍沒有點 具有更大的對應g值，但是某個離x 值比較遠的點表現更好。遺傳算法改善了爬山算法，它保留了 x 的多樣性，使用比如變異和交換的進化-啟發式方法更新 x。
爬山算法和遺傳算法可以用來學習出 x 的最優值。然而對于尋路問題，我們已經有了 A*算法找到最優的 x ，因此函數優化的方法就不需要了。
遺傳編程是遺傳算法的更深層次，它把程序當做參數。例如，你可以輸入的是尋路算法而不是尋路路徑，你的適應值函數會根據表現測算每個算法。對于尋路問題來說，我們已經有個很好的算法，我們無需在進化出一個新的算法。
也許在和神經網絡結合的情況下，遺傳算法可以應用于尋路問題的某個部分。但是，在這篇文章中我還不知道有何用處。相反，如果問題解是已知的，估計會有一個更有前途的方法作為許多可行工具之一，在尋路問題中優化 agent。
強化學習
和遺傳算法一樣，強化學習是一種非監督學習。然而，和遺傳算法不同的是，agent 可以在他們的生存時間內學習；沒必要等著觀察他們的存活情況。并且，多 agents 同時參與到不同部分中分享各自學習成果是可能的。強化學習和 A*的核心部分有著一些相似的地方。
在 A*中，到達結束目標后會沿著經過的路徑追溯回去，標記到目前為止所有路徑的選擇；其他選擇就被去掉了。在強化學習中，可以測算每個狀態時的情況，并且當前的獎（懲）都可以追溯回導致這個狀態之前的所有選擇。使用一個值函數表達這個追溯的過程，這有點像 A*中的啟發式函數，但隨著 agent 嘗試新路徑并對這過程進行學習的更新，這一方面兩者是不同的。
相比于更簡單的算法來說，強化學習和遺傳算法的一個關鍵的優勢是：在探求新解和利用目前學到的信息兩者間是可以做出選擇的。遺傳算法，通過變異尋找（新解）；強化學習，通過明確給出選擇新行為的概率尋找（新解）。
即使和遺傳算法結合，我認為強化學習也不會在尋路問題本身上使用。但是相對來說，它卻可以作為一個向導，指導agent 在游戲世界中如何表現。
注： 函數近似方法可以變形為函數優化問題。為了找到最逼近 f(x)的f'(x),令 g(f’)=∑(f’(x)-f(x))^2（即在所有輸入 x 上(f’(x)-f(x))^2的和）。
更多精彩資訊請關注查字典資訊網，我們將持續為您更新最新資訊!
