第 7 章项目：机器人

[...] 机器是否能思考的问题 [...] 与潜艇是否能游泳的问题一样不相关。

在“项目”章节中，我会暂时停止向您灌输新的理论，而是与您一起完成一个程序。理论对于学习编程是必要的，但阅读和理解实际的程序也同样重要。

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

草地镇

草地镇不是很大。它由 11 个地方和 14 条道路组成。可以使用以下道路数组来描述它

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

移动导致包裹被投递，这在下一个状态中反映出来。但初始状态仍然描述了机器人位于邮局，包裹未投递的情况。

持久数据

不改变的数据结构称为不可变或持久。它们的行为与字符串和数字非常相似，因为它们是它们本身，并保持不变，而不是在不同时间包含不同的内容。

在 JavaScript 中，几乎所有东西都可以更改，因此使用应该持久的数值需要一些克制。有一个名为 Object.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() 返回一个介于零和一之间的数字——但始终低于一。将这样的数字乘以数组的长度，然后应用 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的实现方式现在仍然是一个谜，但在阅读了本书的后续章节（讨论了 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，类似于第 6 章中的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