2

我目前正在研究一个问题，我想尝试找到一个执行以下操作的算法：给定一个方形网格图 G 和起始节点 S 和一个结束节点 E，其中 E 和 S 在 G 中，找到从 S 到的路径 P具有最大值的 E 和 |P| <= k。如果它变得更容易，则可以使 G 成为 DAG。

网格单元为 0 或 1。

举个例子：

S--o--o--o
|  :  |  |
o--o..o..o
:  |  :  |
o--o--E--o
|  :  |  |
o--o--o--o

S := "Starting State" 
E := "Ending State" 
- := "Edge value is 1" 
. := "Edge value is 0"

k = 5 的解决方案（据我所见）

S  o  o  o
|         
o--o  o  o
   |     
o  o--E  o

o  o  o  o

S 和 E 是任意的，所以不能假设只是向下和向右移动，但我可以将图转换为 DAG，但我假设会损失一些最优性。

边值是一个成本，G 是一个网格图，其中每个节点都连接到它的四个邻居。

首先，这个问题在文献中是否已经知道？我没有找到任何关于它的信息。是在 NP 中还是有人对快速算法有想法？我问了我选择的搜索引擎，有人在StackOverflow上问了一些可能与之相关的问题，但他们的问题描述与 100% 不匹配，因为他们的目标是最后一行，而我的目标是一个不同的节点。

4

1 回答 1

1

好吧，先警告一下：我是一时冲动想到的。我似乎记得以前读过类似的东西，但我不记得在哪里，所以虽然它看起来是正确的，但我不能确定。如果我稍后发现一个缺陷，我会回来编辑这篇文章并通知你。

令L(k, v)是从S到某个节点v的长度最多为k的路径的值，并假设v有前辈{u1, u2, ... um}。因为G是一个 DAG，所以它一定是

L(k, v) = max { L(k-1, u1) + w(u1, v), L(k-1, u2) + w(u2, v), ..., L(k-1, um) + w(um, v) }

其中w(u,v)是从u到v的边的权重。

为了使用它，我们要做的是找到长度< R的最大值路径到S的R半径内的每个节点。然后，这为我们提供了足够的信息来计算到S的半径R+1内的每个节点的长度< R+1的最高值路径。所以：

  1. 首先，丢弃与S距离大于k的任何节点，因为它不可能是最佳路径的一部分。我们还有O(k^2)个节点。
  2. 现在初始化一个集合L并设置L[S] = 0。保留所有其他条目未定义。
  3. 接下来，将L[v]规则应用于图中的每个节点（忽略k参数）
    • 如果节点v的前任u还没有定义的值，则在计算时忽略u。L[u]L[v]
    • 如果没有定义v的前任u，则保持未定义。L[u]L[v]
  4. 再重复步骤 3 k-1次。
  5. 如果L[E]有值，则返回它。否则没有从S到Ek的长度路径。

这是O(k^3)时间。您可以通过在第 3 步的第一次执行期间仅考虑S的距离 1 和E的距离k-1内的节点，以及仅考虑S的距离 2和E的距离k-2内的节点来加快大型图的速度第二次执行，依此类推，但这仍然是立方时间。

于 2013-12-03T00:20:02.437 回答