9

我想将循环图转换为非循环图。有没有可以做到这一点的伪代码？我确实尝试过搜索，但他们中的大多数都返回了基于马尔可夫链或研究文章的数学。

我想编写一个程序来做到这一点，任何指示都会很有用。例如考虑下图。

A->B
B->C
C->A

我在麻省理工学院的一次讲座中看到了一个解决方案，但讲座略过了它，参考了之前教过的东西，无法理解。简而言之，它以一种最终图表示DAG但传达相同路径信息的方式在层中复制节点。

[见 46:59]

https://www.youtube.com/watch?v=OQ5jsbhAv_M

编辑：

我想对循环图问题应用动态编程，例如）说最短路径问题Delta(S,D) where S-> Source node and D->Destination node。由于循环图上的DP是无限算法，我们首先需要将循环图转换为无循环图，然后对其应用动态规划技术。

4

1 回答 1

1

我相信您指出了错误的视频，这里是 (46:59)：https ://www.youtube.com/watch?v=OQ5jsbhAv_M

这里公开的想法是制作图形的多个副本并将它们排列成层。每一个都代表图在给定时间的状态，并且对于遍历的每条边，您都会下降一层。我没有找到伪代码，但这里详细介绍了这样做的方法：https ://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-循环图非循环

于 2016-05-15T10:03:27.710 回答