摘要：來(lái)源編程精解中文第三版翻譯項(xiàng)目原文譯者飛龍協(xié)議自豪地采用谷歌翻譯置疑計(jì)算機(jī)能不能思考就相當(dāng)于置疑潛艇能不能游泳。這張圖將成為我們的機(jī)器人在其中移動(dòng)的世界。機(jī)器人在收到包裹時(shí)拾取包裹，并在抵達(dá)目的地時(shí)將其送達(dá)。這個(gè)機(jī)器人已經(jīng)快了很多。

來(lái)源：ApacheCN『JavaScript 編程精解 中文第三版』翻譯項(xiàng)目
原文：Project: A Robot
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
[...] 置疑計(jì)算機(jī)能不能思考 [...] 就相當(dāng)于置疑潛艇能不能游泳。
艾茲格爾·迪科斯特拉，《計(jì)算機(jī)科學(xué)的威脅》

在“項(xiàng)目”章節(jié)中，我會(huì)在短時(shí)間內(nèi)停止向你講述新理論，相反我們會(huì)一起完成一個(gè)項(xiàng)目。 學(xué)習(xí)編程理論是必要的，但閱讀和理解實(shí)際的計(jì)劃同樣重要。

我們?cè)诒菊轮械捻?xiàng)目是構(gòu)建一個(gè)自動(dòng)機(jī)，一個(gè)在虛擬世界中執(zhí)行任務(wù)的小程序。 我們的自動(dòng)機(jī)將是一個(gè)接送包裹的郵件遞送機(jī)器人。

Meadowfield 村不是很大。 它由 11 個(gè)地點(diǎn)和 14 條道路組成。 它可以用roads數(shù)組來(lái)描述：

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"
];

村里的道路網(wǎng)絡(luò)形成了一個(gè)圖。 圖是節(jié)點(diǎn)（村里的地點(diǎn)）與他們之間的邊（道路）的集合。 這張圖將成為我們的機(jī)器人在其中移動(dòng)的世界。

字符串?dāng)?shù)組并不易于處理。 我們感興趣的是，我們可以從特定地點(diǎn)到達(dá)的目的地。 讓我們將道路列表轉(zhuǎn)換為一個(gè)數(shù)據(jù)結(jié)構(gòu)，對(duì)于每個(gè)地點(diǎn)，都會(huì)告訴我們從那里可以到達(dá)哪些地點(diǎn)。

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);

給定邊的數(shù)組，buildGraph創(chuàng)建一個(gè)映射對(duì)象，該對(duì)象為每個(gè)節(jié)點(diǎn)存儲(chǔ)連通節(jié)點(diǎn)的數(shù)組。

它使用split方法，將形式為"Start-End"的道路字符串，轉(zhuǎn)換為兩元素?cái)?shù)組，包含起點(diǎn)和終點(diǎn)作為單個(gè)字符串。

我們的機(jī)器人將在村莊周圍移動(dòng)。 在各個(gè)地方都有包裹，每個(gè)都寄往其他地方。 機(jī)器人在收到包裹時(shí)拾取包裹，并在抵達(dá)目的地時(shí)將其送達(dá)。

自動(dòng)機(jī)必須在每個(gè)點(diǎn)決定下一步要去哪里。 所有包裹遞送完成后，它就完成了任務(wù)。

為了能夠模擬這個(gè)過程，我們必須定義一個(gè)可以描述它的虛擬世界。 這個(gè)模型告訴我們機(jī)器人在哪里以及包裹在哪里。 當(dāng)機(jī)器人決定移到某處時(shí)，我們需要更新模型以反映新情況。

如果你正在考慮面向?qū)ο缶幊?，你的第一個(gè)沖動(dòng)可能是開始為世界中的各種元素定義對(duì)象。 一個(gè)機(jī)器人，一個(gè)包裹，也許還有一個(gè)地點(diǎn)。 然后，它們可以持有描述其當(dāng)前狀態(tài)的屬性，例如某個(gè)位置的一堆包裹，我們可以在更新世界時(shí)改變這些屬性。

這是錯(cuò)的。

