- 程序有所改变。发帖如还有问题请报告
- 【征集】西西河的经济学，及清流措施，需要主动参与者，『稷下学宫』新认证方式，24年网站打算和努力目标
主题：再次请教河里的高手，一个图论问题 -- 棒棒糖
共:💬26 🌺15 新:
我的思路是dynamic programming：假设路径长度为N，先计算出N=2的所有情况，存储路径上的节点号。
然后开始利用N的结果计算N+1的路径，对于有回路的，就prune.
这里面可以优化的细节很多，首先，存储路径上节点的方式，可以帮助后来loop detection + prune。其次，存储路径上面，可以根据 i<j -> {i,j}一定存在来节省空间。最后，如果N太大，可以用divide and conquer的方法，只存储部分结果（i.e. N/2），然后用时间换空间，计算另外一半路径。
具体的程序就不写了，主要是说说思路。
- 相关回复 上下关系8
🙂再次请教河里的高手，一个图论问题 1 棒棒糖 字1001 2007-06-15 00:52:00
🙂一个算法描述： 1 泰让 字476 2007-06-16 08:46:45
🙂如果节点数不多，可否这样做？
🙂用c#实现的 1 闲扫落花 字1316 2007-06-15 09:44:05
🙂算法效率很重要 1 棒棒糖 字126 2007-06-15 10:59:52
🙂程序没有细看，不知道理解的对否 1 棒棒糖 字251 2007-06-15 10:52:18
🙂照你这意思，可以根据反向回路集来求解 1 小愚 字54 2007-06-15 17:01:08
🙂startnodes 1 小愚 字84 2007-06-15 09:56:26