Sae*_*iri 11 algorithm shortest-path
几天前,有人问我,如果我们在我们的环境中有一些代理商,并且他们想要从他们的消息来源到他们的目的地,那么我们如何才能找到他们所有人的最短路径,以便他们不应该在他们的步行.
问题的关键是所有代理人同时在环境中行走(可以通过无向加权图来建模),我们不应该有任何碰撞.我想到了这一点,但我找不到所有这些的最佳路径.但是肯定有太多启发式的想法来解决这个问题.
假定输入是图G(V,E),它们是在米剂:S 1,S 2,...,S 米在启动和图的节点它们应该去节点d 1,... d 米处结束.也可能是节点S i或D i中存在冲突,但这些冲突并不重要,当它们位于其路径的内部节点时,它们不应该发生冲突.
如果它们的路径不应该有相同的内部节点,那将k-disjoint paths是NPC的一种问题,但是在这种情况下路径可以具有相同的节点,但是代理不应该同时在同一节点中.我不知道我能说出确切的问题陈述.如果令人困惑,请在评论中告诉我编辑它.
是否有任何最优和快速的算法(通过最优I均值,所有路径的长度总和尽可能最小,并且快速意味着良好的多项式时间算法).
Google搜索会显示两个可能有用的链接:
编辑:从书的章节(第一个链接):
在多机器人系统中存在各种路径规划方法[原文如此],但是找到最优解是NP难的.Hopcraft等.(1984)将规划问题简化为矩形容器中移动矩形的问题.他们通过最少的步骤证明了从给定配置到目标配置的NP计划的NP难度.因此,所有可行的路径规划方法都是结果的效率和准确性之间的折衷.
我无法在网上找到Hopcroft的原始论文,但鉴于该引用,我怀疑他们将导航任务减少到的问题类似于高峰时段,这是PSPACE完成的.
| 归档时间： |
|
| 查看次数： |
778 次 |
| 最近记录： |