JavaScript 编程精解 中文第三版 七、项目：机器人

摘要：来源编程精解中文第三版翻译项目原文译者飞龙协议自豪地采用谷歌翻译置疑计算机能不能思考就相当于置疑潜艇能不能游泳。这张图将成为我们的机器人在其中移动的世界。机器人在收到包裹时拾取包裹，并在抵达目的地时将其送达。这个机器人已经快了很多。

来源：ApacheCN『JavaScript 编程精解 中文第三版』翻译项目
原文：Project: A Robot
译者：飞龙
协议：CC BY-NC-SA 4.0
自豪地采用谷歌翻译
[...] 置疑计算机能不能思考 [...] 就相当于置疑潜艇能不能游泳。
艾兹格尔·迪科斯特拉，《计算机科学的威胁》

在“项目”章节中，我会在短时间内停止向你讲述新理论，相反我们会一起完成一个项目。 学习编程理论是必要的，但阅读和理解实际的计划同样重要。

我们在本章中的项目是构建一个自动机，一个在虚拟世界中执行任务的小程序。 我们的自动机将是一个接送包裹的邮件递送机器人。

Meadowfield 村不是很大。 它由 11 个地点和 14 条道路组成。 它可以用roads数组来描述：

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

村里的道路网络形成了一个图。 图是节点（村里的地点）与他们之间的边（道路）的集合。 这张图将成为我们的机器人在其中移动的世界。

字符串数组并不易于处理。 我们感兴趣的是，我们可以从特定地点到达的目的地。 让我们将道路列表转换为一个数据结构，对于每个地点，都会告诉我们从那里可以到达哪些地点。

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"的道路字符串，转换为两元素数组，包含起点和终点作为单个字符串。

我们的机器人将在村庄周围移动。 在各个地方都有包裹，每个都寄往其他地方。 机器人在收到包裹时拾取包裹，并在抵达目的地时将其送达。

自动机必须在每个点决定下一步要去哪里。 所有包裹递送完成后，它就完成了任务。

为了能够模拟这个过程，我们必须定义一个可以描述它的虚拟世界。 这个模型告诉我们机器人在哪里以及包裹在哪里。 当机器人决定移到某处时，我们需要更新模型以反映新情况。

如果你正在考虑面向对象编程，你的第一个冲动可能是开始为世界中的各种元素定义对象。 一个机器人，一个包裹，也许还有一个地点。 然后，它们可以持有描述其当前状态的属性，例如某个位置的一堆包裹，我们可以在更新世界时改变这些属性。

这是错的。

至少，通常是这样。 一个东西听起来像一个对象，并不意味着它应该是你的程序中的一个对象。 为应用程序中的每个概念反射式编写类，往往会留下一系列互连对象，每个对象都有自己的内部的变化的状态。 这样的程序通常很难理解，因此很容易崩溃。

相反，让我们将村庄的状态压缩成定义它的值的最小集合。 机器人的当前位置和未送达的包裹集合，其中每个都拥有当前位置和目标地址。这样就够了。

当我们到达新地点时，让我们这样做，在机器人移动时不会改变这种状态，而是在移动之后为当前情况计算一个新状态。

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方法为我们提供新的村庄状态，但完全保留了原有的村庄状态。

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确实需要计算机做一些额外的工作，忽略更新可能会让一些人迷惑，让他们做错事。 所以我通常更喜欢告诉人们，不应该弄乱给定的对象，并希望他们记住它。

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

当语言显然期待我这样做时，为什么我不想改变对象？

因为它帮助我理解我的程序。 这又是关于复杂性管理。 当我的系统中的对象是固定的，稳定的东西时，我可以孤立地考虑操作它们 - 从给定的起始状态移动到爱丽丝的房子，始终会产生相同的新状态。 当对象随着时间而改变时，这就给这种推理增加了全新的复杂性。

对于小型系统，例如我们在本章中构建的东西，我们可以处理那些额外的复杂性。 但是我们可以建立什么样的系统，最重要的限制是我们能够理解多少。 任何让你的代码更容易理解的东西，都可以构建一个更加庞大的系统。

不幸的是，尽管理解构建在持久性数据结构上的系统比较容易，但设计一个，特别是当你的编程语言没有帮助时，可能会更难一些。 我们将在本书中寻找使用持久性数据结构的时机，但我们也将使用可变数据结构。

递送机器人观察世界并决定它想要移动的方向。 因此，我们可以说机器人是一个函数，接受VillageState对象并返回附近地点的名称。

因为我们希望机器人能够记住东西，以便他们可以制定和执行计划，我们也会传递他们的记忆，并让他们返回一个新的记忆。 因此，机器人返回的东西是一个对象，包含它想要移动的方向，以及下次调用时将返回给它的记忆值。

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

考虑一下机器人必须做些什么来“解决”一个给定的状态。 它必须通过访问拥有包裹的每个位置来拾取所有包裹，并通过访问包裹寄往的每个位置来递送，但只能在拾取包裹之后。

什么是可能有效的最愚蠢的策略？ 机器人可以在每回合中，向随机方向行走。 这意味着很有可能它最终会碰到所有的包裹，然后也会在某个时候到达包裹应该送达的地方。

以下是可能的样子：

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属性。