至少，通常是這樣。 一個(gè)東西聽起來(lái)像一個(gè)對(duì)象，并不意味著它應(yīng)該是你的程序中的一個(gè)對(duì)象。 為應(yīng)用程序中的每個(gè)概念反射式編寫類，往往會(huì)留下一系列互連對(duì)象，每個(gè)對(duì)象都有自己的內(nèi)部的變化的狀態(tài)。 這樣的程序通常很難理解，因此很容易崩潰。

相反，讓我們將村莊的狀態(tài)壓縮成定義它的值的最小集合。 機(jī)器人的當(dāng)前位置和未送達(dá)的包裹集合，其中每個(gè)都擁有當(dāng)前位置和目標(biāo)地址。這樣就夠了。

當(dāng)我們到達(dá)新地點(diǎn)時(shí)，讓我們這樣做，在機(jī)器人移動(dòng)時(shí)不會(huì)改變這種狀態(tài)，而是在移動(dòng)之后為當(dāng)前情況計(jì)算一個(gè)新狀態(tài)。

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方法是動(dòng)作發(fā)生的地方。 它首先檢查是否有當(dāng)前位置到目的地的道路，如果沒有，則返回舊狀態(tài)，因?yàn)檫@不是有效的移動(dòng)。

然后它創(chuàng)建一個(gè)新的狀態(tài)，將目的地作為機(jī)器人的新地點(diǎn)。 但它也需要?jiǎng)?chuàng)建一套新的包裹 - 機(jī)器人攜帶的包裹（位于機(jī)器人當(dāng)前位置）需要移動(dòng)到新位置。 而要寄往新地點(diǎn)的包裹需要送達(dá) - 也就是說(shuō)，需要將它們從未送達(dá)的包裹中移除。 "map"的調(diào)用處理移動(dòng)，并且"filter"的調(diào)用處理遞送。

包裹對(duì)象在移動(dòng)時(shí)不會(huì)更改，但會(huì)被重新創(chuàng)建。 move方法為我們提供新的村莊狀態(tài)，但完全保留了原有的村莊狀態(tài)。

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會(huì)使包裹被送達(dá)，并在下一個(gè)狀態(tài)中反映出來(lái)。 但最初的狀態(tài)仍然描述機(jī)器人在郵局并且包裹未送達(dá)的情況。

不會(huì)改變的數(shù)據(jù)結(jié)構(gòu)稱為不變的（immutable）或持久性的（persistent）。 他們的表現(xiàn)很像字符串和數(shù)字，因?yàn)樗麄兙褪撬麄冏约?，并保持這種狀態(tài)，而不是在不同的時(shí)間包含不同的東西。

在 JavaScript 中，幾乎所有的東西都可以改變，所以使用應(yīng)該持久性的值需要一些限制。 有一個(gè)叫做Object.freeze的函數(shù)，它可以改變一個(gè)對(duì)象，使其忽略它的屬性的寫入。 如果你想要小心，你可以使用它來(lái)確保你的對(duì)象沒有改變。 freeze確實(shí)需要計(jì)算機(jī)做一些額外的工作，忽略更新可能會(huì)讓一些人迷惑，讓他們做錯(cuò)事。 所以我通常更喜歡告訴人們，不應(yīng)該弄亂給定的對(duì)象，并希望他們記住它。

let object = Object.freeze({value: 5});
object.value = 10;
console.log(object.value);
// → 5

當(dāng)語(yǔ)言顯然期待我這樣做時(shí)，為什么我不想改變對(duì)象？

因?yàn)樗鼛椭依斫馕业某绦颉?這又是關(guān)于復(fù)雜性管理。 當(dāng)我的系統(tǒng)中的對(duì)象是固定的，穩(wěn)定的東西時(shí)，我可以孤立地考慮操作它們 - 從給定的起始狀態(tài)移動(dòng)到愛麗絲的房子，始終會(huì)產(chǎn)生相同的新狀態(tài)。 當(dāng)對(duì)象隨著時(shí)間而改變時(shí)，這就給這種推理增加了全新的復(fù)雜性。

對(duì)于小型系統(tǒng)，例如我們?cè)诒菊轮袠?gòu)建的東西，我們可以處理那些額外的復(fù)雜性。 但是我們可以建立什么樣的系統(tǒng)，最重要的限制是我們能夠理解多少。 任何讓你的代碼更容易理解的東西，都可以構(gòu)建一個(gè)更加龐大的系統(tǒng)。

