电影兑换券的推荐策略——二分图最优匹配算法

作者 ｜ 刘洁 ,一笔订单最多可使用所含电影票数目张兑换券。换而言之，用户选了几个座位，最多便能使用几张兑换券，兑换券有三个属性，分别是：,面值（元）：在不支持补差的情况下，票价小于等于面值才可以使用,固定支付金额（元）：满足兑换券的使用条件下，需要支付的钱。,补差（是 / 否）：如果支持补差，当票价大于面值时，还需要额外支付 （票价 - 面值）元,我们问题是：用户下了一笔订单，订单中有 x（根据业务场景，x <= 6）张电影票，y 张兑换券，从这 y 张兑换券中选择不超过 x 张兑换券，使得该笔订单的实际支付金额最少，如果有多种解决方案，那么根据以下优先级为用户推荐选券的方案：,优先级 1: 选择实际支付金额少的方案,优先级 2: 如果实际支付金额一致，则优先使用面值小的方案,对票价从大到小排序，让票价高的电影票优先选择，目的就是为了金额大的电影票优先使用限制条件少（既面值大）的兑换券，让券面值得到充分利用，每个票和券的组合都尽可能是最优解。,证明方法：举反例法,很不幸，很快就找出一个反例推翻了这个方案，反例如图所示,,枚举所有方案，从这所有方案中求出最优解，但是时间复杂度高达 C(y, x) * A(x, x) 也就是 O(n!)，若按照 1s 钟计算机能运行 10^8 次计算这样的标准，当 n = 13 的时候，需要超过 10s 才能得到答案，并且 n 每增加 1，时间就会扩大 n 倍。,km 算法是一种二分图最佳匹配算法，该算法主要用于解决一个经典的问题模型：完美婚姻问题。该问题的描述如下：n 个男生和 n 个女生相亲，第 i 个男生和第 j 个女生在一起的幸福值是 val(i, j)，如何让 n 个男生和 n 个女生完成一一配对，使得这个整体的总幸福值最大。我们的问题和完美婚姻问题模型有点相似，并且经过调研 km 算法时间复杂度是 n^3，km 算法有一个非常大的优点就是，他可以求出哪张券用于哪张电影票，适用于选座相关的业务场景。,我们把兑换券看成男生，电影票看成女生，用兑换券 j 购买电影票 i 的花费是 -w(i, j)去建图，如果兑换券 j 无法购买电影票 i，那么花费 w(i, j)设置为负无穷大，去构造一个二分图尝试求解，我们会遇到一些问题：,改造一：如何满足 km 算法的使用条件？,因为 km 算法是用于求解二分图的最佳匹配，也就是说二分图必须存在最佳匹配才能使用 km 算法求解。存在最佳匹配的必要条件是：必须两边的点相同，而且至少存在一种匹配方案使得所有的点都被匹配。所以我们需要补点和补边（补点和补边也是使用 km 算法的常见的技巧）。补边策略：将不存在的边，权重设为-inf。补点策略：新增 x 张兑换券，第 y + i 张兑换券跟第 i 张电影票连边，权值为电影票的原价，这样一来可以保障把无穷大的结果排除在外，二来不需要再额外再计算使用原价购买的情况。,,改造二：如何在多个解中求出满足优先级的解？,我们可以把所有兑换券按照面值由小到大排序，如果面值一致，那么按照入账时间从早到晚排序，如果入驻时间一致，按照过期时间由早到晚排序，简而言之，把优先级高的券放在前面。枚举数量 k，对前 k 个兑换券和所有的电影票加入 km 模型中，计算出最少花费，只有花费变得比之前更小才更新答案。这样可以保证取得最少花费的同时，还能满足优先级。还有一个好处是，如果后续 pm 对策略的优先级进行调整，那么我们可以更改最初的排序规则即可。但是时间复杂度此时变成了 n^4。,如图所示，当 k 等于 2 的时候取得最优解，k=3 的时候有可能匹配到优先级低的券。,,改造三、时间复杂度的优化,经过改造一和改造二的处理后，算法时间复杂度是：（x+y)^4 + y*logy（x 代表电影票张数，y 代表兑换券张数）,时间复杂度分析：经过补点操作后，二分图两边的点都是 x + y 个。因为 km 算法的时间复杂度是 n ^ 3 次方，n 为二分图单侧的点的个数。所以当前的时间复杂度是 （x+y)^3 。为了处理匹配的优先级问题，我们对优惠券进行了优先级排序，时间复杂度是y*logy，在运行 km 算法的时候，枚举了数量 k，所以总时间复杂度为（x+y)^4 + y*logy。,改造方法,具体步骤：对于每一张电影票，预处理出对于这张电影票优先级最高的 n（n 为当前的电影票张数）张，把这些兑换券去重，我们就能得到最多 nn 张兑换券。用着 nn 张兑换券代替原来的所有优惠券,收益：,当用户有 500 张兑换券（极限值时），能非常迅速的计算出最优策略，几乎无延迟。,二分图：又称作二部图，是图论中的一种特殊模型。设 G=(V,E)是一个无向图，如果顶点 V 可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A,j in B)，则称图 G 为一个二分图。,,匹配：在二分图中，一个「匹配」（matching）是一组边的集合，其中任意两条边都没有公共顶点。,,最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。,,最大权匹配：在一个带边权的二分图的所有匹配中，边权和最大的匹配，称为这个图的最大权匹配。,,完美匹配：如果一个二分图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。,,最佳匹配：二分图 G 的每条边都有权值，则权值和最大的完美匹配称为最佳匹配。,,可行顶标：给二分图每个节点 i 分配一个权值 l(i) ，对于所有边(u, v) 满足 w(u, v) <= l(u) + l(v) 的点权集合。如图所示，集合 { a: 30, b: 0, c: 40, d: 20, e: 90, f: 0 } 就是该二分图的一组可行顶标。一个二分图有无数个可行顶标。,,相等子图：对于某一组可行顶标，我们吧包含所有点但只包含满足 w(u, v) = l(u) + l(v) 的边的子图，称为该可行顶标下的生成子图。,,匈牙利算法（感兴趣可以自行百度学习）：该算法用于求解二分图的最大匹配算法，核心策略如下：,,定理：,如果二分图存在某组可行顶标，并且该可行顶标的相等子图存在完美匹配，那么该匹配就是原二分图的最佳匹配。,证明：,考虑原二分图的任意一组完美匹配 M ，其边权和 val(M)等于每条匹配边（匹配边没有公共顶点）的权值和，又根据可行顶标的定义，我们可以得出任意一组完美匹配的边权和都小于等于任意一组可行顶标的点权和。,,如果存在一组可行顶标且该可行顶标的相等子图存在完美匹配，那么该相等子图的完美匹配 M'的边权和 val(M')如下。（因为相等子图只存在 w(u, v) = l(u) + l(v) 的边）,,显然对于任意的完美匹配 M，val(M) <= val(M')，所以 M'就是权值和最大的完美匹配，即最佳匹配。,因为二分图两边点的个数相等，假设个数为 n。,首先我们要初始化二分图的可行顶标，二分图左边的点可行顶标取值为：以这个点为端点的最大边权值，二分图右边的点可行顶标取值为：0,我们依次为左边的点匹配，匹配准则是：可行顶标的和等于边权值。（满足相等子图）,对于左边节点 u 的匹配规则是：如果能匹配那么直接匹配，如果不能匹配就以 u 为起点，找交错路，这些交错路会组成一棵以节点 u 为根节点的交错树，树中的任意两条边都是满足匹配准则。如果存在一个叶子节点 v 与其父节点满足匹配准则，并且是非匹配边（存在增广路），那么进行增广操作（对增广路中的匹配边取补集），来增加一条匹配边。如果没有叶子节点满足匹配准则（叶子节点都是匹配点），那么就调整可行顶标的值，如何调整呢？,我们把二分图左边在交错树中的点集记为 S，右边在交错树中的点集记为 T，左边不在交错树中的点集记为 S'，右边不在交错树的点集记为 T',根据左右顶点所在集合，我们可以把二分图中的边分成 4 种：,当一个新点 u 加入集合 T 有两种情况：,这样每调整一轮可行顶标，集合 T 至少增加一个点，那么至多修改 n 次顶标后，就可以找到增广路。,完美婚姻问题为例：现在有 3 男 3 女，不同的男生和不同的女生之间有不同的好感值，情况如图所示（如果没有连边，代表好感度为 0），我们希望让他们两两配对，使得整体的好感度最大。,,初始化策略：构造一个可行顶标，满足 w(u, v) <= l(u) + l(v)，构造方案：所有男生可行顶标取值：0，所有女生取值：最大好感值,,逐一为每个女生找对象，只有满足可行顶和等于边权才能配对,女一：,女二：,女三：,第一轮：,,第二轮：,,递归版本的代码：,参考文档：