1回答
最小乘积生成树
、、、、
在minimum product spanning tree问题中，树的代价是树中所有边权的乘积，而不是权值之和。你可以假设所有的边都有正的权重。我想得到以下问题的答案。(1)给出了最小乘积生成树与最小权生成树不同的图。
(2)给出了一种计算最小乘积生成树的有效算法。(提示:考虑对数)。
浏览 6提问于2013-04-21得票数 0
5回答
设计了一种有效的求最小大小反馈边缘集的算法.( a) 最小大小反馈边集：，由于图是不加权的，我们可以使用DFS。我们像往常一样从任何顶点开始DFS。当我们遇到一个后边缘，我们把它插入到一组反馈边。( b) 最小权反馈边集：由于图是加权的，所以我们可以使用Kruskal。但是Kruskal通常以最小重量的边缘
浏览 6提问于2012-05-29得票数 15
3回答
假设图中的所有边权都是从1到all的整数。你能让Prim的算法运行多快？如果边权值是某些常数W的1到W范围内的整数怎么办？我认为，由于Prim的算法是基于最小堆的实现，关于边的权重的知识将无助于加速这个过程。这是正确的吗？
浏览 0提问于2013-08-22得票数 2
1回答
最近，我对Prims/Kruskals算法进行了一些研究，以求图中的最小生成树，我对以下问题感兴趣：
设G是m个边的n个顶点上的无向图，使得每个边都有一个权重w(e)∈{1，2，3}.是否有算法在时间O(n+m)中求G的最小生成树？显然，您只需在图上运行Prims，就可以得到最小生成树，但不能在所需的时间内运行。我在想，我们可以先把每一条边的权重1加到树上，前提是它没有创建循环，就好像没有创建循环的权值1的边，那么它比权值2
浏览 7提问于2016-02-25得票数 0
1回答
我编写了一个DFS算法，它在图中的顶点之间找到一条路径，但希望优化它以返回包含最小边数的路径。路径：不能多次访问任何顶点。路径的总权重必须始终为正，包括路径末端顶点之前的任何顶点的路径。正权增加了可用的数量，负重消耗了他们的重量。
任何帮助都将不胜感激，谢谢！
浏览 3提问于2021-07-24得票数 2
回答已采纳
考虑到我们选择最负值的条件，Dijkstra会在所有负权的情况下工作吗？正规Dijkstra算法谢谢。
浏览 1提问于2020-10-24得票数 0
回答已采纳
2回答
我希望我的最小生成树算法基准与最好的。有人知道在哪里可以找到这些算法的C++实现吗？我大摇大摆地搜索了一下，却什么也没找到。如果这些算法是最好的，那么肯定有一个C++实现吗？--迄今最快的最小生成树算法是由David、Philip和Robert提出的，他发现了一种线性时间随机算法，它是Borůvka算法和反向删除算法的结合。函数α增长非常慢，因此在实际应用中，它可以被认为是一个不大于4的常数；因此，Chazelle的算法</e
浏览 2提问于2011-02-07得票数 11
回答已采纳
设G是一个无负圈的有向加权图，设计了一种算法，以求G中的最小权圈，其时间复杂度为O({x}V}^3)。我在这个问题上走在正确的轨道上吗？是否有可能修改弗洛伊德-沃尔算法，以求图中的最小</
浏览 1提问于2014-03-30得票数 3
回答已采纳
2回答
最小乘积生成树与最小和生成树不同吗？请解释(如果可能的话).I指的是，添加到最小值的边应该(？)也有最小的产品。
浏览 7提问于2013-10-14得票数 1
回答已采纳
1回答
改进Dijkstra算法
、、、、
给出了一个边权W介于0~ 1之间的有向图。从源到目标节点的路径代价是路径上从源到目标节点的边权的乘积。我想知道一种算法，它可以在多项式时间内或使用任何其他启发式方法找到最小代价路径。我认为沿着取边权的对数值(取模值)，然后对这个图应用dijkstra，但认为会有无法计算的精度问题。
还有其他更好的方法吗?或者我可以改进日志方法。
浏览 0提问于2016-11-07得票数 1
1回答
请给出几种无向图最小割集的确定性算法，以及它们的复杂度。(顺便说一句，我知道福特-富尔克森算法有一个无向版本，它为每个有向边缘增加了一个相反的平行边，有人能告诉我这个算法的时间复杂度是多少，或许可以给我更多的参考？)
谢谢。
浏览 7提问于2015-09-16得票数 2
我能用Stoer算法找到最大割集吗？比方说，我用Stoer算法否定了所有的边权值，并求出了这个图的最小割集，结果割集是原图的最大割集吗？添加了：在Stoer算法中，如果我选择最不紧密连接的顶点，并选择由相位割集返回的所有割集中最大的一个，那么它是全局最大割集吗？为什么或者为什么不？有什么例子吗？
浏览 1提问于2016-12-09得票数 0
3回答
我把我的问题简化为在图中找到最小生成树。但是我还想有一个约束，那就是每个顶点的总度不应该超过一定的常数因子。我该如何为我的问题建模？MST是不是走错了路？你知道有什么算法能帮我吗？还有一个问题:我的图有重复的边权值，所以有办法计算唯一的MST数吗？有算法可以做到这一点吗？编辑:所谓程度，我指的是连接顶点的边的总数。重复边权是指两个边具有相同的权重。
浏览 9提问于2009-05-20得票数 3
回答已采纳
1回答
认为该图适用于Dijkstra算法，即不存在负边权。我很难说服自己，Dijkstra的算法只有选择每一轮中的最小距离节点才能工作。什么能证明除了最小距离节点外，提取任何东西都会导致Dijkstra算法的失败？我正在寻找一个好的论点，但支持的例子是受欢迎的。
浏览 2提问于2017-04-05得票数 4
回答已采纳
3回答
我想找到一个循环，使得权值之和与对角向量(1，1，1，. 1)之间的角度最小化。有什么算法可以解决这类问题吗？
我很有信心一个Bellman型算法会给我一个很好的解决方案，但我不相信它会是最好的.
浏览 2提问于2014-03-31得票数 3
回答已采纳
2回答
我需要根据以下规则在两个给定节点之间找到简单的路径(没有循环)：
选择此路径，该路径在已找到路径的选定最小值中具有最大最小值。1具有更大的最小值。我想过Dijkstra或Bellman-Ford算法的修改，但挑战是，我们没有局部准则(最小距离)-我们无法找到最小的边缘重量，直到我们不能得到整个路径.解决这个问题的更好的方法是使用深度优先<e
浏览 5提问于2013-08-27得票数 1
回答已采纳
我有一个问题要问：据我所知，L1用于LASSO，L2用于岭回归，L1可以收缩到0，L2不能。我在文档中很少发现这个问题：
权值的L1正则化项。增加这个值将使模型更加保守。gamma def
浏览 5提问于2021-06-22得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
