标签: hungarian-algorithm
匈牙利算法-从中选择0的最后一步，使得每一行和每一列仅选择一个
我正在尝试在Java中实现匈牙利算法。我有一个NxN成本矩阵。我正在逐步遵循本指南，并已达到第9步-
“通过选择一组零来选择匹配项，以便每一行或每一列都只有一个被选择。”
我已经有了0的矩阵。我试图弄清楚这一点，对我有用的唯一方法是蛮力方法。
我还想到选择遇到的第一个0，删除该列和行并重复；但是这种方法不起作用。
有什么技巧或方法吗？不太复杂的东西吗？任何建议将不胜感激。
谢谢
推荐指数
解决办法
查看次数
将学生与课程限制的课程相匹配(匈牙利语,最大流量,最小成本流程......)
我目前正在编写一个将学生映射到课程的程序.目前,我正在使用SAT-Solver,但我正在尝试实现一个多项式时间/非贪心算法,它解决了以下子问题:
- 有学生(50-150)
- 有科目(10-20),例如'数学','生物','艺术'
- 每个科目(至少一门)都有课程,例如'math-1','math-2','biology-1','art-1','art-2','art-3'
- 学生选择一些(固定的)科目(10-12),并且对于每个科目,学生必须被分配到现有的一门课程(如果可能的话).选择哪个课程'math-1'或'math-2'并不重要.
- 这些课程允许的学生人数最多(20-34)
- 每门课程都在一个固定的区块内(=时间段1到13)
- 学生可能不会被分配到同一区块的课程
我现在描述到目前为止我所做的事情.
(1)忽略课程 - 学生限制
我能够用匈牙利算法/二分匹配来解决这个问题.每个学生可以通过如下建模来单独计算:
- 左节点代表主题'数学','生物','艺术'(学生)
- 右节点表示块'1','2',....'13'
- 从"主题"到"阻止"的每个过程插入一条边
通过这种方式,学生被分配到课程的每个科目,而不参加同一区块的课程.但课程限制被忽略了.
(2)忽略学生的选定科目
我能够用max-flow-algorithm解决这个问题.对于每个学生,建模如下:
- 第1层:从源到每个学生,流量为13
- 第2层:从每个学生到他/她的个人区块,流量为1
- 第3层:从每个学生块到该块中的每个课程,流程为1
- 第4层:通过'max-student-limit'从每个球场到水槽
通过这种方式,学生选择任意课程,并且课程限制已满.但是他/她可能不幸并被分配到'数学-1','数学-2'和'数学-3'而无视主题'生物'和'艺术'.
(3)贪婪的匈牙利人
我的另一个想法是一次匹配一个学生与匈牙利算法并调整权重,以便"更多空课程"是首选.例如,可以建模:
- 左节点是学生的主题
- 右边节点是块
- 对于每个球场,插入一个边缘从主体到球场的块重量=自由座位数
然后计算最大权重匹配.
我真的很感激任何建议/帮助.
谢谢!
推荐指数
解决办法
查看次数
将 t-sne 的结果“捕捉”到常规网格 - 可扩展性问题
我正在尝试使用 t-sne 根据视觉相似性来排列图像，类似于表情符号的这个很酷的示例（来源）：
但 t-sne 的输出只是一个“点云”，而我的目标是在规则的、接近正方形的、密集的网格中显示图像。所以我需要以某种方式将 t-sne 的输出转换为网格上的 (x,y) 位置。
到目前为止，我已经遵循了这篇精彩博客文章中的建议：我将其表述为线性分配问题，以找到常规网格的最佳嵌入。我对结果很满意，例如：
我的问题是“捕捉到网格”阶段是一个巨大的瓶颈，我需要我的方法能够很好地扩展大量图像（10K）。为了解决线性分配问题，我使用 Jonker-Volgenant 算法的 Java 实现，其时间复杂度为 O(n^3)。因此，虽然 t-sne 是 nlogn 并且可以很好地扩展到 10K 图像，但对齐到规则网格的部分最多只能处理 2K 图像。
我认为潜在的解决方案：
- 从总共 10K 图像中随机采样 2K 图像
- 将 10K 图像分为 5 份并创建 5 个地图。这是有问题的，因为存在“先有鸡还是先有蛋”的问题，如何做好划分呢？
- 以准确性换取性能：大约在接近线性的时间内解决线性分配问题。我想尝试这个，但我找不到任何现有的实现可供我使用。
- 以不同的、更有效的方式实现“对齐网格”部分。
我正在使用 Java，但 cpp 中的解决方案也很好。我想我不是第一个尝试这个的人。有什么建议么？想法？
谢谢！
algorithm data-visualization time-complexity hungarian-algorithm
推荐指数
解决办法
查看次数
使用匈牙利算法解决分配问题的第二最佳解决方案
为了找到分配问题的最佳解决方案，可以轻松使用匈牙利算法。例如：
A | 3 4 2
B | 8 9 1
C | 7 9 5
当使用匈牙利算法时，你会变成：
A | 0 0 1
B | 5 5 0
C | 0 1 0
这意味着 A 被分配到“作业”2，B 被分配到作业 3，C 被分配到作业 1。但是，我想找到第二个最佳解决方案，这意味着我想要最佳解决方案，其成本严格大于最佳解决方案的成本。根据我的说法，我只需要找到最后一个矩阵中总和最小的分配，而不需要与最优分配相同。我可以通过在树中搜索（通过修剪）来做到这一点，但我担心复杂性（O(n!)）。有什么我不知道的有效方法吗？
我正在考虑一种搜索，其中我首先对行进行排序，然后首先贪婪地选择最低成本，假设大部分最低成本将弥补最小总和+修剪。但是假设匈牙利算法可以产生一个带有大量零的矩阵，那么复杂性又是可怕的......
推荐指数
解决办法
查看次数
最小化配对点的距离
我的问题如下:
Given a number of 2n points, I can calculate the distance between all points
and get a symmetrical matrix.
Can you create n pairs of points, so that the sum of the distance of all pairs is
minimal?
EDIT: Every point has to be in one of the pairs. Which means that
every point is only allowed to be in one pair.
我天真地试图使用匈牙利语算法,并希望它可以给我一个作业,以便作业是对称的.但这显然不起作用,因为我没有二分图.
搜索之后,我发现了稳定的室友问题,这似乎与我的问题类似,但不同的是,它只是试图找到一个匹配,但不是试图最小化某种距离.
有谁知道类似的问题甚至解决方案？我错过了什么？问题实际上看起来并不那么困难,但我无法想出最佳解决方案.
推荐指数
解决办法
查看次数
给定二维矩阵找到元素的最小总和，以便从每行和每列中选择一个元素？
找到 n*n 2D 矩阵的元素的最小总和，这样我必须从每一行和每列中选择一个且仅一个元素？例如
4 12
6 6
如果我4从 row 中选择，1我不能12从 row1 也从 column 中1选择，我只能从第 2 行第 2 列中选择 6。
所以，同样的最低金额是4 + 6 = 10其中6从第二行第二列
而不是6 + 12 = 18其中6是从第二行第一列
也4 + 12不允许，因为两者都来自同一行
我想到了蛮力，一旦我从行和列中选择元素，我就无法选择另一个，但这种方法是O(n!)
.
推荐指数
解决办法
查看次数
匈牙利算法：每个工人有多个工作
匈牙利算法是否有扩展功能，可以满足每个工人的多个工作分配要求？该算法以其最简单的形式将单个作业分配给单个工人。
我的应用程序是一个利润最大化的问题，有3个工人和180个工作岗位。我还将添加约束（每个工人最少分配50个工作）。
我已经使用Python中的mungres库成功实现了匈牙利算法，效果很好。我只是在努力寻找与每个工人的多个任务相关的文献。
https://pypi.python.org/pypi/munkres
https://zh.wikipedia.org/wiki/匈牙利语算法
https://zh.wikipedia.org/wiki/Generalized_assignment_problem
我尝试了注释中列出的标准numpy方法，但无法将其扩展到每个工作人员多个分配。如果我的矩阵是矩形（即3个工人和4个工作），则仅将前3个工作分配给工人。我还尝试添加虚拟变量以创建方矩阵，但是随后将作业分配给了这些虚拟工，而不是实际工
推荐指数
解决办法
查看次数
如何找到覆盖矩阵中所有零的最少行数？
I\xe2\x80\x99m 正在解决一个问题，我有一个nxn矩阵，我需要确定覆盖矩阵中所有零的最小行数（水平和垂直）。本质上，我想找到一种分配这些线路的最佳方法，以最大限度地减少总覆盖范围。
\n这是一个例子：
\n(0, 1, 0, 1, 1)\n(1, 1, 0, 1, 1)\n(1, 0, 0, 0, 1)\n(1, 1, 0, 1, 1)\n(1, 0, 0, 1, 0)\n解决方案必须是：
\n(x, x, x, x, x)\n(1, 1, x, 1, 1)\n(x, x, x, x, x)\n(1, 1, x, 1, 1)\n(x, x, x, x, x)\n在这种情况下，最小行数为 4。
\n有什么算法可以解决吗？
\n我尝试创建一个二维数组，在其中我可以看到一行中的零之和并且可以。
\n上面示例的数组：
\n{ \n [0, 1, 2, 5, 1, 1]\n [2, 0, 0, 0, 0, 0]\n [1, 0, 0, 0, …推荐指数
解决办法
查看次数