七, 项目: 机器人
译者: 飞龙 https://github.com/wizardforcel
协议: CC BY-NC-SA 4.0 http://creativecommons.org/licenses/by-nc-sa/4.0/
自豪地采用谷歌翻译 https://translate.google.cn/
部分参考了JavaScript 编程精解(第 2 版) https://book.douban.com/subject/26707144/
[...] 置疑计算机能不能思考 [...] 就相当于置疑潜艇能不能游泳.
艾兹格尔. 迪科斯特拉,计算机科学的威胁
https://raw.githubusercontent.com/wizardforcel/eloquent-js-3e-zh/master/img/7-0.png
在 "项目" 章节中, 我会在短时间内停止向你讲述新理论, 相反我们会一起完成一个项目. 学习编程理论是必要的, 但阅读和理解实际的计划同样重要.
我们在本章中的项目是构建一个自动机, 一个在虚拟世界中执行任务的小程序. 我们的自动机将是一个接送包裹的邮件递送机器人.
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"
- ];
- https://raw.githubusercontent.com/wizardforcel/eloquent-js-3e-zh/master/img/7-1.jpg
村里的道路网络形成了一个图. 图是节点 (村里的地点) 与他们之间的边 (道路) 的集合. 这张图将成为我们的机器人在其中移动的世界.
字符串数组并不易于处理. 我们感兴趣的是, 我们可以从特定地点到达的目的地. 让我们将道路列表转换为一个数据结构, 对于每个地点, 都会告诉我们从那里可以到达哪些地点.
- 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
来源: http://www.jianshu.com/p/f631ed2dc501