# 七、項目：機器人 > 原文：[Project: A Robot](http://eloquentjavascript.net/07_robot.html) > > 譯者：[飛龍](https://github.com/wizardforcel) > > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > > 自豪地采用[谷歌翻譯](https://translate.google.cn/) > [...] 置疑計算機能不能思考 [...] 就相當于置疑潛艇能不能游泳。 > > 艾茲格爾·迪科斯特拉，《計算機科學的威脅》  在“項目”章節中，我會在短時間內停止向你講述新理論，相反我們會一起完成一個項目。 學習編程理論是必要的，但閱讀和理解實際的計劃同樣重要。 我們在本章中的項目是構建一個自動機，一個在虛擬世界中執行任務的小程序。 我們的自動機將是一個接送包裹的郵件遞送機器人。 ## Meadowfield Meadowfield 村不是很大。 它由 11 個地點和 14 條道路組成。 它可以用`roads`數組來描述： ```js const roads = [ "Alice's House-Bob's House", "Alice's House-Cabin", "Alice's House-Post Office", "Bob's House-Town Hall", "Daria's House-Ernie's House", "Daria's House-Town Hall", "Ernie's House-Grete's House", "Grete's House-Farm", "Grete's House-Shop", "Marketplace-Farm", "Marketplace-Post Office", "Marketplace-Shop", "Marketplace-Town Hall", "Shop-Town Hall" ]; ```  村里的道路網絡形成了一個圖。 圖是節點（村里的地點）與他們之間的邊（道路）的集合。 這張圖將成為我們的機器人在其中移動的世界。 字符串數組并不易于處理。 我們感興趣的是，我們可以從特定地點到達的目的地。 讓我們將道路列表轉換為一個數據結構，對于每個地點，都會告訴我們從那里可以到達哪些地點。 ```js function buildGraph(edges) { let graph = Object.create(null); function addEdge(from, to) { if (graph[from] == null) { graph[from] = [to]; } else { graph[from].push(to); } } for (let [from, to] of edges.map(r => r.split("-"))) { addEdge(from, to); addEdge(to, from); } return graph; } const roadGraph = buildGraph(roads); ``` 給定邊的數組，`buildGraph`創建一個映射對象，該對象為每個節點存儲連通節點的數組。 它使用`split`方法，將形式為`"Start-End"`的道路字符串，轉換為兩元素數組，包含起點和終點作為單個字符串。 ## 任務 我們的機器人將在村莊周圍移動。 在各個地方都有包裹，每個都寄往其他地方。 機器人在收到包裹時拾取包裹，并在抵達目的地時將其送達。 自動機必須在每個點決定下一步要去哪里。 所有包裹遞送完成后，它就完成了任務。 為了能夠模擬這個過程，我們必須定義一個可以描述它的虛擬世界。 這個模型告訴我們機器人在哪里以及包裹在哪里。 當機器人決定移到某處時，我們需要更新模型以反映新情況。 如果你正在考慮面向對象編程，你的第一個沖動可能是開始為世界中的各種元素定義對象。 一個機器人，一個包裹，也許還有一個地點。 然后，它們可以持有描述其當前狀態的屬性，例如某個位置的一堆包裹，我們可以在更新世界時改變這些屬性。 這是錯的。 至少，通常是這樣。 一個東西聽起來像一個對象，并不意味著它應該是你的程序中的一個對象。 為應用程序中的每個概念反射式編寫類，往往會留下一系列互連對象，每個對象都有自己的內部的變化的狀態。 這樣的程序通常很難理解，因此很容易崩潰。 相反，讓我們將村莊的狀態壓縮成定義它的值的最小集合。 機器人的當前位置和未送達的包裹集合，其中每個都擁有當前位置和目標地址。這樣就夠了。 當我們到達新地點時，讓我們這樣做，在機器人移動時不會改變這種狀態，而是在移動之后為當前情況計算一個新狀態。 ```js class VillageState { constructor(place, parcels) { this.place = place; this.parcels = parcels; } move(destination) { if (!roadGraph[this.place].includes(destination)) { return this; } else { let parcels = this.parcels.map(p => { if (p.place != this.place) return p; return {place: destination, address: p.address}; }).filter(p => p.place != p.address); return new VillageState(destination, parcels); } } } ``` `move`方法是動作發生的地方。 它首先檢查是否有當前位置到目的地的道路，如果沒有，則返回舊狀態，因為這不是有效的移動。 然后它創建一個新的狀態，將目的地作為機器人的新地點。 但它也需要創建一套新的包裹 - 機器人攜帶的包裹（位于機器人當前位置）需要移動到新位置。 而要寄往新地點的包裹需要送達 - 也就是說，需要將它們從未送達的包裹中移除。 `'map'`的調用處理移動，并且`'filter'`的調用處理遞送。 包裹對象在移動時不會更改，但會被重新創建。 `move`方法為我們提供新的村莊狀態，但完全保留了原有的村莊狀態。 ```js let first = new VillageState( "Post Office", [{place: "Post Office", address: "Alice's House"}] ); let next = first.move("Alice's House"); console.log(next.place); // → Alice's House console.log(next.parcels); // → [] console.log(first.place); // → Post Office ``` `move`會使包裹被送達，并在下一個狀態中反映出來。 但最初的狀態仍然描述機器人在郵局并且包裹未送達的情況。 ## 持久性數據 不會改變的數據結構稱為不變的（immutable）或持久性的（persistent）。 他們的表現很像字符串和數字，因為他們就是他們自己，并保持這種狀態，而不是在不同的時間包含不同的東西。 在 JavaScript 中，幾乎所有的東西都可以改變，所以使用應該持久性的值需要一些限制。 有一個叫做`Object.freeze`的函數，它可以改變一個對象，使其忽略它的屬性的寫入。 如果你想要小心，你可以使用它來確保你的對象沒有改變。 `freeze`確實需要計算機做一些額外的工作，忽略更新可能會讓一些人迷惑，讓他們做錯事。 所以我通常更喜歡告訴人們，不應該弄亂給定的對象，并希望他們記住它。 ```js let object = Object.freeze({value: 5}); object.value = 10; console.log(object.value); // → 5 ``` 當語言顯然期待我這樣做時，為什么我不想改變對象？ 因為它幫助我理解我的程序。 這又是關于復雜性管理。 當我的系統中的對象是固定的，穩定的東西時，我可以孤立地考慮操作它們 - 從給定的起始狀態移動到愛麗絲的房子，始終會產生相同的新狀態。 當對象隨著時間而改變時，這就給這種推理增加了全新的復雜性。 對于小型系統，例如我們在本章中構建的東西，我們可以處理那些額外的復雜性。 但是我們可以建立什么樣的系統，最重要的限制是我們能夠理解多少。 任何讓你的代碼更容易理解的東西，都可以構建一個更加龐大的系統。 不幸的是，盡管理解構建在持久性數據結構上的系統比較容易，但設計一個，特別是當你的編程語言沒有幫助時，可能會更難一些。 我們將在本書中尋找使用持久性數據結構的時機，但我們也將使用可變數據結構。 ## 模擬 遞送機器人觀察世界并決定它想要移動的方向。 因此，我們可以說機器人是一個函數，接受`VillageState`對象并返回附近地點的名稱。 因為我們希望機器人能夠記住東西，以便他們可以制定和執行計劃，我們也會傳遞他們的記憶，并讓他們返回一個新的記憶。 因此，機器人返回的東西是一個對象，包含它想要移動的方向，以及下次調用時將返回給它的記憶值。 ```js function runRobot(state, robot, memory) { for (let turn = 0;; turn++) { if (state.parcels.length == 0) { console.log(`Done in ${turn} turns`); break; } let action = robot(state, memory); state = state.move(action.direction); memory = action.memory; console.log(`Moved to ${action.direction}`); } } ``` 考慮一下機器人必須做些什么來“解決”一個給定的狀態。 它必須通過訪問擁有包裹的每個位置來拾取所有包裹，并通過訪問包裹寄往的每個位置來遞送，但只能在拾取包裹之后。 什么是可能有效的最愚蠢的策略？ 機器人可以在每回合中，向隨機方向行走。 這意味著很有可能它最終會碰到所有的包裹，然后也會在某個時候到達包裹應該送達的地方。 以下是可能的樣子： ```js function randomPick(array) { let choice = Math.floor(Math.random() * array.length); return array[choice]; } function randomRobot(state) { return {direction: randomPick(roadGraph[state.place])}; } ``` 請記住，`Math.random()`返回 0 和 1 之間的數字，但總是小于 1。 將這樣一個數乘以數組長度，然后將`Math.floor`應用于它，向我們提供數組的隨機索引。 由于這個機器人不需要記住任何東西，所以它忽略了它的第二個參數（記住，可以使用額外的參數調用 JavaScript 函數而不會產生不良影響）并省略返回對象中的`memory`屬性。 為了使這個復雜的機器人工作，我們首先需要一種方法來創建一些包裹的新狀態。 靜態方法（通過直接向構造函數添加一個屬性來編寫）是放置該功能的好地方。 ```js VillageState.random = function(parcelCount = 5) { let parcels = []; for (let i = 0; i < parcelCount; i++) { let address = randomPick(Object.keys(roadGraph)); let place; do { place = randomPick(Object.keys(roadGraph)); } while (place == address); parcels.push({place, address}); } return new VillageState("Post Office", parcels); }; ``` 我們不想要發往寄出地的任何包裹。 出于這個原因，當`do`循環獲取與地址相同的地方時，它會繼續選擇新的地方。 讓我們建立一個虛擬世界。 ```js runRobot(VillageState.random(), randomRobot); // → Moved to Marketplace // → Moved to Town Hall // → … // → Done in 63 turns ``` 機器人需要花費很多時間來交付包裹，因為它沒有很好規劃。 我們很快就會解決。 為了更好地理解模擬，你可以使用本章編程環境中提供的`runRobotAnimation`函數。 這將運行模擬，但不是輸出文本，而是向你展示機器人在村莊地圖上移動。 ```js runRobotAnimation(VillageState.random(), randomRobot); ``` `runRobotAnimation`的實現方式現在仍然是一個謎，但是在閱讀本書的后面的章節，討論 Web 瀏覽器中的 JavaScript 集成之后，你將能夠猜到它的工作原理。 ## 郵車的路線 我們應該能夠比隨機機器人做得更好。 一個簡單的改進就是從現實世界的郵件傳遞方式中獲得提示。 如果我們發現一條經過村莊所有地點的路線，機器人可以通行該路線兩次，此時它保證能夠完成。 這是一條這樣的路線（從郵局開始）。 ```js const mailRoute = [ "Alice's House", "Cabin", "Alice's House", "Bob's House", "Town Hall", "Daria's House", "Ernie's House", "Grete's House", "Shop", "Grete's House", "Farm", "Marketplace", "Post Office" ]; ``` 為了實現路線跟蹤機器人，我們需要利用機器人的記憶。 機器人將其路線的其余部分保存在其記憶中，并且每回合丟棄第一個元素。 ```js function routeRobot(state, memory) { if (memory.length == 0) { memory = mailRoute; } return {direction: memory[0], memory: memory.slice(1)}; } ``` 這個機器人已經快了很多。 它最多需要 26 個回合（13 步的路線的兩倍），但通常要少一些。 ```js runRobotAnimation(VillageState.random(), routeRobot, []); ``` ## 尋路 不過，我不會盲目遵循固定的智能尋路行為。 如果機器人為需要完成的實際工作調整行為，它可以更高效地工作。 為此，它必須能夠有針對性地朝著給定的包裹移動，或者朝著包裹必須送達的地點。 盡管如此，即使目標距離我們不止一步，也需要某種尋路函數。 在圖上尋找路線的問題是一個典型的搜索問題。 我們可以判斷一個給定的解決方案（路線）是否是一個有效的解決方案，但我們不能像 2 + 2 這樣，直接計算解決方案。 相反，我們必須不斷創建潛在的解決方案，直到找到有效的解決方案。 圖上的可能路線是無限的。 但是當搜索`A`到`B`的路線時，我們只關注從`A`起始的路線。 我們也不關心兩次訪問同一地點的路線 - 這絕對不是最有效的路線。 這樣可以減少查找者必須考慮的路線數量。 事實上，我們最感興趣的是最短路線。 所以我們要確保，查看較長路線之前，我們要查看較短的路線。 一個好的方法是，從起點使路線“生長”，探索尚未到達的每個可到達的地方，直到路線到達目標。 這樣，我們只探索潛在的有趣路線，并找到到目標的最短路線（或最短路線之一，如果有多條路線）。 這是一個實現它的函數： ```js function findRoute(graph, from, to) { let work = [{at: from, route: []}]; for (let i = 0; i < work.length; i++) { let {at, route} = work[i]; for (let place of graph[at]) { if (place == to) return route.concat(place); if (!work.some(w => w.at == place)) { work.push({at: place, route: route.concat(place)}); } } } } ``` 探索必須按照正確的順序完成 - 首先到達的地方必須首先探索。 我們不能到達一個地方就立即探索，因為那樣意味著，從那里到達的地方也會被立即探索，以此類推，盡管可能還有其他更短的路徑尚未被探索。 因此，該函數保留一個工作列表。 這是一系列應該探索的地方，以及讓我們到那里的路線。 它最開始只有起始位置和空路線。 然后，通過獲取列表中的下一個項目并進行探索，來執行搜索，這意味著，會查看從該地點起始的所有道路。 如果其中之一是目標，則可以返回完成的路線。 否則，如果我們以前沒有看過這個地方，就會在列表中添加一個新項目。 如果我們之前看過它，因為我們首先查看了短路線，我們發現，到達那個地方的路線較長，或者與現有路線一樣長，我們不需要探索它。 你可以在視覺上將它想象成一個已知路線的網，從起始位置爬出來，在各個方向上均勻生長（但不會纏繞回去）。 只要第一條線到達目標位置，其它線就會退回起點，為我們提供路線。 我們的代碼無法處理工作列表中沒有更多工作項的情況，因為我們知道我們的圖是連通的，這意味著可以從其他所有位置訪問每個位置。 我們始終能夠找到兩點之間的路線，并且搜索不會失敗。 ```js function goalOrientedRobot({place, parcels}, route) { if (route.length == 0) { let parcel = parcels[0]; if (parcel.place != place) { route = findRoute(roadGraph, place, parcel.place); } else { route = findRoute(roadGraph, place, parcel.address); } } return {direction: route[0], memory: route.slice(1)}; } ``` 這個機器人使用它的記憶值作為移動方向的列表，就像尋路機器人一樣。 無論什么時候這個列表是空的，它都必須弄清下一步該做什么。 它會取出集合中第一個未送達的包裹，如果該包裹還沒有被拾取，則會繪制一條朝向它的路線。 如果包裹已經被拾取，它仍然需要送達，所以機器人會創建一個朝向遞送地址的路線。 讓我們看看如何實現。 ```js runRobotAnimation(VillageState.random(), goalOrientedRobot, []); ``` 這個機器人通常在大約 16 個回合中，完成了送達 5 個包裹的任務。 略好于`routeRobot`，但仍然絕對不是最優的。 ## 練習 ### 測量機器人 很難通過讓機器人解決一些場景來客觀比較他們。 也許一個機器人碰巧得到了更簡單的任務，或者它擅長的那種任務，而另一個沒有。 編寫一個`compareRobots`，接受兩個機器人（和它們的起始記憶）。 它應該生成 100 個任務，并讓每個機器人解決每個這些任務。 完成后，它應輸出每個機器人每個任務的平均步數。 為了公平起見，請確保你將每個任務分配給兩個機器人，而不是為每個機器人生成不同的任務。 ```js function compareRobots(robot1, memory1, robot2, memory2) { // Your code here } compareRobots(routeRobot, [], goalOrientedRobot, []); ``` ### 機器人的效率 你能寫一個機器人，比`goalOrientedRobot`更快完成遞送任務嗎？ 如果你觀察機器人的行為，它會做什么明顯愚蠢的事情？如何改進它們？ 如果你解決了上一個練習，你可能打算使用`compareRobots`函數來驗證你是否改進了機器人。 ```js // Your code here runRobotAnimation(VillageState.random(), yourRobot, memory); ``` ### 持久性分組 標準 JavaScript 環境中提供的大多數數據結構不太適合持久使用。 數組有`slice`和`concat`方法，可以讓我們輕松創建新的數組而不會損壞舊數組。 但是`Set`沒有添加或刪除項目并創建新集合的方法。 編寫一個新的類`PGroup`，類似于第六章中的`Group`類，它存儲一組值。 像`Group`一樣，它具有`add`，`delete`和`has`方法。 然而，它的`add`方法應該返回一個新的`PGroup`實例，并添加給定的成員，并保持舊的不變。 與之類似，`delete`創建一個沒有給定成員的新實例。 該類應該適用于任何類型的值，而不僅僅是字符串。 當與大量值一起使用時，它不一定非常高效。 構造函數不應該是類接口的一部分（盡管你絕對會打算在內部使用它）。 相反，有一個空的實例`PGroup.empty`，可用作起始值。 為什么只需要一個`PGroup.empty`值，而不是每次都創建一個新的空分組？ ```js class PGroup { // Your code here } let a = PGroup.empty.add("a"); let ab = a.add("b"); let b = ab.delete("a"); console.log(b.has("b")); // → true console.log(a.has("b")); // → false console.log(b.has("a")); // → false ```