2回答
迭代最大匹配
、、、
在中是一组两两顶点不相交的边，如果它覆盖了图中最大的顶点数，则它是最大的。有一些有效的算法来查找这样的匹配，以及实现(例如，在C++中的一个例子)。但是，在一个任意图中可以有几个最大匹配；是否有任何算法实现允许您列出所有这些算法？我更喜欢C++实现，但其他语言也不错。
浏览 10提问于2011-10-27得票数 4
5回答
二部匹配
、、、、
如何用C或C++实现二部匹配算法(可能基于最大流算法)？(M，F) -->其中M表示男性的id，F表示女性的id。我需要找到匹配的最大数量，并显示匹配的情侣。喜欢:匹配: 1&3，2&5
我在一些书中读到过，我可以基于“网络中的最大流量”算法来解决这个问题，但除了“这个问题可以通过...算法</e
浏览 1提问于2009-05-18得票数 1
回答已采纳
1回答
求解最大权重二部b-匹配
、、、、
我的问题是关于最大重量B匹配问题。
二部匹配问题对二部图中的两组顶点。最大加权二部匹配 (MWM)被定义为匹配中边值之和有一个最大值的匹配。一种著名的MWM多项式时间算法是匈牙利算法。我感兴趣的是一个特殊的最大加权二部匹配问题，称为权值二部匹配问题。一个加权二分B匹配问题(WBM)寻求匹配顶点，使每个顶点与其容量b允许的顶点不<
浏览 0提问于2018-06-18得票数 5
1回答
我们必须找到图书馆员给每个成员最多两本书的方式，这样才能满足最大成员的要求。
引入两个新的顶点s(源)和t(目的)。将边从s引入到X中容量为2的所有成员，所有边E有容量1，新边Y到t有容量1，现在应用最大流算法寻找最大匹配。最大匹配是所需的解决方案。另一种方法是采用相同的算法，引入相同的边缘，但每条边的容量为1，现在寻找最大匹配。这种匹配将为最大的成员提供一
浏览 0提问于2012-09-06得票数 0
1回答
我用Dijkstra的算法编写了二部图的最小匈牙利算法，以求最大匹配的最小代价。然而，我想使用这样的算法来实现最大匈牙利算法，并且不知道只否定边缘是否正确，因为我不知道算法是否会处理它。我的实现是基于以下站点上的解释：
给定G=(AUB，E)，其思想是通过A中有不饱和节点边的人工起始点s对顶点进行标记，并运行Dijkstra算法对每个顶点进行标注，然后在每个顶点进行标记后，再用其初始权重减去边缘端点
浏览 11提问于2022-06-02得票数 1
回答已采纳
我想要找到最大的二部匹配，所以我将使用Flow Ford Fulkerson的算法，作为explained here。但是当我实现这个函数时，我只得到最大流的值，但我感兴趣的是流本身，这样我就可以找到匹配的流。 有人能帮我吗？ 我在R中使用了函数maxFlowFordFulkerson。
浏览 28提问于2019-10-03得票数 1
我看到可以用来解决这个问题的未加权版本，我知道这个问题也可以归结为一个LP问题(但是有指数型的约束)。有办法用多项式时间来解决吗？
浏览 5提问于2015-06-29得票数 6
回答已采纳
5回答
我正在寻找Python代码，以便在二部图中进行最大重量/最小成本匹配。我一直在使用NetworkX中的通用case最大权重匹配代码，但我发现它太慢了，无法满足我的需求。这可能是由于通用算法较慢的事实，以及NetworkX解决方案完全用Python语言实现的事实。理想情况下，我希望为包装了一些C/C++代码的二部匹配问题找到一些Python代码，但是现在，任何比NetworkX实现更快的代码都会很有帮助。
浏览 3提问于2010-12-13得票数 13
回答已采纳
2回答
我正在阅读扩充路径或Kuhn的算法，以便在未加权的二部图中找到最大匹配大小。我可以理解算法，但我在理解它通常实现的方式方面存在问题。这里有一个参考实现-- 。在每个阶段，我们应该尝试从左侧不匹配的顶点开始找到一条交替的路径。然而，在给定的<e
浏览 4提问于2014-08-27得票数 2
1回答
我读过很多文章，指出用最大流算法可以找到二部图的最大匹配。但是，我们从最大流得到的匹配可能不是最大的，或者匹配没有最大的边。来自Anti Laaksonen的竞争性方案编制手册的例子：
但是，如果我以不同的方式呈现这个图，那么现在的图形是：
然后，随着最大流量算法的推进，匹配结果为1-5，2-7。因为1简单地擦除了通向水槽的路径，但是如果它被移到边缘1-6，那么
浏览 3提问于2021-06-24得票数 1
回答已采纳
我正在学习如何使用networkx模块对二分图进行匹配。该模块中有两个函数给出了图的最大基数匹配：
PS:我的网络是1.11版
浏览 5提问于2017-05-21得票数 6
回答已采纳
1回答
我知道计算加权无向二分图(即赋值问题)的最大加权匹配的各种算法：我希望能找到具有多项复杂性的算法的指针或先前的转换，从而使图无向，这样我就可以应用上述任何算法。编辑：注意到匹配应该使边的权重最大化，这就是为什么有向边会产生不同的结果(A->
浏览 5提问于2013-02-12得票数 2
回答已采纳
1回答
图匹配算法
、、、
我一直在寻找用Python编写的图形匹配算法，但是我没有找到多少。
我目前正在尝试匹配两个不同的图形，它们是从两组不同的字符序列派生而来的。但是图没有相同的标签，因此，我需要通过比较拓扑和/或属性来返回节点映射的图形匹配算法。通过测试，我希望能最大限度地得到正确的匹配。我想测试其他选项，可能更标准，比如最大子图同构，或者找到两个图之间很好匹配的子图。如果图形编辑距离能够给出匹配，它也可能会有所帮助。问题是，
浏览 1提问于2018-05-06得票数 0
1回答
要求在给定的n乘n矩阵的不同行和列中找到一组具有最大可能和的n元素。在O(n^3)中，匈牙利算法可以得到最优解。然而，让我们考虑以下次优贪婪算法：
从第1步重复。实现这种算法的有效数据结构是什么？如果只要求O(n^2 log(n))对所有元素进行排序，那么它的时间复杂度可以是O(n^2)吗？
浏览 2提问于2016-03-17得票数 1
回答已采纳
1回答
我想要做的是找到完美匹配(当然，在没有完美匹配的情况下，尽可能接近完美匹配)，然后从所有这些匹配中，你可以在n个顶点中匹配k(其中k是最高可能的)，我想选择最高的总重量。因此，简单地说，我要说的是以下优先事项：
因为(非加权)最大匹配在大多数情况下是明确的，所以我想要选择边的权重之和最大的一个。我听说过福特-富尔克森算法。它是按照我描述的方式工作，还是需要其他算法？
浏览 3提问于2013-06-20得票数 6
我们有n个盒子和k个球，不同的colors.Each容器在it.We中很少有球，可以从每个盒子中选择最多一个球。示例：Box1 - A, DBox3 - D, ABox5 - D
浏览 0提问于2018-02-28得票数 1
回答已采纳
1回答
我建立了一个非加权二分图，并利用最大流算法实现了1的最大基数匹配。因为我的代理和任务列表是动态变化的。有没有办法不需要从头开始重建图并重新运行流算法？我可以使用相同的图形并以某种方式重新运行最大流算法吗？
浏览 2提问于2022-10-18得票数 0
1回答
一般图的最小代价+最大匹配算法
、、、、
现在，我希望通过它们各自的边缘将这些节点匹配在一起，其中只有一个约束：
我想做的是，找到最大匹配和总体最小成本的解决方案。0.5
Start: End Cost解决这一问题的办法如下：
指定Edge 1和Edge 3，因为这是匹配的最大</em
浏览 3提问于2016-11-10得票数 3
回答已采纳
1回答
初值二部图的快速最大匹配算法
、、、、
我正在处理一个二分匹配问题，在这个问题中，我需要求解一个初始图，然后求解多个不同节点被移除的图的变体。我们的目标是尽快解决所有的变体，所以我想使用从求解原始图中获得的信息来更快地解决这些变体。我有用单纯形法求解线性规划问题的经验，这得益于对解的初步猜测，但我对二分匹配算法还不熟悉。
是否有一种二部匹配算法，可以利用初始猜测来加快求解速度？
浏览 0提问于2019-07-26得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
