七、项目：机器人

[...] 置疑计算机能不能思考 [...] 就相当于置疑潜艇能不能游泳。

艾兹格尔·迪科斯特拉，《计算机科学的威胁》

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

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

Meadowfield

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