如何根据项目的属性匹配项目

本文关键字:项目 属性 何根 | 更新日期: 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算法)