腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
视频
沙龙
4
回答
如果最小生成树是贪婪的,为什么Kruskal的算法会找到它呢?
、
如果最小生成树是贪婪的,为什么Kruskal的算法会找到它呢?最小生成树不是一个全局优化问题吗?贪婪的意义不是在于你有可能找不到最优的解决方案吗?那么,Kruskal如何在贪婪的情况下找到最小生成树呢?
浏览 2
提问于2016-12-10
得票数 5
1
回答
找到MST的临界边缘:用改进的Prim算法可能吗?
、
、
、
当我找到一个“临界边缘”问题的解决方案时,我遇到了这个问题。我已经解决的最初(C++)问题是: 考虑一个图G=(V,E)。找出有多少边属于所有的 MST,有多少边不属于属于任何MST,有多少边属于一些MST,但不是全部。 让我们分别将“绿色”、“红色”和“黄色”称为上述3种情况下的边缘。 在进行我的研究之后,我偶然发现了,它解决了这个问题。一个将运行Kruskal算法的修改版本:如果两个或多个相同权重的边缘连接相同的组件,从而形成一个循环,那么所有这些都是黄色边缘,即可以包含在MST中的边缘(或不包括)。无可争辩地被选中的边缘是“绿色”的,在同一组件中创建循环的边缘是“红色”的。原来的
浏览 3
提问于2014-12-31
得票数 4
回答已采纳
1
回答
在有向图上寻找最小生成树
、
、
在有向图上找到最小生成树的算法是什么?我试着修改Prim的算法,但没能让它发挥作用。
浏览 3
提问于2014-02-24
得票数 31
2
回答
在Kruskal算法上使用贪婪策略解决的子问题是什么?
、
、
、
Kruskal算法在每次迭代时选择最小的边。虽然最终的目标是获得一个MST,但是解决的子问题是什么呢?是为了让森林有最小的重量,也是完全连接起来的吗?
浏览 5
提问于2020-07-03
得票数 1
回答已采纳
2
回答
图构件间的消去算法
、
、
首先,这是一个家庭作业问题。我有一个布尔矩阵,其中1s表示节点,相邻节点被认为是连通的。例如: 1 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 根据给出的定义,这个矩阵包含3个组。左上角一个,由5个节点组成,右上一个由1个节点组成,下一个由2个节点组成。 我需要做的是编写一个函数,该函数确定必须添加到矩阵中的节点数量最少,以便连接所有独立的组件。当可以从一个组中的任何节点创建路径到另一个节点时,两个组被连接。 所以,我所要求的是,在算法方面,有人把我推向正确的方向。我已经考虑过如何使用路径查找算法来找到两个组之间的最短路径,但我不确定如何对矩阵中的每个组这样做。
浏览 2
提问于2013-11-24
得票数 3
回答已采纳
2
回答
反作用的“差异”启发式算法背后的动机是什么?
、
我的问题是关于实现一个启发式O(n)算法。 对于这个算法问题,有一些通用的解决方案,即生成将一棵树转换为另一棵树的最小操作数。然而,的复杂度为O(n^3),其中n是树中的元素数。 为什么把一棵树转换成另一棵树的复杂性是O(n^3)? 如果我们在React中使用这一点,那么显示1000个元素将需要10亿个比较。这个太贵了。相反,React实现了基于两个假设的启发式O(n)算法: 两种不同类型的元素会产生不同的树。 开发人员可以提示哪些子元素可以在不同的呈现过程中通过关键支柱保持稳定。 您能详细说明React实现中的是什么吗? 假设在一般情况下是
浏览 4
提问于2019-05-13
得票数 2
回答已采纳
1
回答
对不同行进行排序
我一直被这个问题卡住了。有人能帮我解决这个问题吗? 我们得到了长度为l1,l2,...,ln的n个排序的人行。所有行都是按高度排序的。我们希望将所有行合并到一个排序行中。我们可以一次合并两行,这需要的时间与两行中的人数成比例。
浏览 0
提问于2015-10-12
得票数 2
1
回答
具有顶点权和边权的最小Spanninjg树
、
、
我在解决一个关于最小生成树的问题时遇到了一些麻烦。因此,图中的每个节点都是一个城市,并且有可能将两个节点连接在一起,这就是在两个城市之间修建一条道路的成本。问题基本上是告诉建设道路的最低成本,并让所有城市都以某种方式连接起来。我可以很容易地解决这个问题,使用Prim或kruskal算法来解决我最大问题的子问题。 现在,棘手的部分来了:每个城市(节点)可以有一个机场,每个机场都有一个时间成本(如果你决定建造它)。如果两个城市都有机场,你可以使用机场在两个城市之间旅行。现在,我必须计算建造道路和机场的最低成本,才能将所有城市连接起来,但我很难将与机场的连接与网络的其他部分联系起来。有人能帮我吗?也
浏览 3
提问于2017-04-18
得票数 4
回答已采纳
2
回答
TSP问题的聚类算法
、
、
我正在尝试解决一个有大约10,000个城市的非常大的TSP。为了使我的任务并行化,我想将这些城市划分为集群,并求解每个集群的TSP。 我想要一种可以将我的城市划分为集群的方法(基于城市密度/集群中每个城市之间的邻近度)。 有谁知道做这件事的有效顺序吗?
浏览 1
提问于2012-12-14
得票数 1
回答已采纳
1
回答
用什么算法来寻找最小生成森林?
、
、
、
正如维基百科所说: 最小生成林是其连通部分的最小生成树的结合。 为了找到最小生成树,我们可以使用例如、或。 我们可以用什么算法来寻找最小生成森林?
浏览 2
提问于2017-05-16
得票数 2
回答已采纳
3
回答
是否存在最小深度、生成树算法?
、
、
、
我目前正在优化电网规划,而MST没有很好地解决这个问题,因为如果到主电网的连接是一个辐射点,所有的电力都必须流经一条边,并将经过很长的“电气距离”到达每个耗电量点。 我正在研究的问题可能是最小化MW*distance或有功功率矩,但这会产生一个非线性问题。 所以我要找的是一个最小的生成树(不是最优的,只是最有效的),它最小化到树根的最大电气距离(通过图的距离)。 通过这种方式,我只是购买更长更细的电缆,这是一种更便宜的解决方案,较短,较厚的电缆。
浏览 1
提问于2013-06-27
得票数 6
2
回答
给定一个图,找到一个不是最小的生成树
、
、
、
如何找到图中不是最小的生成树(如果可能)
浏览 4
提问于2016-05-02
得票数 0
1
回答
证明了旅行商的2倍最优逼近算法并不能计算出最优解。
、
、
我有期末考试的复习,这道题让我特别困惑。本文给出了一个关于旅行商问题(TSP)的2倍最优逼近算法在三角不等式不成立的情况下不计算2倍最优解的例子。我试过一个三角形的例子,它的代价是1,1,10。然而,要得到哈密顿循环,所有三条边都要经过。这样,最优解将与此算法的近似解没有什么不同。我看错了吗?我希望能在这方面提供任何帮助。
浏览 1
提问于2015-05-09
得票数 2
回答已采纳
1
回答
查找森林中所有断开连接的树的MST
、
我有一个邻接矩阵格式的图,这个图有断开连接的树。我需要找到每个断开的树的MST。所以,我应该先为每棵树找到子图,然后在树上使用MST,还是有更好的方法/算法?
浏览 4
提问于2016-05-03
得票数 2
回答已采纳
2
回答
什么类型的算法是用来寻找路径的多路径,但一个起源?
、
我有一个有一个原点和多个目的地的图表。我试图找到一种方法来解释这个问题,找出要解决的正确算法类型。目标是尽可能少的路径到达所有的点,然而路径必须始终遵循网格点(即直角)。 例如: Origin: (0, 0) Point A: (3, 3) Point B: (3, 0) Point C: (1, 3) 从-> C到-> A的路径是很好的,因为到达A点只需要两个额外的段,因为它能够共享来自原产地-> C的路径。 有些事我想过了: 用尽所有路径选项到所有点,然后用尽所有组合。这显然是蛮力和最慢的方法。不是很好的比例。 创建一个从原点到点_的1的矩阵,然后执行矩阵加法以
浏览 0
提问于2018-11-13
得票数 1
回答已采纳
1
回答
什么情况下克鲁斯卡尔得不到最低限度?
、
、
由于Kruskal算法是贪婪的方法,这意味着我们有时可能得不到真正的最小路径。 但是谁能给出一个例子,证明这个算法没有得到最小值? 我不是在寻找复杂性,只是需要一个真正没有得到最优解决方案的案例。 谢谢
浏览 7
提问于2019-03-21
得票数 0
6
回答
Kruskal和Prim算法的应用
、
、
谁能给出这两种算法的一些应用程序,它们可以用于哪里以及哪些应用程序?
浏览 3
提问于2011-09-06
得票数 12
回答已采纳
1
回答
使用生成树数据结构的实际应用程序
、
、
你们中有谁知道使用生成树数据结构的实际应用程序吗?
浏览 6
提问于2014-02-10
得票数 1
回答已采纳
1
回答
对于“洪水问题”有什么有效的算法吗?
、
、
我得找出堵车的降雨门槛。 所以,我必须打印降水的阈值来阻止交通。 (前) 3 3 0 1 2 1 2 3 0 2 6 产出:3 对于这个问题有什么好的算法或关键字吗? 谢谢
浏览 0
提问于2019-04-02
得票数 1
回答已采纳
1
回答
有没有计算最短树(而不是路径)的算法?
、
、
、
问候Overflowers 我有一个加权的有向图,我想要一个最低成本的树,它覆盖了根是图中特定给定节点的所有节点。我不知道是否也可以在每个节点上设置不同的最大分支,其中从该节点到其他节点(向外的边)的分支数量等于或小于该最大值? 那么,什么是最适合我开始阅读的算法呢?我希望它足够快:) 非常感谢!
浏览 2
提问于2011-05-28
得票数 2
回答已采纳
1
回答
如何给有向图的结点分配连续数?
、
有一个有很多节点的图,它们之间只有很少的边-问题是给节点分配编号,所以大多数节点是从i到i+1或以其他方式关闭。 我的问题是如何很好地打印图形数据,但像这样的算法几乎是每个编译器的一部分(中间代码只是一个图形,生成的目标代码获取内存位置)。 我认为这只是简单的深度优先搜索,但结果并不是那么好-它似乎可以很好地减少返回的链接数量,但它留下的链接往往很可怕(比如1 -> 500 -> 1)。 有更好的主意吗?
浏览 0
提问于2010-07-19
得票数 1
回答已采纳
1
回答
所有的启发式方法,如UPGMA,是否都能在重复分析中提供不同的结果?
、
、
、
我想知道是否所有的启发式方法,但具体地说,UPGMA或亲和传播可能会在重复分析中提供不同的结果,如果组没有高度定义的话。 我的意思是,由于启发式方法是实用的方法,不能确保最优,在每次重复分析中,如果没有明确的最优,我们可能会得到不同的解决方案,对吗? 因此,我想确认这可能发生在所有启发式方法中。 提前感谢
浏览 0
提问于2017-12-19
得票数 0
1
回答
最优压缩的最佳哈夫曼树
、
我正在编写一个霍夫曼字符串压缩器,我想有一个确认,我正在做我的树的最佳压缩。 我使用的是这种树: 而不是这棵树: 我认为超过10个单字符,是不可能在8位上压缩的。 第一张图片真的是最好的吗?
浏览 3
提问于2012-01-17
得票数 1
回答已采纳
1
回答
如何使用联合查找、minheap、Kruskal和排序算法来创建最小成本的生成树?(C++)
、
、
、
如果这个问题有点宽泛,我很抱歉,但我很难理解如何创建最小成本的生成树。这是用C++编写的,如果这很重要的话。 据我所知,您将使用Kruskal's来选择构建生成树的最低成本边。我的想法是将边缘读入一个小堆中,这样你就可以从顶部移除边缘,从而以最小的成本获得边缘。 到目前为止,我只能实现联合查找的minheap和set,我仍然不确定联合查找的目的以及用于创建生成树的排序算法。 如果有任何建议,我将非常感谢。 编辑:我不局限于联合查找、minheap、kruskals和排序算法,也不需要做任何事情。这些只是讲师建议的项目。
浏览 0
提问于2011-02-07
得票数 1
回答已采纳
1
回答
聚类最小生成树的数据集
、
、
、
最近我遇到了最小生成树的概念,发现它在聚类中有一个应用程序。我正在寻找一个真实的数据集(最好是干净的),它可以作为各种聚类算法的数据源。有一种信息表明,MST聚类在球面和非球面数据上工作得足够好。这就是为什么非球面数据集也被追求的原因。 我心目中的数据集应该包含地面真相信息(标签),因此各种标志的有效性可以通过与WSS不同的东西来衡量。
浏览 1
提问于2018-06-12
得票数 0
回答已采纳
1
回答
加权有向图的Prim算法
、
、
、
我在学习最小生成树。我研究了Prim关于加权有向图的算法。 算法简单 您有两个顶点集,已访问的和未访问的。 将所有边的距离设为无穷远 从未访问集中的任意顶点开始,并探索其边缘。 在所有边缘中,如果目标顶点没有被访问,并且如果边缘的权重小于目标顶点的距离,则使用该边缘的权重更新目标顶点的距离。 选择距离最小的未访问顶点,然后再做一次,直到所有顶点都被访问。 通过上述算法,我可以在所有的生成树中找到代价最小的生成树,即最小生成树。 但是我把它应用到下面的例子中,我认为它失败了。 请考虑以下示例 顶点是{v1,v2,v3,v4,v5}和带权的边。 (x,y):W
浏览 2
提问于2014-03-18
得票数 0
3
回答
霍夫曼编码基于贪婪的方法或动态编程
、
能否用动态规划来解决哈夫曼编码问题,有没有什么算法
浏览 2
提问于2013-05-13
得票数 3
回答已采纳
2
回答
全对最大流
、
、
给定有向加权图,如何求出所有顶点对之间的最大流(或最小边切)。 天真的方法是简单地为每对调用一个像Dinic这样的最大流算法,其复杂性是O((V^2)*E)。 因此,对于所有对,它都是O((V^4)*E)。 是否可以通过一些优化来降低O((V^3)*E)或O(V^3)的复杂性?
浏览 4
提问于2012-12-21
得票数 8
3
回答
图形算法: Prim
、
、
我想知道一个图G的任何最小生成树是否可以通过在这个图上执行Prim算法来提供? Prim算法给了我们所有可能的MST吗?
浏览 1
提问于2012-08-27
得票数 0
1
回答
在具有给定边的两权图中求MST的权
、
、
、
我需要得到一个完整图的MST,其中所有的边都默认为权重3,而且我还得到了有权重1的边。 下面是一个例子 5 4 (N, M) 1 5 1 4 4 2 4 3 Resulting MST = 3 -> 5 -> 1 -> 4 -> 2 如果第一行有总节点数(N),则1权重边(M)的数量和以下所有行(M)都包含权重为1的边。 我试着构造一个完整的图并将给定边的权值更新为1,但是对于一个包含10^5 1权边的问题来说,空间复杂度太大了。
浏览 4
提问于2021-11-28
得票数 1
回答已采纳
3
回答
对科学工具包学习决策树中random_state的困惑
、
、
、
、
对random_state参数感到困惑,不确定为什么决策树训练需要一些随机性。我的想法是,(1)它与随机森林有关吗?(2)它与分裂训练测试数据集有关吗?如果是这样,为什么不直接使用训练测试拆分方法()? >>> from sklearn.datasets import load_iris >>> from sklearn.cross_validation import cross_val_score >>> from sklearn.tree import DecisionTreeClassifier >>> clf =
浏览 3
提问于2016-08-26
得票数 32
回答已采纳
2
回答
图权重的最小和,其中每个节点都是连接的(如网络)
我可以使用什么算法来解决这样的问题: 有一个图的正权重,我想知道每个节点连接的权重的最小和(像网络一样连接,其中每个节点是一个eg。网络设备)。 在这个网络中,每个节点都可以通过其他节点以某种方式与其他节点相连。但输入图中的所有节点都必须位于网络中。
浏览 1
提问于2010-04-26
得票数 0
回答已采纳
1
回答
一种用于遍历图的线性时间算法
、
、
、
我正在阅读一本算法教科书,以提高我的算法技能,但我在这个问题上完全被困住了,这让我很困扰。我认为底层的数据结构是一个图表,但我甚至不知道从哪里开始这个问题。有人能给点见解吗?谢谢 给出了一个地形图,该地形图提供了任意两个相邻城市和两个城市a和b之间的直接道路上的最大高度。提出了一个线性时间算法,该算法可以找到从s到t的路径,从而使最大高度最小化。道路可以双向通行。
浏览 3
提问于2013-10-01
得票数 1
2
回答
最优子结构与贪婪选择
、
我读到了一个贪婪问题的两个性质,我试图理解两者之间的区别:- 最优子结构性质:最优整体解包含其所有子问题的最优解。 贪婪选择性质:贪婪地选择局部最优选择可以得到全局最优解。 这两个不是等价物吗?这两者似乎是一回事,你能给我一个例子吗,最优的子结构是满意的,但贪婪的选择不是?并举例说明当满足贪婪选择而不满足最优子结构时?
浏览 3
提问于2014-10-18
得票数 2
回答已采纳
3
回答
查找连接所有节点的最短路径集
、
、
、
、
我在二维坐标空间中有一组点。 我想找出一组总长度最短的连接它们的路径。(启发式解决方案ok,不需要精确。) 这可能听起来像旅行推销员的问题,但它是不同的。我不是在寻找一个周期,它将访问每个点一次并且只有一次。我只需要每个点连接到至少一个其他点,这样集合中的所有点至少间接地彼此连接,所选连接的长度之和将被最小化。因此,它应该是非循环的,以最小化连接长度的总和。 简单的最近邻居算法(即,将每个点连接到尚未连接到它的最近邻居)不起作用,因为彼此相距较远的小集群最终将被隔离,而您最终将最终创建循环。
浏览 6
提问于2020-01-31
得票数 1
1
回答
在加权图中将循环图转换为无圈图
、
、
、
、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图,这样被移除的边的权重之和就会最小化。输出将是移除的边。 我的想法是:由于一个连通的非循环图是一棵树,我可以简单地获取最大的n-1边,然后删除所有其他边。但是,这并不总是正确的。它可能导致不连通的图。 然后,我想到了使用dfs。我知道如何使用dfs检测图是否有圈,但我不知道如何检测涉及到的所有边,以及如何将其转换为非循环图。任何帮助(代码/伪代码/文字中的算法)都将不胜感激。谢谢..。
浏览 36
提问于2019-06-12
得票数 1
回答已采纳
1
回答
起始位置和一组所需节点之间的最小生成树
、
、
、
、
我试图确定最优的搜索案例,以与我编写的搜索算法进行比较。 我有一组标记为“必需”的节点和一个标记为“开始”的节点,其余的都标记为“可选”。如果我第一个展开的节点是"start“节点,那么我希望找到需要展开的节点的最佳数目,以发现所有所需的节点。 我相信我正在寻找的是最小生成树,但修剪了所有不以“必需”节点结尾的分支。这是吗 如果我的图是未加权的,那么Steiner树和最小生成树的大小是否相同? 如果我能说出这棵树的大小呢?例如,(最小生成树的大小=平均最短路径**所需节点的大小……我不认为这是真的,但如果能够根据连通性或其他什么来计算平均值会更好)。 几个注意事项:
浏览 2
提问于2012-04-07
得票数 4
回答已采纳
2
回答
如何求图中最小生成树的总数?
、
、
我不想找到所有的最小生成树,但是我想知道其中有多少树,下面是我考虑过的方法: 用prim或kruskal算法求出最小生成树,然后求出所有生成树的权值,当最小生成树的权重等于最小生成树的权重时,增加运行计数器。 我找不到任何方法来求出所有生成树的权重,而且生成树的数目也可能很大,所以这种方法可能不适合这个问题。由于最小生成树的数目是指数的,将它们计算起来不是一个好主意。 所有的重量都是正数。 我们还可以假设,在图中不会出现超过三次的权重。 顶点的数目将小于或等于40,000。 边数将小于或等于100,000。 图中只有一个最小生成树,其中顶点的权重是不同的。我
浏览 4
提问于2012-12-13
得票数 9
回答已采纳
1
回答
Dijkstra与MST的关系
、
、
当我看到时,这个问题突然浮现在我的脑海中。为了简单起见,我们可以将讨论限制在无向、加权、连通图上。显然,如果从图中选择任意节点作为源,Dijkstra不能保证生成MST。然而,它是否保证在一个无向、加权、连通图中必须存在一个节点,如果我们选择它作为源并应用Dijkstra的算法,它将为该图生成一个MST?也许你可以给出一个证据或者一个反例。谢谢!
浏览 1
提问于2020-12-16
得票数 2
回答已采纳
3
回答
在sklearn的RandomForestClassifier偏差中设置一个随机状态是您的模型吗?
、
、
、
我已经训练了一个随机森林模型,并且使用了一致的random_state值。在我的培训、测试和验证数据集(所有数据都在.98左右)中,我也获得了很好的准确性。虽然少数类仅占数据集的10%。 如果您感兴趣,这里有一些代码: model = RandomForestClassifier(n_jobs=-1, oob_score=True, random_state=310, n_estimators=300) model.fit(subset, train.iloc[:,-1]) 考虑到训练、验证和测试数据集的良好精度分数,random_state是否会影响我的模型的泛化?
浏览 1
提问于2019-03-08
得票数 1
回答已采纳
2
回答
用Kruskal算法求图的最小生成树
、
、
、
、
,我需要用Prim的和Kruskal的算法找到G的最小生成树。 我用Prim算法找到了最小生成树。。 我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频,但我最终得到了与Prim算法相同的图形。 有人能告诉我如何用Kruskal算法求图的最小生成树吗?
浏览 1
提问于2019-03-17
得票数 0
回答已采纳
2
回答
基于Dijkstra算法的最小生成树
、
、
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径,而是寻找最小生成树。 为此,我做了一些表格,并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此,目的不是找到从A到K的最佳路径,而是MST。
浏览 58
提问于2019-02-05
得票数 2
2
回答
无向图:具有尽可能少的红色边的最小生成树
、
我不确定如何处理这个问题。 给定一个无向图,每条边的颜色不是红色就是蓝色。如何在时间复杂度(O(m + n) log )内找到包含尽可能少红色边的最小生成树。其中m个顶点和n个是边。 任何帮助都将不胜感激。
浏览 1
提问于2015-12-07
得票数 1
2
回答
给定图G,分而治之的方法能找到最小生成树吗?
、
、
如果给定连通图G,则将图拆分为Ga和Gb。如果找到Ga和Gb的最小生成树(分别称为Xa和Xb ),那么用最小加权边将Xa连接到Xb是否仍然形成生成树?生成树是最小生成树吗? 到目前为止这是我的逻辑。我相信将Xa与Xb连接起来至少会形成一棵生成树,这几乎是定义上的。(如果有反例(尽管这会有帮助),但我不认为它总是会形成最小生成树,因为根据图的结构,您可能可以从Xa或Xb中移除边缘,然后添加连接它们的边缘,并且仍然有一棵树。在同一权重的多个边缘将Xa和Xb连接在不同的顶点的情况下,可能会出现这种情况。 到目前为止,我的逻辑正确吗?
浏览 3
提问于2012-04-01
得票数 1
回答已采纳
1
回答
怎样才能很容易地拆分出一条旅行推销员之路呢?(近似)
、
、
假设我们有一个问题,其中有几个城市之间的路径成本(在时间上)是可变的,并且我们有两个推销员,他们两个之间必须至少访问每个城市一次。 现在,假设我们有一个算法,给定一个推销员和一组城市,可以为这个推销员设计一条最优路径。我们想要做的是以这样的方式划分城市,将一套分配给第一个推销员,另一套分配给另一名推销员,这样我们就可以得到一个解决方案,使总时间尽可能地短。做这件事的好方法是什么?我们想要一个很好的解决方案,但不一定是最优的。 我的想法是,我们可以使用某种启发式方法来确定给定的拆分是好是坏,但有很多城市,所以选择拆分是困难的。我不完全确定该怎么做。 需要澄清的是:每个城市必须至少有一个推销员到访
浏览 1
提问于2014-05-01
得票数 0
1
回答
最小化特定节点的度的最小生成树
、
、
、
我们如何找到最小化节点v度的最小生成树(在所有最小生成树中)? 修改Kruskal算法,如果有几条边具有相同的权重,我们会选择不接触v的那条边来解决问题吗?
浏览 14
提问于2017-02-22
得票数 2
2
回答
用Java动态规划求解TSP问题
、
、
、
我在网上找到了许多资源,讨论这个和相关的主题,但我还没有找到任何真正帮助我知道从哪里开始实现这个解决方案的东西。 为了澄清,从城市0开始,我需要每隔一个城市访问一次,然后返回到城市0。 我有一个像这样的数组: 0 1129 1417 1240 1951 1129 0 1100 800 2237 1417 1100 0 1890 3046 1240 800 1890 0 1558 1951 2237 3046 1558 0 除了找到最佳路线外,我还需要找到沿途的最佳部分路线。例如,我从长度为2的路由开始,最后打印出如下内容: S = {0,1} C({0,1},
浏览 2
提问于2015-10-30
得票数 2
1
回答
prims算法与boruvka算法的区别
、
、
、
我正在学习MST算法。我很好奇想要找到prims和boruvka算法之间的关键区别,但在线资源除了它们的实现和算法之外,没有太多关于它们的内容。如果有人能解释,那将是很大的帮助。谢谢!
浏览 4
提问于2021-07-18
得票数 2
3
回答
边权值给定时求最小生成树的算法
、
、
、
、
最近有人问我是否可以找到一个算法来计算给定图的最小成本生成树,其中生成树的总成本是边成本的乘积,而不是它们的总和。 有几种算法可以计算正则最小生成树,但我不确定如何针对上面提到的情况调整它们。有什么想法吗? 谢谢。
浏览 2
提问于2010-11-19
得票数 3
回答已采纳
2
回答
如何有效地从图中生成所有可能的生成树
、
、
、
首先,请注意,这个问题是而不是询问MST,而只是all possible spanning trees。 所以这是,而不是,与或一样 我只需要从一个图表中生成所有可能的spanning trees。 我认为蛮力的方式是直接的: 假设我们有V节点和E边。 获取图的所有边 将V-1的所有可能组合从E边缘提取出来。 从组合中筛选出non-spanning-tree (对于生成树,一组V-1边缘中的所有节点都应该出现一次) 但是我觉得面对大图的时候太慢了。 我们有更好的方法吗?
浏览 4
提问于2014-03-02
得票数 9
回答已采纳
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最小生成树算法?详述最小生成树算法的原理?用C语言实现最小生成树算法。内附完整代码。
最小生成树-克鲁斯卡尔算法-Kruskal算法
PageRank、最小生成树:ML开发者应该了解的五种图算法
C+图进阶系列之 kruskal和Prim 算法_图向最小生成树的华丽转身
每天一个ml模型——决策树
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券