腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
4
回答
如果最小
生成
树是贪婪
的
,为什么Kruskal
的
算法
会找到它呢?
graph-algorithm
、
greedy
如果最小
生成
树是贪婪
的
,为什么Kruskal
的
算法
会找到它呢?最小
生成
树不是一个全局优化问题吗?贪婪
的
意义不是在于你有可能找不到
最优
的
解决方案吗?那么,Kruskal如何在贪婪
的
情况下找到最小
生成
树呢?
浏览 2
提问于2016-12-10
得票数 5
2
回答
寻找具有最大最小度
的
生成
树
algorithm
、
graph
、
graph-algorithm
给定一个连通
的
无向
图
,寻找具有最小最大度
的
生成
树
的
问题已经得到了很好
的
研究(M.F¨urer,B.Rahvachari,“近似最小度
生成
树到
最优
度
的
1以内”,ACM-SIAM离散
算法
研讨会(SODA),这个问题是NP难
的
,文献中已经描述了一种近似
算法
。 我对以下问题感兴趣-给定一个连通无向
图
G= (V1,V2,E),找出所有内部节点(非叶子节点)上具有最大最小度<
浏览 1
提问于2013-03-18
得票数 3
1
回答
寻找最小
生成
路径
的
算法
?
graph
、
graph-algorithm
受这个漫画
的
启发 我知道有许多
算法
可以找到加权
图
的
最小
生成
树,但是我一直在努力寻找任何能够找到最小
生成
“路径”
的
算法
。对于漫画来说,如果我们根据每对关系对每条边进行加权,那么社会
最优
排列将是最小跨越“路径”,即一条跨越所有顶点
的
路径。有人能帮忙吗?
浏览 5
提问于2012-05-24
得票数 5
2
回答
快进和pddl:计算
的
解决方案是最好
的
吗?
artificial-intelligence
、
planning
、
pddl
我怎样才能确定由快进计划器计算出
的
计划是所有可能计划中最好
的
?!非常感谢!
浏览 5
提问于2013-09-22
得票数 0
1
回答
具有多根顶点
的
图
的
最小
生成
树
algorithm
、
graph
、
graph-algorithm
、
minimum-spanning-tree
、
directed-graph
我想知道是否有
算法
计算有向图中
的
最小
生成
树(最佳分支),给出所有这些根顶点之间
的
一组根顶点,但不只是一个根顶点和图中
的
所有其他顶点。给出一组根顶点1,4,6和
图
G,如下图所示:...the
算法
应该在同一张图片上返回类似绿色子
图
的
内容。 我想得到这样一个MST,它将提供给
算法
的
所有根顶点连接起来。我倾向于认为,该
算法
的
结果是
图
G
浏览 2
提问于2011-10-21
得票数 1
回答已采纳
2
回答
给定一组顶点,如何
生成
具有几乎极小边数
的
强连通有向
图
?
c++
、
search
、
graph
、
dijkstra
我试图对图形类
的
dijkstras
算法
执行测试。为了做到这一点,我
生成
了一个有几千个顶点
的
图
,然后通过随机添加数千条边使
图
连通,直到这个
图
被连接。问题是,我经常以一个几乎稠密
的
图
结束,因为我使用
的
是邻接列表表示,导致我
的
搜索
算法
非常慢。 问题:给定一组顶点V,如何
生成
一个强连通有向
图
,它
的
边比同一顶点上
的
稠密<
浏览 2
提问于2015-01-09
得票数 4
2
回答
从单个源到所有其他节点在
生成
树中寻找最短路径
的
最佳
算法
algorithm
、
graph
、
tree
、
shortest-path
、
spanning-tree
如果我知道给定
的
图
实际上是一棵
生成
树,即每一对顶点之间只有一条路径,那么如何才能找到从每个顶点到每个顶点
的
最短路径?我想要最理想
的
解决方案。我知道Dijkstra
的
算法
,但它非常复杂。我基本上想知道每个顶点从一个源
的
距离和路径。考虑到它是一棵
生成
树,那么它
的
最佳和
最优
解是什么?另外,如果
图
实际上是
生成
树,那么请告诉我是否有什么不同
的
方法可以找到所
浏览 6
提问于2014-12-11
得票数 0
回答已采纳
2
回答
路径
图
的
最大权无关集问题
algorithm
、
dynamic-programming
、
graph-theory
在使用类时,其中一个问题询问路径
图
的
最大权重独立集问题。a[i] = max(a[i - 1], a[i - 2] + w[i]) 如果一个顶点被排除在两个连续子问题
的
最优
解之外,那么它就被排除在
浏览 1
提问于2018-12-25
得票数 2
回答已采纳
1
回答
支配集贪婪逼近最坏情况示例
math
、
graph
、
graph-algorithm
、
discrete-mathematics
要找到无向
图
G
的
最小支配集,可以使用如下贪心
算法
:从一个空集D开始,直到D是一个支配集,添加一个具有最大未覆盖邻居数
的
顶点v。该
算法
一般不会找到
最优
解,它是一个ln(增量)-approximation。(如果增量是G中顶点
的
最大次数) 现在我正在寻找一个简单
的
例子,其中贪婪
算法
找不到
最优
解。我找到
的
唯一一个是集合覆盖问题
的
相关实例。(右侧
的
图片)将此
图</
浏览 6
提问于2012-06-04
得票数 4
回答已采纳
1
回答
改进
的
最小
生成
树
algorithm
、
shortest-path
、
minimum-spanning-tree
、
kruskals-algorithm
我必须实现一个
算法
,其中我们有一个现有的道路网络(节点通过路径连接,即无向
图
)。我们必须将所有的城市连接在一起,通常我会使用类似Kruskal
的
算法
来获得最小
生成
树。然而,我们不关心城市之间需要多长时间(可以假设边权重都是0或1或其他值),而是与建造道路(在两个顶点之间添加边)或销毁道路(删除两个顶点之间
的
边)相关
的
成本。这是我们必须考虑
的
唯一成本。我们
的
目标是每对城市只有一条路径连接。所有成本都是非负整数。 我有3x2d数组(我已经
浏览 8
提问于2021-05-31
得票数 2
1
回答
胡
的
算法
是否适用于一般单位长度
的
边DAG?
algorithm
、
graph-theory
、
scheduler
根据
的
说法,当
图
是树时,Hu
的
算法
是
最优
的
。对于一般单位长度
的
边缘DAG,它会失败吗?在这种情况下它不是
最优
的
原因是什么?有这样
的
失败
的
例子吗?
浏览 3
提问于2019-09-17
得票数 0
2
回答
一种证明没有贪婪
算法
来获得
最优
解
的
方法?
algorithm
、
greedy
我需要证明没有贪婪
的
算法
可以得到一个给定问题
的
最优
解。 我不清楚是否有一个问题必须满足
的
条件,从而存在一个贪婪
的
算法
来获得
最优
解。或者,如果有任何充分条件,该问题不能由贪婪
的
算法
解决。我说
的
正是贪婪
的
色彩:
浏览 4
提问于2015-04-30
得票数 3
回答已采纳
1
回答
图中
最优
簇数
的
求法
matlab
、
graph
、
cluster-analysis
我使用matlab中
的
对称非负矩阵因式分解
算法
(SYMNMF)对
图
G进行聚类。输入如下: 簇间运行
的
边数尽可能少。给出
图
的
邻接矩阵,有什么
算法
可以用来找出
最优
的
聚类数吗?
浏览 1
提问于2015-04-17
得票数 0
1
回答
将一个点插入到与现有点最大距离
的
有限2D区域中
geometry
、
2d
、
point
、
insertion
在有限
的
2D空间区域中,我有一组2D点(假设是一个世界对齐
的
矩形,以使事情变得简单)。怎样才能非常有效地将一个新
的
点插入到与其新
的
近邻有较大距离
的
集合中?我可以慢慢建立一个Delaunay三角剖分,并将我
的
搜索限制在最大
的
三角形,但我希望有人有一个不同(更好)
的
想法。忘了提一下,每次都要考虑到前面的所有要点,我需要做几千次。我正在寻找一种
算法
,它不会随着我
的
点集
的
增长而减速到
浏览 2
提问于2009-11-08
得票数 1
回答已采纳
5
回答
什么是快速
算法
,可以找到一个短路径来遍历一个加权无向
图
的
每个节点至少一次?
python
、
search
、
artificial-intelligence
、
computer-science
、
heuristics
我
的
问题是:什么是快速
算法
来做到这一点?这是一个众所周知
的
问题吗?相当快--我们这里讨论
的
图</em
浏览 3
提问于2012-09-05
得票数 4
2
回答
为什么使用Dijkstra
算法
而不是最佳(最便宜)优先搜索?
algorithm
、
search
、
graph
、
dijkstra
从我到目前为止所读到
的
。在找到到达目标的最短路径方面,似乎更快,因为Dijkstra
的
算法
在遍历图形时必须放松所有节点。是什么让Dijkstra
的
算法
比Best First Search更好?
浏览 1
提问于2012-04-30
得票数 13
回答已采纳
2
回答
TSP问题
的
聚类
算法
c++
、
algorithm
、
visual-c++
我正在尝试解决一个有大约10,000个城市
的
非常大
的
TSP。为了使我
的
任务并行化,我想将这些城市划分为集群,并求解每个集群
的
TSP。我想要一种可以将我
的
城市划分为集群
的
方法(基于城市密度/集群中每个城市之间
的
邻近度)。 有谁知道做这件事
的
有效顺序吗?
浏览 1
提问于2012-12-14
得票数 1
回答已采纳
1
回答
什么是树分解中
的
分隔符概念?
tree
、
dynamic-programming
、
graph-theory
、
graph-algorithm
我正在尝试使用动态编程来理解树分解中
的
最大独立集问题。然而,在提出
的
算法
中,我无法获得“分隔符”
的
概念。有人能让我明白这一点吗。提前谢谢。
浏览 2
提问于2019-02-08
得票数 1
1
回答
图
搜索
算法
与
图
优化
算法
algorithm
、
optimization
、
graph
、
graph-theory
我已经看了很多
图
搜索,-both知情和不知情。我还研究并编写了一些优化问题,如爬山。我
的
问题是,如何将这两种
算法
联系起来?更清楚一点,这里有一个例子:假设我运行了一个像深度第一迭代深化这样
的
图形
算法
。我运行它
的
一个深度,得到一个目标节点,然后我再次运行在一个不同
的
深度,并找到一个目标节点,等等。现在,我有了一组可能
的
目标节点。我可以运行一个优化
算法
,如爬山,以找出哪一个是“
最优
”,根据不同
的
限制?
浏览 0
提问于2014-03-19
得票数 1
回答已采纳
2
回答
在完全图中寻找最大团
c++
、
algorithm
、
graph
、
clique
在一个有大约100个顶点
的
完美图(这个
图
有至少1个弦
的
奇数圈)中找到最大团
的
快速
算法
?? 还有比暴力更简单
的
方法吗,因为这是一个完美的
图
,应该有一个多项式时间
的
解。但是我找不到
算法
。贪婪着色在所有完美图中都能给出
最优
着色吗?
浏览 3
提问于2010-06-11
得票数 5
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
机器学习中的最优化算法总结
C+图进阶系列之 kruskal和Prim 算法_图向最小生成树的华丽转身
蚁群算法在水资源最优分配上的应用
PageRank、最小生成树:ML开发者应该了解的五种图算法
RBS:最优时间复杂度的single-target PPR算法
活动推荐
运营活动
广告
关闭
领券