为了使这个复杂的机器人工作，我们首先需要一种方法来创建一些包裹的新状态。 静态方法（通过直接向构造函数添加一个属性来编写）是放置该功能的好地方。

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循环获取与地址相同的地方时，它会继续选择新的地方。

让我们建立一个虚拟世界。

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

机器人需要花费很多时间来交付包裹，因为它没有很好规划。 我们很快就会解决。

为了更好地理解模拟，你可以使用本章编程环境中提供的runRobotAnimation函数。 这将运行模拟，但不是输出文本，而是向你展示机器人在村庄地图上移动。

runRobotAnimation(VillageState.random(), randomRobot);

runRobotAnimation的实现方式现在仍然是一个谜，但是在阅读本书的后面的章节，讨论 Web 浏览器中的 JavaScript 集成之后，你将能够猜到它的工作原理。

我们应该能够比随机机器人做得更好。 一个简单的改进就是从现实世界的邮件传递方式中获得提示。 如果我们发现一条经过村庄所有地点的路线，机器人可以通行该路线两次，此时它保证能够完成。 这是一条这样的路线（从邮局开始）。

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

为了实现路线跟踪机器人，我们需要利用机器人的记忆。 机器人将其路线的其余部分保存在其记忆中，并且每回合丢弃第一个元素。

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

这个机器人已经快了很多。 它最多需要 26 个回合（13 步的路线的两倍），但通常要少一些。

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

不过，我不会盲目遵循固定的智能寻路行为。 如果机器人为需要完成的实际工作调整行为，它可以更高效地工作。

为此，它必须能够有针对性地朝着给定的包裹移动，或者朝着包裹必须送达的地点。 尽管如此，即使目标距离我们不止一步，也需要某种寻路函数。

在图上寻找路线的问题是一个典型的搜索问题。 我们可以判断一个给定的解决方案（路线）是否是一个有效的解决方案，但我们不能像 2 + 2 这样，直接计算解决方案。 相反，我们必须不断创建潜在的解决方案，直到找到有效的解决方案。

图上的可能路线是无限的。 但是当搜索A到B的路线时，我们只关注从A起始的路线。 我们也不关心两次访问同一地点的路线 - 这绝对不是最有效的路线。 这样可以减少查找者必须考虑的路线数量。

事实上，我们最感兴趣的是最短路线。 所以我们要确保，查看较长路线之前，我们要查看较短的路线。 一个好的方法是，从起点使路线“生长”，探索尚未到达的每个可到达的地方，直到路线到达目标。 这样，我们只探索潜在的有趣路线，并找到到目标的最短路线（或最短路线之一，如果有多条路线）。

这是一个实现它的函数：

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

探索必须按照正确的顺序完成 - 首先到达的地方必须首先探索。 我们不能到达一个地方就立即探索，因为那样意味着，从那里到达的地方也会被立即探索，以此类推，尽管可能还有其他更短的路径尚未被探索。

因此，该函数保留一个工作列表。 这是一系列应该探索的地方，以及让我们到那里的路线。 它最开始只有起始位置和空路线。

然后，通过获取列表中的下一个项目并进行探索，来执行搜索，这意味着，会查看从该地点起始的所有道路。 如果其中之一是目标，则可以返回完成的路线。 否则，如果我们以前没有看过这个地方，就会在列表中添加一个新项目。 如果我们之前看过它，因为我们首先查看了短路线，我们发现，到达那个地方的路线较长，或者与现有路线一样长，我们不需要探索它。

你可以在视觉上将它想象成一个已知路线的网，从起始位置爬出来，在各个方向上均匀生长（但不会缠绕回去）。 只要第一条线到达目标位置，其它线就会退回起点，为我们提供路线。

我们的代码无法处理工作列表中没有更多工作项的情况，因为我们知道我们的图是连通的，这意味着可以从其他所有位置访问每个位置。 我们始终能够找到两点之间的路线，并且搜索不会失败。

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

这个机器人使用它的记忆值作为移动方向的列表，就像寻路机器人一样。 无论什么时候这个列表是空的，它都必须弄清下一步该做什么。 它会取出集合中第一个未送达的包裹，如果该包裹还没有被拾取，则会绘制一条朝向它的路线。 如果包裹已经被拾取，它仍然需要送达，所以机器人会创建一个朝向递送地址的路线。

让我们看看如何实现。

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

这个机器人通常在大约 16 个回合中，完成了送达 5 个包裹的任务。 略好于routeRobot，但仍然绝对不是最优的。

很难通过让机器人解决一些场景来客观比较他们。 也许一个机器人碰巧得到了更简单的任务，或者它擅长的那种任务，而另一个没有。

编写一个compareRobots，接受两个机器人（和它们的起始记忆）。 它应该生成 100 个任务，并让每个机器人解决每个这些任务。 完成后，它应输出每个机器人每个任务的平均步数。

为了公平起见，请确保你将每个任务分配给两个机器人，而不是为每个机器人生成不同的任务。

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

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

你能写一个机器人，比goalOrientedRobot更快完成递送任务吗？ 如果你观察机器人的行为，它会做什么明显愚蠢的事情？如何改进它们？

如果你解决了上一个练习，你可能打算使用compareRobots函数来验证你是否改进了机器人。

// 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值，而不是每次都创建一个新的空分组？

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