腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
DAG中的最小路径
覆盖
、
、
、
我想知道是否存在一个有效的
算法
来计算有向无环图的最小路径
覆盖
。请不要将最小“路径
覆盖
”与“顶点不相交的路径
覆盖
”混淆。对于后者,我知道一个有效的
算法
,使用相应的二部图的
最大
匹配。当每个顶点可以被多次访问时,是否可以放松相同的
算法
以获得路径
覆盖
的答案?
浏览 4
提问于2013-06-10
得票数 3
回答已采纳
2
回答
迭代
最大
匹配
、
、
、
在中是一组两两顶点不相交的边,如果它
覆盖
了图中
最大
的顶点数,则它是
最大
的。有一些有效的
算法
来查找这样的匹配,以及实现(例如,在C++中的一个例子)。但是,在一个任意图中可以有几个
最大
匹配;是否有任何
算法
实现允许您列出所有这些
算法
?我更喜欢C++实现,但其他语言也不错。
浏览 10
提问于2011-10-27
得票数 4
2
回答
边缘团
覆盖
算法
、
、
、
、
我试图编写一个
算法
来计算输入图(无向和无自循环)的边团
覆盖
数(
覆盖
所有边的最小团数)。我的想法是 有谁知道一个更好的方法吗?有标准的
算法
吗?令我惊讶的是,我找不到任何这样的
算法
。
浏览 2
提问于2018-03-06
得票数 3
回答已采纳
1
回答
支配集贪婪逼近最坏情况示例
、
、
、
要找到无向图G的最小支配集,可以使用如下贪心
算法
:从一个空集D开始,直到D是一个支配集,添加一个具有
最大
未
覆盖
邻居数的顶点v。该
算法
一般不会找到最优解,它是一个ln(增量)-approximation。(如果增量是G中顶点的
最大
次数)有人知道一个小例子吗? 提前感谢
浏览 6
提问于2012-06-04
得票数 4
回答已采纳
1
回答
最大
覆盖
不相交区间
、
、
、
假设您有k<=10^5间隔a_i,b_i \in ,并且您需要选择一组彼此不相交的间隔,以便它们的联合是
最大
的。不是
最大
数量的不相交间隔,但工会必须
覆盖
最多。 不能尝试所有可能的子集2^k不可行。用a_i (区间
覆盖
算法
)和b_i (
最大
不相交区间
算法
)排序的贪婪方法不能确定是否存在动态程序解。
浏览 3
提问于2017-03-12
得票数 3
回答已采纳
2
回答
用pythonic方法求多个集合交集的
最大
长度?
、
我想要得到每个子集相交的
最大
长度的子集的总元素,我想知道如何以一种简单的pythonic方式编码?如果有人能帮上忙,非常感谢。elements.intersection(e) for e in subsets)) 很抱歉造成混乱,我正在尝试实现贪婪
算法
来解决
最大
覆盖
率问题对于每一步,在排除当前选择的子集之后,我希望找到
覆盖
最多未
覆盖
元素的子集。子集的结果应该
浏览 3
提问于2018-01-29
得票数 0
1
回答
最大
加权段
覆盖
算法
、
这是我想过的
算法
问题,但我想不出一个简单的解决办法。给定n段[l_i, r_i],其中所有l_i, r_i in [1,M]。每个段都有一个值v_i,如果您可以选择任意数量的非重叠段,那么可以得到的
最大
值是多少?
浏览 4
提问于2017-06-16
得票数 1
1
回答
计算占用网格中的
最大
覆盖
路径
、
、
、
我正在实现一个基本的机器人,它使用SLAM
算法
生成其环境的占用网格。它是非常简单的,没有概率方面,只是一个枚举来表示空的,占有的,未探索的,不可触及的等等。我想知道是否有一个众所周知的
算法
可以找到访问所有网格单元所需的最短路径(这是一个真空吸尘器!)。这是旅行推销员的问题吗?
浏览 0
提问于2012-03-27
得票数 2
回答已采纳
4
回答
如何近似n个矩形的多边形?
、
、
是否有任何
算法
可以近似给定的多边形与n个不重叠的矩形给出
最大
的
覆盖
范围?所谓
最大
覆盖
,我的意思是,矩形面积之和是
最大
的。矩形不一定大小相等。编辑2我忘记提到这些矩形是正交矩形,即与轴对齐。
浏览 8
提问于2012-06-06
得票数 7
1
回答
二部图的最小顶点
覆盖
、
、
通过查看图表,我知道最小顶点
覆盖
是{v1,v2,u3}和{v1,u2,u3},但我不确定如何使用二部匹配/顶点
覆盖
算法
来找出这一点。和图的
最大
匹配是边(v1,u1)、(v2,u2)和(v3,u3)。给定
最大
匹配,下一步是从一个不饱和的顶点开始(该顶点不是匹配边的端点之一) 但是在这种情况下,所有的顶点都是饱和的,所以我不知道如何继续。
浏览 1
提问于2014-04-28
得票数 0
1
回答
整数线性规划与线性规划的界原理
、
、
目前,我正在学习近似
算法
。当我通过LP学习顶点
覆盖
时,我遇到了一个叫做边界原则的原则。它是这样的:用于LP松弛的
最大
ILP≤
最大
值用于LP松弛的ILP≥MIN 我不明白为什么“
最大
为ILP,≤
最大
值用于LP松弛”和"MIN为ILP≥MIN用于LP松弛“。
浏览 6
提问于2013-11-12
得票数 0
回答已采纳
2
回答
用圆
覆盖
不规则区域
、
然而,我想
最大
限度地扩大地图的
覆盖
面。我假设这可以通过随机生成圆圈的中心来实现,并旨在
最大
化
覆盖
范围。如果我可以进一步
最大
化使用的面积,我不介意区域重叠一点 有没有关于如何解决这个问题的建议,或者是否有任何
算法
可以为我做到这一点?
浏览 52
提问于2017-07-31
得票数 1
回答已采纳
1
回答
遗传
算法
在无线传感器网络中的应用
、
、
我想在无线传感器网络中实现遗传
算法
来优化传感器在一个区域内的部署,这样最小的传感器
覆盖
最大
的目标,任何人都可以以任何方式帮助,谢谢。
浏览 13
提问于2021-04-24
得票数 0
1
回答
在描述路由时使用了哪些
算法
?
、
、
、
在这个中,作者问到地图上从A点到B点的方向计算
算法
是什么,答案是 但我也对命名不同替代方案所使用的
算法
感到好奇。他们是不是选择了
覆盖
距离
最大
的那条路?
浏览 0
提问于2016-09-25
得票数 1
1
回答
在R*树中插入新树叶
、
、
、
、
R*树的插入
算法
有哪些步骤? 注意:我希望能够通过插入来构建树。它总是给我
最大
重叠和
最大
面积
覆盖
的垃圾树,无论我选择什么条件来选择最好的叶子(在树的每一层添加后测试最小重叠面积,在树的每一层上的最小扩展率等)。
浏览 2
提问于2012-12-07
得票数 3
回答已采纳
1
回答
Delaunay三角剖分中的重新定位点
、
、
、
、
我刚刚完成了Delaunay的增量翻转
算法
的实现。该
算法
具有时间复杂度O(N log N)。 我无法想象如何用有效的
算法
来
浏览 4
提问于2016-01-11
得票数 0
回答已采纳
2
回答
确定
最大
覆盖
面积的
算法
、
、
我正在寻找一种
算法
,我肯定已经研究过了,但我对图论还不太熟悉,甚至不知道要搜索的正确术语。在抽象中,我正在寻找一种
算法
来确定可达顶点x1、x2、xn和某个起始点之间的路由集,当每条边都有一个权重,而每条路径只能有给定的
最大
总重量x时。从更实际的角度来说,我有公路网,每个路段都有一个长度和
最大
的旅行速度。我需要确定从网络上的任何起点到某一时间范围内可以到达的区域。如果我能找到在这段时间内可以到达的最远点,那么我将使用凸包
算法
来确定区域(这对我的用例来说已经足够了)。 那么,我的问题是,我如何找到这些终点?我
浏览 3
提问于2015-07-09
得票数 3
回答已采纳
1
回答
查找
最大
顶点-不相交路径
覆盖
。
、
、
、
我们想要找到一个顶点不相交的路径
覆盖
,它具有
覆盖
中所有路径的
最大
权重和。 我知道这是NP问题。有没有解决这个问题的
算法
?还是有什么问题可以归结为这个问题呢?
浏览 1
提问于2016-11-18
得票数 0
回答已采纳
1
回答
有没有计算最短树(而不是路径)的
算法
?
、
、
、
问候Overflowers那么,什么是最适合我开始阅读的
算法
呢?我希望它足够快:) 非常感谢!
浏览 2
提问于2011-05-28
得票数 2
回答已采纳
1
回答
无连通有向图的
最大
子集的大小?
给定一个有向图,我如何才能找到一个
最大
的眩晕子集的大小,以至于它们中没有两个是通过有向路径连接的? 这个问题(或者解决它的
算法
)有一个共同的名称吗?(提示:“根据Dilworth定理,该问题实际上等价于计算传递闭包后的DAG上链
覆盖
的最小数目,从而可以将该问题归结为二分图上的
最大
匹配问题.)
浏览 1
提问于2012-10-19
得票数 1
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
算法:32.最小子串覆盖
算法:41.最大子数组
算法:42.最大子数组 II
机器学习期望最大算法:实例解析
经典算法(一)-最大子列和问题
热门
标签
更多标签
云服务器
ICP备案
实时音视频
对象存储
云直播
活动推荐
运营活动
广告
关闭
领券