4

我正在构建一个机器人模拟器，其中有 n 个机器人需要去 n 个不同的位置。所有机器人同时开始移动。当机器人到达指定位置时，它会停止移动。所有机器人到达其位置所需的总时间由给定机器人到达其指定位置所需的最长长度决定。我想通过巧妙地将目的地分配给机器人来最小化这个最长的长度。

显然这个问题是“线性瓶颈分配问题”。

我找不到任何代码来解决这个问题。任何人都有任何伪代码或实际代码（任何语言都可以，首选 Ruby/Java）来有效地解决这个问题？

4

2 回答 2

2

阈值算法是解决线性瓶颈分配问题的标准算法之一。快速搜索并没有找到我可以在此处轻松复制和粘贴的伪代码，但伪代码由 Rainer Burkard、Mauro Dell'Amico 和 Silvano Martello在Assignment Problems的第 175 页给出。这是相关页面的 Google 图书链接。几页后，他们给出了另一种利用对偶性的算法，但我对那个算法不太熟悉。

于 2012-11-27T03:56:42.100 回答
0

LBAP（线性瓶颈分配）只是与您的案例相关的整个分配和路径路由问题系列中的一个特定子类。

在决定为您的 n 个机器人实施MinMax路由算法时，您有很多选择。这就是我要做的：我将从Dijkstra 最短路径算法的最简单实现开始。

Dijkstra的wikipedia 页面有一个很好的可视化示例，但它们的伪代码看起来比它需要的更令人生畏。它甚至链接到机器人运动规划，尽管从您的问题来看，您似乎正在寻找要实施的路径算法。

[根据 OP 的澄清更新。最小最大]

Dijkstra 仍然有效，但您需要执行一些额外的步骤。以下是基本策略：

For each robot r = 1 to n
   calculate the shortest time-path for r from source of r to sink of r - (suggest starting with Dijkstra's) [if you are assuming constant speeds, then distance and length become equivalent]
Next r

MinMax 模式：

  1. 按所用时间对所有路径（时间）进行排序并取最长的路径。（这是您的理论最小最大时间。） - 我们称之为t_max
  2. 其他机器人 r 有时间"slack"-t_max 减 time_r
  3. 拿每一对机器人，看看它们的路径是否冲突。
    • 如果没有冲突，你就完成了。
    • 如果是冲突，那么您必须在松弛时间内重新路由（冲突节点/边缘避免）。（最简单的重新路由是等到冲突的机器人清除边缘或交叉点。）
  4. 如果你能够在 内路由slack，你就完成了。否则，将 t_max 更新为最长（重新路由）路径。

以下是您应该能够使用的一些 Dijkstra 代码示例。（网络搜索将产生更多。）

  1. http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html（Java）
  2. 这是Ruby的要点

补充说明：

  1. 你不必局限于 Dijkstra 的方法。您可以换出并尝试找到其他路由算法。尝试一些路由算法。
  2. 记得检查冲突。（即两个机器人同时在同一个节点t） 无冲突路由的最基本实现涉及一些优先规则，一个机器人要等到节点清除后再继续。

希望有帮助。

于 2012-11-27T20:11:17.503 回答