1回答
图的最长路的动态规划
、、、
我正在尝试获得一个“快速”运行的算法，它给定传递锦标赛的子图的邻接矩阵，计算最长路径的大小，目前我的代码如下所示： #this function defines the adjacency matrixelse: else: return(C) 我正在运行的算法是基本的动态编程，
浏览 18提问于2021-04-29得票数 0
1回答
我需要解决有向图和无向图的最长路径问题(这两种情况都是未加权的)。对于有向图，很容易找到动态规划算法，这些算法能够在伪多项式时间内解决问题，从某个节点开始，计算子问题的最长路径，直到每个问题都被解决。 我可以为无向图做类似的事情吗？我似乎找不到任何关于它的文字？
浏览 20提问于2020-11-07得票数 0
回答已采纳
假设你有一组块，每个块都有一定的高度和重量。我的方法是或多或少地解决它，就像背包问题。我把积木从轻到重，从阵列的末端开始。然后，对于我正在考虑的每一个区块，我找到了打桩与不打桩之间的最大值，并将其返回。正如您可能已经猜到的，问题是重叠子问题，因此复杂性是指数级的。
解决这个问题的通常方法是动态规划，但是我很难实现它，特别是因为有两个约束。如果存在单个约束，比如说权重，我将构建一个二维数组，其中行表示正在处理的
浏览 0提问于2011-12-10得票数 3
回答已采纳
1回答
我有两个有向无圈图，我需要计算这些图的最长公共子序列(LCS)。对于两个字符串/子序列，我使用使用动态规划(DP)的LCS算法，但如何将该算法修改为图呢？设G是一个有向无圈图，其中每个顶点都有来自有限字母表的符号标记。不同的顶点可以用相同的符号标记。G中的每个有向路径都具有跟踪，它是通过连接路径中的顶点符号而形成的。图
浏览 5提问于2014-05-12得票数 0
1回答
我们知道，寻找两个顶点之间的最大权重路径是np困难的。但是如果我们限制边权重，例如。所有的边权重都小于某个特定值x。我清楚地定义了下面的问题。我有一个有向图G(V，E)，其中每条边的权重都在1到|V|之间。我想找到两个顶点u和v之间的最大权重路径。
这个问题是多项式时间可解的吗？
浏览 1提问于2018-03-11得票数 0
1回答
最大路径值
、、、
最近，我不得不编写一个算法，用于输入5x5大小的矩阵和定义的路径长度，从第一个左上角矩阵元素(0，0)到最后一个右下角元素(n，n)，找到这个给定长度的路径。所需的路径是使该路径上的矩阵元素之和最大化的路径。在阅读了关于Dijkstra或A*和DFS与BFS等常见路径查找算法的文章之后，下面是我得出的结论： """Calculates sum of all grid这就是为什么
浏览 0提问于2019-04-02得票数 2
考虑一个没有圈的图。图中有K个不同的对，我们想要给每个other.if发送一封信给所有的人。寄一封信需要一个单位的时间。我们希望加快这一进程。那么，信件到达每个人(图的节点)的最短时间是多少？我们可以把信交给所有连接部件中的任何人。
浏览 1提问于2020-01-06得票数 0
回答已采纳
如果使用动态规划来获得某个问题的最优解。您如何重构导致该解决方案的实际步骤？使用这一点，我们可以得到背包中可以出现的最大值。您如何找到实际存在的项目。这是否可以推广到任何动态编程解决方案。例如。找出属于最长递增子序列的实际nos，其解已使用动态规划获得。
浏览 0提问于2011-10-19得票数 2
回答已采纳
例如，letA=<0，1，0，0，0，1，0>then<0>、<1>、<0，1>、<1，0>and<0，1，0，1，0>are不同的交替subsequenceswhile<1，1>is不是交替的子序列。Is<0，1，0，1，0>and的最长交替子序列，长度为5。(a)设计一个O(n^2)动态规划算法来求给定序列A的最长交替序列的长度
(b)
浏览 2提问于2020-11-13得票数 0
1回答
我有两个字符串，我必须在这些字符串之间得到相同的值String tempPath = "TEB-MRI-SUD-KRT-THB-DU-PSG-BOI-RW";我希望得到这两个字符串之间的公共值，并将它变成另一个字符串变量，如下所示String passedPath = "TEB-MRI-SUD-KRT-THB-DU-";
变量
浏览 1提问于2014-04-06得票数 0
回答已采纳
1回答
我想找出上有一定阻塞有向路径的最长路径距离。这意味着
所以我们有路径(1，3，2)，(0，2，1)等等。因此最长的距离是3。
浏览 4提问于2020-09-10得票数 2
2回答
在对这两个问题进行研究之后，我无法断定它们之间的区别是什么。哈密顿路径是一个图的两个顶点之间的一条路径，它正好访问每个顶点一次。给定一个图G和两个不同的节点S和E，G中是否有从S到E的哈密顿路径？我发现这个问题是NP-完全的在图论中，最短路径问题是求图中两个顶点(或节点)之间的一条路径，从而使其组成边的权重之和最小化的问题。这个问题是P
他们之间的实际区别
浏览 7提问于2013-02-04得票数 4
回答已采纳
1回答
这是我在课堂上遇到的一个问题(我向你保证这不是家庭作业)。直到现在，我还在思考这件事。您将收到一个最多包含25个节点和25条边的图。此外，每个节点的度最多为3。任务是在这个图中找到最长的路径。然而，你不会只收到1个图，而是15,000个图，而且你需要在1秒内找到所有图中最长的路径。有没有人能给我这个问题的解决方案(或者更好的是，只是一个提示)？非常感谢!信息：
节点是可以重新访问<
浏览 0提问于2016-05-26得票数 2
4回答
问题陈述我必须选择最大数量的矩形，条件是第一个矩形的长度>第二个矩形的长度和第一个矩形的宽度>第二个矩形的宽度。My Procedure
我所做的是根据长度和宽度对每个矩形进行排序，然后只考虑那些长度和宽度在增加的矩形，但我的排序不正常。
浏览 20提问于2014-10-14得票数 0
回答已采纳
2回答
我正在寻找一种算法，以fidn的两个点之间的网格最长的路径，并增加了限制，你不能重新访问网格上的单元。(此外，您只能向上、向下、向左和向右移动)。考虑到这些限制，我认为走最长的路径与试图填满尽可能多的空间是一样的。然而，我在弄清楚如何做到这一点上有些困难。
浏览 1提问于2013-05-12得票数 1
构造并描述了一种有效的算法，该算法以两个有向无圈图(DAG)为输入，并求出它们中存在的最长路径。如果存在多条路径，则该算法应该返回最长路径之一(这与哪条路径无关)。总之，给定图G= (V，E)和G‘=(V'，E')，找出最大可能序列<v1，…，vk>，其中(v_i，v_{i+1})在E中， E’表示I=1.k-1。
有什么想法吗？我可以自己编写实际的代码，我只需要帮助构建实际算法背后的想法，并找到问题的解决方案。我
浏览 8提问于2021-12-14得票数 0
回答已采纳
现在我需要知道，在具有相同顶点和边数的加权无向图中，寻找具有最大代价的简单路径的问题是否是NP-完全的？输出：图G中最昂贵的路径的代价。你能提供任何参考的文章，我可以审查这一点。由衷地，
亚历克斯。
浏览 3提问于2010-12-29得票数 2
回答已采纳
3回答
LCS算法(示例)
、、、
有一个动态规划算法来寻找两个序列的最长公共子序列。如何找到两个序列X和Y的LCS算法(正确性测试)
(b) X = BFAAAABBBBBJPRSTY Y=ABCDEFGHIJKLMNOPRS
浏览 1提问于2011-11-24得票数 2
我们可以用动态规划(DP)求出两个字符串的最长公共子序列(LCS)。通过DP表跟踪，我们可以得到LCS。但是，如果存在多个LCS，我们如何获取所有LCS？
浏览 2提问于2013-05-31得票数 3
云服务器
ICP备案
云直播
对象存储
实时音视频
腾讯云开发者
