项目：机器人
在“项目”章节中，我会暂时停止向您灌输新的理论，而是和您一起完成一个程序。理论对于学习编程来说是必要的，但阅读和理解实际程序同样重要。
本章的项目是构建一个自动机，一个小程序，它在一个虚拟世界中执行一项任务。我们的自动机将是一个邮递机器人，负责收取和投递包裹。
草地村
草地村不是很大。它由 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 (from in graph) { graph[from].push(to); } else { graph[from] = [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
为什么我要费尽心思不去改变对象，而语言显然希望我去改变对象？因为这有助于我理解自己的程序。这再次与复杂性管理有关。当系统中的对象是固定的、稳定的东西时，我可以隔离地考虑对它们的运算——从给定初始状态移动到 Alice 的房子总是产生相同的新的状态。当对象随着时间的推移发生改变时，就会在该推理中增加一个全新的复杂维度。
对于像本章中正在构建的这样的小型系统，我们可以处理这种额外的复杂性。但限制我们能够构建的系统类型的最重要的限制是我们的理解程度。任何使代码更容易理解的东西，都会使构建更复杂的系统成为可能。
不幸的是，尽管理解基于持久数据结构的系统更容易，但设计一个系统（尤其是在您的编程语言没有帮助的情况下）可能会更难一些。在本书中，我们将寻找使用持久数据结构的机会，但我们也会使用可变的数据结构。
模拟
送货机器人观察世界，并决定想要向哪个方向移动。因此，我们可以说机器人是一个函数，它接收一个 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 的实现方式目前仍是个谜，但读完本书的后面的章节（讨论 JavaScript 在 Web 浏览器中的集成）后，你就能猜到它的工作原理了。
邮车的路线
我们应该能够比随机机器人做得更好。一个简单的改进方法是借鉴现实世界中邮递员的做法。如果我们找到一条经过村庄所有地方的路线，机器人就可以跑两次这条路线，这样它就一定能完成任务。以下是一条这样的路线（从邮局开始）
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