不幸的是，盡管理解構(gòu)建在持久性數(shù)據(jù)結(jié)構(gòu)上的系統(tǒng)比較容易，但設(shè)計(jì)一個(gè)，特別是當(dāng)你的編程語(yǔ)言沒有幫助時(shí)，可能會(huì)更難一些。 我們將在本書中尋找使用持久性數(shù)據(jù)結(jié)構(gòu)的時(shí)機(jī)，但我們也將使用可變數(shù)據(jù)結(jié)構(gòu)。

遞送機(jī)器人觀察世界并決定它想要移動(dòng)的方向。 因此，我們可以說(shuō)機(jī)器人是一個(gè)函數(shù)，接受VillageState對(duì)象并返回附近地點(diǎn)的名稱。

因?yàn)槲覀兿Ｍ麢C(jī)器人能夠記住東西，以便他們可以制定和執(zhí)行計(jì)劃，我們也會(huì)傳遞他們的記憶，并讓他們返回一個(gè)新的記憶。 因此，機(jī)器人返回的東西是一個(gè)對(duì)象，包含它想要移動(dòng)的方向，以及下次調(diào)用時(shí)將返回給它的記憶值。

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}`);
  }
}

考慮一下機(jī)器人必須做些什么來(lái)“解決”一個(gè)給定的狀態(tài)。 它必須通過訪問擁有包裹的每個(gè)位置來(lái)拾取所有包裹，并通過訪問包裹寄往的每個(gè)位置來(lái)遞送，但只能在拾取包裹之后。

什么是可能有效的最愚蠢的策略？ 機(jī)器人可以在每回合中，向隨機(jī)方向行走。 這意味著很有可能它最終會(huì)碰到所有的包裹，然后也會(huì)在某個(gè)時(shí)候到達(dá)包裹應(yīng)該送達(dá)的地方。

以下是可能的樣子：

function randomPick(array) {
  let choice = Math.floor(Math.random() * array.length);
  return array[choice];
}

function randomRobot(state) {
  return {direction: randomPick(roadGraph[state.place])};
}

請(qǐng)記住，Math.random()返回 0 和 1 之間的數(shù)字，但總是小于 1。 將這樣一個(gè)數(shù)乘以數(shù)組長(zhǎng)度，然后將Math.floor應(yīng)用于它，向我們提供數(shù)組的隨機(jī)索引。

由于這個(gè)機(jī)器人不需要記住任何東西，所以它忽略了它的第二個(gè)參數(shù)（記住，可以使用額外的參數(shù)調(diào)用 JavaScript 函數(shù)而不會(huì)產(chǎn)生不良影響）并省略返回對(duì)象中的memory屬性。

為了使這個(gè)復(fù)雜的機(jī)器人工作，我們首先需要一種方法來(lái)創(chuàng)建一些包裹的新狀態(tài)。 靜態(tài)方法（通過直接向構(gòu)造函數(shù)添加一個(gè)屬性來(lái)編寫）是放置該功能的好地方。

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);
};

我們不想要發(fā)往寄出地的任何包裹。 出于這個(gè)原因，當(dāng)do循環(huán)獲取與地址相同的地方時(shí)，它會(huì)繼續(xù)選擇新的地方。

讓我們建立一個(gè)虛擬世界。

runRobot(VillageState.random(), randomRobot);
// → Moved to Marketplace
// → Moved to Town Hall
// → …
// → Done in 63 turns

機(jī)器人需要花費(fèi)很多時(shí)間來(lái)交付包裹，因?yàn)樗鼪]有很好規(guī)劃。 我們很快就會(huì)解決。

為了更好地理解模擬，你可以使用本章編程環(huán)境中提供的runRobotAnimation函數(shù)。 這將運(yùn)行模擬，但不是輸出文本，而是向你展示機(jī)器人在村莊地圖上移動(dòng)。

runRobotAnimation(VillageState.random(), randomRobot);

runRobotAnimation的實(shí)現(xiàn)方式現(xiàn)在仍然是一個(gè)謎，但是在閱讀本書的后面的章節(jié)，討論 Web 瀏覽器中的 JavaScript 集成之后，你將能夠猜到它的工作原理。

我們應(yīng)該能夠比隨機(jī)機(jī)器人做得更好。 一個(gè)簡(jiǎn)單的改進(jìn)就是從現(xiàn)實(shí)世界的郵件傳遞方式中獲得提示。 如果我們發(fā)現(xiàn)一條經(jīng)過村莊所有地點(diǎn)的路線，機(jī)器人可以通行該路線兩次，此時(shí)它保證能夠完成。 這是一條這樣的路線（從郵局開始）。

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"
];

為了實(shí)現(xiàn)路線跟蹤機(jī)器人，我們需要利用機(jī)器人的記憶。 機(jī)器人將其路線的其余部分保存在其記憶中，并且每回合丟棄第一個(gè)元素。

function routeRobot(state, memory) {
  if (memory.length == 0) {
    memory = mailRoute;
  }
  return {direction: memory[0], memory: memory.slice(1)};
}

這個(gè)機(jī)器人已經(jīng)快了很多。 它最多需要 26 個(gè)回合（13 步的路線的兩倍），但通常要少一些。

runRobotAnimation(VillageState.random(), routeRobot, []);

不過，我不會(huì)盲目遵循固定的智能尋路行為。 如果機(jī)器人為需要完成的實(shí)際工作調(diào)整行為，它可以更高效地工作。

為此，它必須能夠有針對(duì)性地朝著給定的包裹移動(dòng)，或者朝著包裹必須送達(dá)的地點(diǎn)。 盡管如此，即使目標(biāo)距離我們不止一步，也需要某種尋路函數(shù)。

在圖上尋找路線的問題是一個(gè)典型的搜索問題。 我們可以判斷一個(gè)給定的解決方案（路線）是否是一個(gè)有效的解決方案，但我們不能像 2 + 2 這樣，直接計(jì)算解決方案。 相反，我們必須不斷創(chuàng)建潛在的解決方案，直到找到有效的解決方案。

圖上的可能路線是無(wú)限的。 但是當(dāng)搜索A到B的路線時(shí)，我們只關(guān)注從A起始的路線。 我們也不關(guān)心兩次訪問同一地點(diǎn)的路線 - 這絕對(duì)不是最有效的路線。 這樣可以減少查找者必須考慮的路線數(shù)量。

事實(shí)上，我們最感興趣的是最短路線。 所以我們要確保，查看較長(zhǎng)路線之前，我們要查看較短的路線。 一個(gè)好的方法是，從起點(diǎn)使路線“生長(zhǎng)”，探索尚未到達(dá)的每個(gè)可到達(dá)的地方，直到路線到達(dá)目標(biāo)。 這樣，我們只探索潛在的有趣路線，并找到到目標(biāo)的最短路線（或最短路線之一，如果有多條路線）。

這是一個(gè)實(shí)現(xiàn)它的函數(shù)：

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)});
      }
    }
  }
}

探索必須按照正確的順序完成 - 首先到達(dá)的地方必須首先探索。 我們不能到達(dá)一個(gè)地方就立即探索，因?yàn)槟菢右馕吨瑥哪抢锏竭_(dá)的地方也會(huì)被立即探索，以此類推，盡管可能還有其他更短的路徑尚未被探索。

因此，該函數(shù)保留一個(gè)工作列表。 這是一系列應(yīng)該探索的地方，以及讓我們到那里的路線。 它最開始只有起始位置和空路線。

然后，通過獲取列表中的下一個(gè)項(xiàng)目并進(jìn)行探索，來(lái)執(zhí)行搜索，這意味著，會(huì)查看從該地點(diǎn)起始的所有道路。 如果其中之一是目標(biāo)，則可以返回完成的路線。 否則，如果我們以前沒有看過這個(gè)地方，就會(huì)在列表中添加一個(gè)新項(xiàng)目。 如果我們之前看過它，因?yàn)槲覀兪紫炔榭戳硕搪肪€，我們發(fā)現(xiàn)，到達(dá)那個(gè)地方的路線較長(zhǎng)，或者與現(xiàn)有路線一樣長(zhǎng)，我們不需要探索它。

你可以在視覺上將它想象成一個(gè)已知路線的網(wǎng)，從起始位置爬出來(lái)，在各個(gè)方向上均勻生長(zhǎng)（但不會(huì)纏繞回去）。 只要第一條線到達(dá)目標(biāo)位置，其它線就會(huì)退回起點(diǎn)，為我們提供路線。

我們的代碼無(wú)法處理工作列表中沒有更多工作項(xiàng)的情況，因?yàn)槲覀冎牢覀兊膱D是連通的，這意味著可以從其他所有位置訪問每個(gè)位置。 我們始終能夠找到兩點(diǎn)之間的路線，并且搜索不會(huì)失敗。

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)};
}

這個(gè)機(jī)器人使用它的記憶值作為移動(dòng)方向的列表，就像尋路機(jī)器人一樣。 無(wú)論什么時(shí)候這個(gè)列表是空的，它都必須弄清下一步該做什么。 它會(huì)取出集合中第一個(gè)未送達(dá)的包裹，如果該包裹還沒有被拾取，則會(huì)繪制一條朝向它的路線。 如果包裹已經(jīng)被拾取，它仍然需要送達(dá)，所以機(jī)器人會(huì)創(chuàng)建一個(gè)朝向遞送地址的路線。

讓我們看看如何實(shí)現(xiàn)。

runRobotAnimation(VillageState.random(),
                  goalOrientedRobot, []);

這個(gè)機(jī)器人通常在大約 16 個(gè)回合中，完成了送達(dá) 5 個(gè)包裹的任務(wù)。 略好于routeRobot，但仍然絕對(duì)不是最優(yōu)的。

很難通過讓機(jī)器人解決一些場(chǎng)景來(lái)客觀比較他們。 也許一個(gè)機(jī)器人碰巧得到了更簡(jiǎn)單的任務(wù)，或者它擅長(zhǎng)的那種任務(wù)，而另一個(gè)沒有。

編寫一個(gè)compareRobots，接受兩個(gè)機(jī)器人（和它們的起始記憶）。 它應(yīng)該生成 100 個(gè)任務(wù)，并讓每個(gè)機(jī)器人解決每個(gè)這些任務(wù)。 完成后，它應(yīng)輸出每個(gè)機(jī)器人每個(gè)任務(wù)的平均步數(shù)。

為了公平起見，請(qǐng)確保你將每個(gè)任務(wù)分配給兩個(gè)機(jī)器人，而不是為每個(gè)機(jī)器人生成不同的任務(wù)。

function compareRobots(robot1, memory1, robot2, memory2) {
  // Your code here
}

compareRobots(routeRobot, [], goalOrientedRobot, []);

你能寫一個(gè)機(jī)器人，比goalOrientedRobot更快完成遞送任務(wù)嗎？ 如果你觀察機(jī)器人的行為，它會(huì)做什么明顯愚蠢的事情？如何改進(jìn)它們？

如果你解決了上一個(gè)練習(xí)，你可能打算使用compareRobots函數(shù)來(lái)驗(yàn)證你是否改進(jìn)了機(jī)器人。

// Your code here

runRobotAnimation(VillageState.random(), yourRobot, memory);

標(biāo)準(zhǔn) JavaScript 環(huán)境中提供的大多數(shù)數(shù)據(jù)結(jié)構(gòu)不太適合持久使用。 數(shù)組有slice和concat方法，可以讓我們輕松創(chuàng)建新的數(shù)組而不會(huì)損壞舊數(shù)組。 但是Set沒有添加或刪除項(xiàng)目并創(chuàng)建新集合的方法。

編寫一個(gè)新的類PGroup，類似于第六章中的Group類，它存儲(chǔ)一組值。 像Group一樣，它具有add，delete和has方法。

然而，它的add方法應(yīng)該返回一個(gè)新的PGroup實(shí)例，并添加給定的成員，并保持舊的不變。 與之類似，delete創(chuàng)建一個(gè)沒有給定成員的新實(shí)例。

該類應(yīng)該適用于任何類型的值，而不僅僅是字符串。 當(dāng)與大量值一起使用時(shí)，它不一定非常高效。

構(gòu)造函數(shù)不應(yīng)該是類接口的一部分（盡管你絕對(duì)會(huì)打算在內(nèi)部使用它）。 相反，有一個(gè)空的實(shí)例PGroup.empty，可用作起始值。

為什么只需要一個(gè)PGroup.empty值，而不是每次都創(chuàng)建一個(gè)新的空分組？

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