1回答
最小乘积生成树
、、、、
在minimum product spanning tree问题中，树的代价是树中所有边权的乘积，而不是权值之和。你可以假设所有的边都有正的权重。我想得到以下问题的答案。(1)给出了最小乘积生成树与最小权生成树不同的图。
(2)给出了一种计算最小乘积生成树的有效算法。(提示:考虑对数)。
浏览 6提问于2013-04-21得票数 0
给定一个无向连通图G，G中的所有边都有未知的代价，但已知每个边的每个代价的区间，例如边e的代价在闭区间i，j中，其中i和j是实数。我还得到了一个G的生成树，名为T。我需要创建一个算法来检查T是否是G的最小生成树。我试着将这个问题连接到网络流，但我无法找到解决方案。有什么提示可以解决这样的问题吗？
浏览 1提问于2018-12-31得票数 1
回答已采纳
1回答
我正在阅读关于最佳BST算法的文章。
更具体地说，我们从最小成本树开始，每个树都包含一个键，然后用2，3，，构造最小成本树。。。，n个连续键。因此，我们不考虑n个节点的所有可能的树，而是只考虑n(最小代价)树，每个节点有1个节点，n -1 (最小代价)树，每个节点有2个节点。。，具有n个节点的最小代价</e
浏览 5提问于2015-09-09得票数 1
2回答
我试图找到一个算法来解决以下问题，但有一个不同之处:边缘不明显。
给出了一个有效的算法来检验在G中加入新的边后，T是否仍然是最小代价生成树。
浏览 2提问于2016-01-08得票数 0
注:C‘为logc，基数为17用线性函数对每条边的代价进行变换，很容易证明结论是正确的。
我没有考虑具体的算法，比如贪婪的算法。我只考虑了变换后两棵树的权重之和之间的关系。如果G生成的一棵树有两个边a和b，由G生成的另一棵树有c和d，a+b<c+d，第一棵树是MST，但在变换图G‘中，第二
浏览 8提问于2020-08-12得票数 2
回答已采纳
我正在尝试实现Kou的算法来识别R中的Steiner树。Kou的算法可以这样描述：
用G的最短路(有几条最短路，选择任意一条)代替T‘的每一条边，构造G的子图Gs。求Gs的最小生成树Ts (如果有
浏览 3提问于2015-05-06得票数 13
回答已采纳
2回答
例如，对于神经网络，我使用反向传播算法将代价函数最小化。在决策树中是否存在与基尼指数相当的东西？
CART算法总是说：“选择集A的分区，这使基尼指数最小化”，但是我怎么才能从数学上得到这个划分呢？
浏览 2提问于2019-08-30得票数 0
回答已采纳
1回答
我试图解决一个关于图的算法挑战，我已经将它分解为以下几个方面:给定一个无向生成树，找到2叶，使得它们之间的代价最小。现在我知道了Floyd算法，它可以找到具有时间复杂度O(N^3)和空间复杂度O(N^2)的所有对最短路径。问题的输入是N= 10^5，所以O(N^3)和O(N^2)太多了。
浏览 6提问于2017-03-07得票数 1
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树
浏览 1提问于2019-03-17得票数 0
回答已采纳
1回答
找出修复边的最小成本，这样所有节点都可以从彼此之间再次访问。n，表示节点总数的int。然后尝试做基本的联合查找算法，以最小的成本连接两个节点。首先，当unionFind被破坏时，我很难更新它。
浏览 2提问于2019-08-13得票数 1
回答已采纳
4回答
最小生成树子图
、、、、
目前我的想法使我相信，既然我们已经有了最小生成树G，那么既然我们在最小生成树中有子节点，就必须存在G‘。就目前情况而言，我有点不知所措。设(V，T)是G的最小生成树，G‘=(V’，E‘)是G的连通子图。(b)在什么条件下(V‘，E’∩T)是G‘的最小生成树？
浏览 2提问于2012-10-29得票数 4
回答已采纳
给出了在边集w:e -> Z上有权函数的二叉树T和一个正整数k，对于V (T)的子集T‘，代价( T’)定义为边(u，v)的权值之和，使得u，v∈T‘.Give是求精确k顶点子集T’的最小代价(T‘)的算法
浏览 1提问于2022-04-07得票数 0
1回答
设T= (V，E)是一棵具有已知代价的|V|顶点和|E| = |V-1|边树。构造了一个最小权完全图G= (V，E')，它的最小生成树为T。
跨T作为其唯一MST的最小权重完整图G如下：
我试图找到一个生成这个图的(多项式时间)算法。证明:假设相反；我们可以用另一条边替换(
浏览 2提问于2015-01-05得票数 3
回答已采纳
所以刚刚学习了Kruskals的最小生成树算法。所以我的理解是：
它初始化一个包含所有顶点V的不相交集数据结构。Kruskals算法在用计数排序(如果权重允许的话)按权重对边进行排序之后，如果节点u和v不是不相交集中同一集的一部分，则迭代排序边，并将边(u，v)添加到最小生成树中，如果节点u和v不是不相交集中同一集的一部分当迭代我们的边(u，v)时，我们可以在数组中的O(1)时间内查找它们的索引，如果这些数组值中的任一值为0，那么我们将它们都设置为1，
浏览 1提问于2018-10-12得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
