七记罚、項目：機器人

原文：Project: A Robot

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

部分參考了《JavaScript 編程精解（第 2 版）》

[...] 置疑計算機能不能思考 [...] 就相當于置疑潛艇能不能游泳浅妆。

艾茲格爾·迪科斯特拉望迎，《計算機科學的威脅》

https://raw.githubusercontent.com/wizardforcel/eloquent-js-3e-zh/master/img/7-0.png

在“項目”章節(jié)中，我會在短時間內(nèi)停止向你講述新理論凌外，相反我們會一起完成一個項目辩尊。 學習編程理論是必要的，但閱讀和理解實際的計劃同樣重要康辑。

我們在本章中的項目是構建一個自動機摄欲，一個在虛擬世界中執(zhí)行任務的小程序。 我們的自動機將是一個接送包裹的郵件遞送機器人疮薇。

Meadowfield

Meadowfield 村不是很大胸墙。 它由 11 個地點和 14 條道路組成。 它可以用roads數(shù)組來描述：

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

https://raw.githubusercontent.com/wizardforcel/eloquent-js-3e-zh/master/img/7-1.jpg

村里的道路網(wǎng)絡形成了一個圖按咒。 圖是節(jié)點（村里的地點）與他們之間的邊（道路）的集合迟隅。 這張圖將成為我們的機器人在其中移動的世界。

字符串數(shù)組并不易于處理胖齐。 我們感興趣的是玻淑，我們可以從特定地點到達的目的地。 讓我們將道路列表轉換為一個數(shù)據(jù)結構呀伙，對于每個地點补履，都會告訴我們從那里可以到達哪些地點。

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)建一個映射對象箫锤，該對象為每個節(jié)點存儲連通節(jié)點的數(shù)組贬蛙。

它使用split方法，將形式為"Start-End"的道路字符串谚攒，轉換為兩元素數(shù)組阳准，包含起點和終點作為單個字符串。

任務

我們的機器人將在村莊周圍移動馏臭。 在各個地方都有包裹野蝇，每個都寄往其他地方。 機器人在收到包裹時拾取包裹括儒，并在抵達目的地時將其送達绕沈。

自動機必須在每個點決定下一步要去哪里。 所有包裹遞送完成后帮寻，它就完成了任務乍狐。

為了能夠模擬這個過程，我們必須定義一個可以描述它的虛擬世界固逗。 這個模型告訴我們機器人在哪里以及包裹在哪里浅蚪。 當機器人決定移到某處時，我們需要更新模型以反映新情況烫罩。

如果你正在考慮面向?qū)ο缶幊滔О粒愕牡谝粋€沖動可能是開始為世界中的各種元素定義對象。 一個機器人嗡髓，一個包裹操漠，也許還有一個地點收津。 然后饿这，它們可以持有描述其當前狀態(tài)的屬性，例如某個位置的一堆包裹撞秋，我們可以在更新世界時改變這些屬性长捧。

這是錯的。

至少吻贿，通常是這樣串结。 一個東西聽起來像一個對象，并不意味著它應該是你的程序中的一個對象舅列。 為應用程序中的每個概念反射式編寫類肌割，往往會留下一系列互連對象，每個對象都有自己的內(nèi)部的變化的狀態(tài)帐要。 這樣的程序通常很難理解把敞，因此很容易崩潰。

相反榨惠，讓我們將村莊的狀態(tài)壓縮成定義它的值的最小集合奋早。 機器人的當前位置和未送達的包裹集合盛霎，其中每個都擁有當前位置和目標地址。這樣就夠了耽装。

