我试图理解一个解决练习2,第3章-算法设计由tardos。
但我不知道答案。
简言之,问题是
我们给出了两个位于节点a和节点b的机器人,它们分别需要移动到节点c和节点d问题是如果其中一个节点彼此靠近。”假设距离为r答案很长,对我来说没有任何意义,或者我不明白它的意思。
不管怎样,我想我们不能执行dfs/bfs来找到从节点a到节点c和从节点b到节点d的路径。然后我们修改dfs/bfs算法,以便我们在每次移动时都检查机器人是否彼此靠近?
由于需要在多项式时间内解决这个问题,我认为对任何算法“bfs/dfs”的修改都不会耗费大量时间。
解决办法是“从书本上”
如果我们从底层图g的层次来看待事物,这个问题可能很难思考:对于给定的机器人配置,即每个机器人的当前位置,我们不清楚应该使用什么规则来决定下一个机器人如何移动。因此,我们采用一种方法,这种方法对于我们试图执行这种搜索的情况非常有用。我们观察到我们的问题看起来很像一个路径发现问题,不是在原始图G中,而是在所有可能配置的空间中。
让我们定义下面的(较大的)图h。h的节点集是机器人的所有可能配置的集合;即h由g中所有可能的节点对组成。如果h的两个节点表示在一个计划中可以连续的配置,则用一条边将它们连接起来;即(u,v)和(u′,v′)将用h中的一条边连接起来,如果其中一对u,u′或v,v′相等,另一对对应于G中的边。
为什么需要更大的图h?
他的意思是:h的节点集是机器人所有可能的配置的集合,即h由g中所有可能的节点对组成。
他是什么意思:如果H的两个节点表示一个排程中可以连续的构型,我们就用一条边把它们连接起来;也就是说,如果其中一对u,u′或v,v′相等,而另一对对应于G中的一条边,那么(u,v)和(u′,v′)就会用H中的一条边连接起来。?

最佳答案

我没有这本书,但从他们的回答看来,他们每走一步都会移动一个或另一个机器人。假设H由所有可能的节点对组成,这些节点对之间的距离大于r如果通过移动一个或另一个机器人可以到达H中的节点,则H中的节点是相邻的。
在你提出的算法中没有足够的细节来说明它。

10-05 22:58
查看更多