ruby - 如何改进这种二分匹配解决方案？

Question

我正在处理 codefights，并正在尝试 Instacart 公司挑战中的 busyHolidays 挑战。

挑战提供了三个数组。 Shoppers 包含代表他们轮类开始和结束时间的字符串。 Orders 包含表示订单开始和结束时间的字符串，leadTime 包含表示完成工作所需分钟数的整数。

目标是确定订单是否可以与购物者匹配，以便每个购物者只有一个订单并且每个订单都有一个购物者。如果购物者可以在订购时间内开始并完成订单，则订单可能仅与购物者匹配。

我有一个通过 19/20 测试的解决方案，但由于我看不到最后一个测试，所以我不知道出了什么问题。我最初花了几天时间尝试学习像埃德蒙算法和匈牙利算法这样的算法，但我缺乏 CS 背景和数学弱点让我有点头疼，我似乎无法全神贯注于如何实际实现这些方法，所以我想出了一个解决方案，该解决方案涉及根据可能的连接数对图每一侧的每个节点进行加权。如果有人能帮我看看我的解决方案，或者指出它可能搞砸的地方，或者以一种对于没有接受过正规算法培训的人来说更容易理解的方式提出更标准的解决方案，我将不胜感激.提前致谢。

我会把代码放在要点中，因为它相当长

代码:https://gist.github.com/JakeTompkins/7e1afc4722fb828f26f8f6a964774a25

Answer 1

好吧，我看不出有任何理由认为您正在编写的算法实际上会起作用，所以关于您如何搞砸它的问题似乎并不相关。

您已正确地将此识别为分配问题的一个实例。更具体地说，这是“最大二分匹配”问题，Edmonds-Karp 算法是解决它的最简单方法 (https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm)

然而，这是一个寻找网络中最大流的算法，这是一个比简单的二分匹配更大的问题，而且这个算法的解释真的比你需要的要复杂得多。可以理解的是，您在从文献中实现这一点时遇到了一些麻烦，但实际上当问题简化为简单(未加权)二分匹配时，该算法很容易理解:

1. 进行初始分配
2. 尝试改进
3. 重复直到找不到更多改进。

对于二分匹配，“改进”总是具有相同的形式，这使得这个问题很容易解决。要找到改进，您必须遵循以下规则找到将未分配的购物者连接到未分配的订单的路径:

• 路径可以从任何购物者到他/她可以完成但没有完成的任何订单
• 路径只能从任何订单到在当前分配中完成它的购物者。

你使用面包优先搜索找到最短路径，这将对应于改变现有分配的最小数量的改进。

你找到的路径必然有奇数条边，偶数条边就是赋值。为了实现改进，您删除了这些分配并用奇数边替换它们。还有一个，这就是让它有所改进的原因。它看起来像这样:

PREVIOUS       PATH FOUND      IMPROVED ASSIGNMENT

    1              1                  1
                 /                  /
A              A                  A
  \              \     
    2              2                  2
                 /                  /
B              B                  B           
  \              \       
    3              3                  3
                 /                  /
C              C                  C