當我們到達新地點時愤炸，讓我們這樣做，在機器人移動時不會改變這種狀態(tài)掉奄，而是在移動之后為當前情況計算一個新狀態(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方法是動作發(fā)生的地方。 它首先檢查是否有當前位置到目的地的道路姓建，如果沒有绰姻，則返回舊狀態(tài)，因為這不是有效的移動引瀑。

然后它創(chuàng)建一個新的狀態(tài)狂芋，將目的地作為機器人的新地點。 但它也需要創(chuàng)建一套新的包裹 - 機器人攜帶的包裹（位于機器人當前位置）需要移動到新位置憨栽。 而要寄往新地點的包裹需要送達 - 也就是說帜矾，需要將它們從未送達的包裹中移除。 'map'的調(diào)用處理移動屑柔，并且'filter'的調(diào)用處理遞送屡萤。

包裹對象在移動時不會更改，但會被重新創(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會使包裹被送達唧瘾，并在下一個狀態(tài)中反映出來措译。 但最初的狀態(tài)仍然描述機器人在郵局并且包裹未送達的情況。

持久性數(shù)據(jù)

不會改變的數(shù)據(jù)結構稱為不變的（immutable）或持久性的（persistent）饰序。 他們的表現(xiàn)很像字符串和數(shù)字领虹，因為他們就是他們自己，并保持這種狀態(tài)求豫，而不是在不同的時間包含不同的東西塌衰。

在 JavaScript 中，幾乎所有的東西都可以改變蝠嘉，所以使用應該持久性的值需要一些限制最疆。 有一個叫做Object.freeze的函數(shù)，它可以改變一個對象蚤告，使其忽略它的屬性的寫入努酸。 如果你想要小心，你可以使用它來確保你的對象沒有改變罩缴。 freeze確實需要計算機做一些額外的工作蚊逢，忽略更新可能會讓一些人迷惑层扶，讓他們做錯事。 所以我通常更喜歡告訴人們烙荷，不應該弄亂給定的對象镜会，并希望他們記住它。

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

當語言顯然期待我這樣做時终抽，為什么我不想改變對象戳表？

因為它幫助我理解我的程序。 這又是關于復雜性管理昼伴。 當我的系統(tǒng)中的對象是固定的匾旭，穩(wěn)定的東西時，我可以孤立地考慮操作它們 - 從給定的起始狀態(tài)移動到愛麗絲的房子圃郊，始終會產(chǎn)生相同的新狀態(tài)价涝。 當對象隨著時間而改變時，這就給這種推理增加了全新的復雜性持舆。

對于小型系統(tǒng)色瘩，例如我們在本章中構建的東西，我們可以處理那些額外的復雜性逸寓。 但是我們可以建立什么樣的系統(tǒng)居兆，最重要的限制是我們能夠理解多少。 任何讓你的代碼更容易理解的東西竹伸，都可以構建一個更加龐大的系統(tǒng)泥栖。

不幸的是，盡管理解構建在持久性數(shù)據(jù)結構上的系統(tǒng)比較容易勋篓，但設計一個吧享，特別是當你的編程語言沒有幫助時，可能會更難一些生巡。 我們將在本書中尋找使用持久性數(shù)據(jù)結構的時機耙蔑，但我們也將使用可變數(shù)據(jù)結構。

模擬

遞送機器人觀察世界并決定它想要移動的方向孤荣。 因此，我們可以說機器人是一個函數(shù)须揣，接受VillageState對象并返回附近地點的名稱盐股。

因為我們希望機器人能夠記住東西，以便他們可以制定和執(zhí)行計劃耻卡，我們也會傳遞他們的記憶疯汁，并讓他們返回一個新的記憶。 因此卵酪，機器人返回的東西是一個對象幌蚊，包含它想要移動的方向谤碳，以及下次調(diào)用時將返回給它的記憶值。

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

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

什么是可能有效的最愚蠢的策略搓茬？ 機器人可以在每回合中，向隨機方向行走队他。 這意味著很有可能它最終會碰到所有的包裹卷仑，然后也會在某個時候到達包裹應該送達的地方。

以下是可能的樣子：

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 之間的數(shù)字锡凝，但總是小于 1。 將這樣一個數(shù)乘以數(shù)組長度垢啼，然后將Math.floor應用于它私爷，向我們提供數(shù)組的隨機索引。

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

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

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ā)往寄出地的任何包裹进统。 出于這個原因助币，當do循環(huán)獲取與地址相同的地方時，它會繼續(xù)選擇新的地方螟碎。

讓我們建立一個虛擬世界眉菱。

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

機器人需要花費很多時間來交付包裹，因為它沒有很好規(guī)劃掉分。 我們很快就會解決俭缓。

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

runRobotAnimation(VillageState.random(), randomRobot);

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

郵車的路線

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

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

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

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

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

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

尋路

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

為此婉刀，它必須能夠有針對性地朝著給定的包裹移動吟温，或者朝著包裹必須送達的地點。 盡管如此突颊，即使目標距離我們不止一步鲁豪，也需要某種尋路函數(shù)。

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

圖上的可能路線是無限的柜裸。 但是當搜索A到B的路線時，我們只關注從A起始的路線掷漱。 我們也不關心兩次訪問同一地點的路線 - 這絕對不是最有效的路線粘室。 這樣可以減少查找者必須考慮的路線數(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)});
      }
    }
  }
}

