如何根据项目的属性匹配项目
本文关键字:项目 属性 何根 | 更新日期: 2023-09-27 18:20:00
我正在尝试编写一种算法,根据项目的属性匹配它们。
我有一份课程清单,每门课程都属于一个或多个类别。一个级别的每个类别必须有一个主题。一个主题不能用于针对一个级别中一个以上类别的证据。
例如:
课程x有类别:Cat 1、Cat 2、Cat 3、Cat 4和Cat 5。
Subject A - Cat 1, Cat 2
Subject B - Cat 2, Cat 3
Subject C - Cat 4
Subject D - Cat 2, Cat 4
Subject E - Cat 5
在这种情况下,我会把
A Cat 1,
B Cat 3,
C Cat 4,
D Cat 2,
E Cat 5.
学生在运行算法时可能还没有完成所有类别,因此它需要能够应对这种情况。
非常感谢任何帮助/建议/论文/片段。我有1500条记录要匹配,必须手动启动这个过程才能按时完成。
对我来说,这看起来像是一个二分图匹配问题,其中图由两个方面组成:类别、主题。边缘是范畴与主体的连接。
图的最大匹配也将是某些course x
的最优结果。
在您的例子中,二分图是:
G=(V,U,E)
V = { Cat1, Cat2, Cat3, Cat4, Cat5}
U = { Subject A, Subject B, Subject C, Subject D, Subject E}
E = { (A,1), (A,2), (B,2), (B,3), (C,4), (D,2), (D,4), (E,5) }
这可以通过各种方式解决(如将其转换为最大流量问题,或使用Hopcroft-Karp算法)