寻路

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

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

在图上寻找路线的问题是一个典型的搜索问题。 我们可以判断一个给定的解决方案（路线）是否是一个有效的解决方案，但我们不能像 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，但仍然绝对不是最优的。