-1

问题是这样的：一个带有障碍物的二维网格已经用“n”个机器人给出了。机器人可以在一个时间滴答内移动到相邻的单元格中。机器人有多种限制，例如它们不能同时在同一个单元中。但是，它们可以同时移动。需要为将机器人从起点移动到目的地的每个机器人找出一个行动计划，以便满足约束并且机器人花费的总时间最少。

我似乎无法理解这个问题是否是一个 NP 难题

4

1 回答 1

1

快速搜索一下最近一篇关于这个主题的论文：

有向图上多智能体寻路的计算复杂度

在这种有向图的特殊情况下，问题是 NP 难题。在许多情况下，有多项式时间算法可以找到解决方案，但即使在无向图上也很难找到最佳解决方案。（滑动瓷砖拼图是 NP-Hard，多智能体寻路是一个特例。）

于 2020-09-07T20:33:22.573 回答