2回答
我想通过消除负圈来解决图的最小费用流问题。Goldberg和Tarjan在1989年发表了一篇以此为标题的论文，但我既找不到原始版本的副本，也找不到任何可能解释相同算法的更新的衍生作品。有没有人有描述这个算法的文档或者实现它的代码？
浏览 0提问于2011-03-27得票数 1
设G是一个无负圈的有向加权图，设计了一种算法，以求G中的最小权圈，其时间复杂度为O({x}V}^3)。
以上是我一直在努力的问题，作为我的课程工作的一部分。当我第一次读到它的时候，我立刻想到Floyd算法可以解决这个问题--主要是因为for运行在O({x}V}^3)的时间里，并且它同时适用于没有负圈的正负加权图。然而，我很快就记得F被设计用来寻找
浏览 1提问于2014-03-30得票数 3
回答已采纳
如何通过删除回路来最小化有向图的顶点数量？有没有可以在这里改编的算法？ 已经有一个关于删除图中的圈的问题，但我特别询问通过删除图中的圈来最小化顶点的数量。
浏览 20提问于2021-08-08得票数 0
1回答
在Dijkstra的算法中，松弛最多被称为m乘以(其中m=#边)。我试着找出一些具体的图例子，它确实是被执行了很多次。我知道，每次找到到给定节点的更便宜的路径时，都会出现松弛，但我不能真正“想象”这种情况。
浏览 1提问于2012-10-21得票数 1
是否有任何变种的福特-富尔克森，增加了额外的尺寸“重量”的边缘？
我的意思是，一些边比其他边更理想，虽然所有的可能性都在那里，但它将理想边优先于不太理想的边。
浏览 0提问于2013-05-27得票数 4
回答已采纳
MapReduce已被证明是以并行/分布式方式解决大数据集问题的强大工具。
一些组合优化问题，如最大网络流，最小费用网络流，多商品最小费用流，或最短距离路径/路径对问题，都能够扩展到非常大的规模。是否有人有成功/失败的经验来应用MapReduce来处理这些类型的问题？你能分享一下你的看法吗?用MapReduce来解决这类问题是个好主意还是坏主意？
浏览 0提问于2011-08-10得票数 2
1回答
考虑圈覆盖问题:给定一个图G，我们寻找一组C圈，使得V(G)的所有顶点都在C的至少一个圈中，且C中的圈数最小。我的任务是证明这个问题不允许绝对逼近，即不可能有一个算法H，对于该问题的所有情形I，H(I) <= OPT(I) + k，其中OPT(I)是i的最优值，k是一个大于或等于1的数。通常的技巧是证明如果存在该算法，我们
浏览 0提问于2014-06-16得票数 1
回答已采纳
1回答
我想找出加权有向图中由4条边构成的最短圈(最短=边的最小权和)。
我知道我可以使用弗洛伊德-沃尔算法来寻找图中的最短圈，如所描述的那样。但我不知道如何才能找到由四边构成的最短循环。
浏览 2提问于2015-04-11得票数 1
回答已采纳
1回答
具有最少轮数的网格上的生成树
、、、、
是否有一个多项式算法可以找到无向网格图的生成树，从而最小化树中的圈数？转弯是指有两条边连接到一个具有垂直方向的顶点。
关于近似算法的想法也可能有用。
浏览 6提问于2018-08-03得票数 2
1回答
是否有一种算法以有向图作为输入，并作为输出给出最小数目的边“中断”，以防止循环？例如，上面的图中的循环是：
电子- G，中断1圈我目前的方法是找出所有循环，按最常见的边缘分组，顺序desc，并在循环与以前的迭代还没有中断的情况下，按该顺序对它们进
浏览 4提问于2020-12-01得票数 3
设G= (V，E)是不含负圈的有向赋权图。如何修改福特bellman算法，使其在while循环的m+1次迭代后停止。M是最小路径中的最大弧数(根据权重而不是道路中拱门的数量确定的最小道路)
浏览 6提问于2020-07-03得票数 0
我希望尽量减少两项职能：b.源和目标之间的边沿总数。如果我只需要最小化(a)，我就会使用Dijkstra的算法；如果我只需要最小化(b)，我就会使用BFS。
但是，考虑到我必须将两者都最小化，我可以只使用Dijkstra的算法吗？换句话说，如果我从障碍中找到代价最小的路径，Dijkstra的
浏览 10提问于2022-09-02得票数 0
1回答
我喜欢在有向图(有时可能有圈)中找到最小生成树(甚至是森林)。解释的那个有一些错误。在Python中有没有这个算法的包/代码可以实际工作？
浏览 8提问于2016-08-04得票数 1
我知道在web.But上有很多计算最小围圈(SEC)的算法，我想知道为什么一个简单的算法不适用于它。我的想法是:我有一组点，我认为我可以用以下方法计算出它们最小的包围圆(SEC)：
这个能行吗？
浏览 3提问于2014-01-29得票数 0
例如，我如何通过Python中的ortools简单地找到(x-1)^2的最小值？
我读了ortools的文档，但我找不到它。我知道它不属于线性优化，但我在它的文档中找不到合适的类型。
浏览 159提问于2018-06-02得票数 2
回答已采纳
2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。解决这个问题的一种天真的方法是使用福特-贝尔曼或弗洛伊德-沃肖尔算法找到图的
浏览 5提问于2019-12-31得票数 5
1回答
可以使用Prim算法或Kruskal算法来寻找顶点/节点和边/链路的集合的最小生成树/图。我想要的是找到这个集合的最小生成图的算法，但是结果图只需要包括任意选择的节点，而不是所有节点。如果结果图包含比所需节点更多的节点，这是可以的。
这样的算法存在吗？也许在修改图以仅包括所需节点后，可以只使用Pri
浏览 1提问于2012-10-31得票数 7
回答已采纳
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
腾讯云开发者