探索必須按照正確的順序完成 - 首先到達的地方必須首先探索埠啃。 我們不能到達一個地方就立即探索，因為那樣意味著伟恶，從那里到達的地方也會被立即探索碴开，以此類推，盡管可能還有其他更短的路徑尚未被探索博秫。

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

然后即寒，通過獲取列表中的下一個項目并進行探索橡淆，來執(zhí)行搜索，這意味著蒿叠，會查看從該地點起始的所有道路明垢。 如果其中之一是目標，則可以返回完成的路線市咽。 否則痊银，如果我們以前沒有看過這個地方，就會在列表中添加一個新項目施绎。 如果我們之前看過它溯革，因為我們首先查看了短路線，我們發(fā)現(xiàn)谷醉，到達那個地方的路線較長致稀，或者與現(xiàn)有路線一樣長，我們不需要探索它俱尼。

你可以在視覺上將它想象成一個已知路線的網(wǎng)抖单，從起始位置爬出來，在各個方向上均勻生長（但不會纏繞回去）。 只要第一條線到達目標位置矛绘，其它線就會退回起點耍休，為我們提供路線。

我們的代碼無法處理工作列表中沒有更多工作項的情況货矮，因為我們知道我們的圖是連通的羊精，這意味著可以從其他所有位置訪問每個位置。 我們始終能夠找到兩點之間的路線囚玫，并且搜索不會失敗喧锦。

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

這個機器人使用它的記憶值作為移動方向的列表，就像尋路機器人一樣抓督。 無論什么時候這個列表是空的燃少，它都必須弄清下一步該做什么。 它會取出集合中第一個未送達的包裹本昏，如果該包裹還沒有被拾取供汛，則會繪制一條朝向它的路線。 如果包裹已經(jīng)被拾取涌穆，它仍然需要送達怔昨，所以機器人會創(chuàng)建一個朝向遞送地址的路線。

讓我們看看如何實現(xiàn)宿稀。

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

這個機器人通常在大約 16 個回合中趁舀，完成了送達 5 個包裹的任務。 略好于routeRobot祝沸，但仍然絕對不是最優(yōu)的矮烹。

練習

測量機器人

很難通過讓機器人解決一些場景來客觀比較他們。 也許一個機器人碰巧得到了更簡單的任務罩锐，或者它擅長的那種任務奉狈，而另一個沒有。

編寫一個compareRobots涩惑，接受兩個機器人（和它們的起始記憶）仁期。 它應該生成 100 個任務，并讓每個機器人解決每個這些任務竭恬。 完成后跛蛋，它應輸出每個機器人每個任務的平均步數(shù)。

為了公平起見痊硕，請確保你將每個任務分配給兩個機器人赊级，而不是為每個機器人生成不同的任務。

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

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

機器人的效率

你能寫一個機器人岔绸，比goalOrientedRobot更快完成遞送任務嗎理逊？ 如果你觀察機器人的行為橡伞，它會做什么明顯愚蠢的事情？如何改進它們挡鞍？

如果你解決了上一個練習骑歹，你可能打算使用compareRobots函數(shù)來驗證你是否改進了機器人预烙。

// Your code here

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

持久性分組

標準 JavaScript 環(huán)境中提供的大多數(shù)數(shù)據(jù)結構不太適合持久使用墨微。 數(shù)組有slice和concat方法，可以讓我們輕松創(chuàng)建新的數(shù)組而不會損壞舊數(shù)組扁掸。 但是Set沒有添加或刪除項目并創(chuàng)建新集合的方法翘县。

編寫一個新的類PGroup，類似于第六章中的Group類谴分，它存儲一組值锈麸。 像Group一樣，它具有add牺蹄，delete和has方法忘伞。

然而，它的add方法應該返回一個新的PGroup實例沙兰，并添加給定的成員氓奈，并保持舊的不變。 與之類似鼎天，delete創(chuàng)建一個沒有給定成員的新實例舀奶。

該類應該適用于任何類型的值，而不僅僅是字符串斋射。 當與大量值一起使用時育勺，它不一定非常高效。

構造函數(shù)不應該是類接口的一部分（盡管你絕對會打算在內(nèi)部使用它）罗岖。 相反涧至，有一個空的實例PGroup.empty，可用作起始值桑包。

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

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