基本上我有一份工作,有固定数量的职位,比如3个或6个,有N个申请人。
这个工作需要一些技能,比如技能a,b,c,…z。
申请人具备工作所需的一些技能,但可能不是全部。
我正在努力做的是构建一个算法来匹配3或6个申请人,使他们的综合技能满足所有情况下工作所需的许多技能。乐观地实现所有目标,但最坏的情况是尽可能多地实现这些目标
如果这与任何类型的算法相似或相同,请告诉我我不知道如何研究这个。
我试着想一个解决方案,比如增加一个拥有工作所需最多技能的人,然后试着找到一个拥有工作所需最多技能的人。但是,如果解决方案是由具有"中等"技能的人组成,那么这种情况就会崩溃。
我还想把每个申请人的技能变成二进制1或0来表示他们是否有,但我正在努力把它变成有用的东西。我认为这样做可能是正确的。
这不是一个特定的算法,但是解决这类问题的一种方法是使用约束求解器/优化器。例如,在Java中你可以使用OptaPlanner。
这些基本上是声明式系统,所以你不必解释算法,而是必须编写问题所在。基本上描述状态空间,以及什么是或不是解决方案的约束。然后运行它,它会告诉你是否找到了解决方案以及找到了什么解决方案。
注意:这不是一个完整的解决方案,但我想分享一些注意事项。
因此,我们有n
申请人和一套m
技能S = {s(1),s(2),...,s(m)}
。
为了我们的目的,每个申请人都是S
的子集A
,以表征他/她的技能。t
是要选择的申请人数量(例如3或6)。
正如OP所说,我们可以将每个申请人的技能表示为长度为m
的字符串,如果s(i)
属于A
,则i
位置的字符为1,如果不属于CC_10,则为0。
:
S = {Programming, Accounting}
Programming Accounting
Applicant1 0 1
Applicant2 1 1
减少申请人数
我们可以在申请人上定义以下顺序:给定两个申请人a1和a2,我们说a1 <= a2
当且仅当以下语句为真:在上面的例子中,我们有Applicant1 <= Applicant2
.
现在我们可以使用以下顺序过滤我们的申请人集合:如果申请人a1在我们的订单中"低于"另一个申请人a2,则a1可以被丢弃,因为选择a2总是会产生至少相同的结果。这可以在O(n^2)
步骤中完成。
非最优贪婪算法
一旦我们完成,我将这样进行:
r = string of lenght m filled with zeros
choose an applicant a
r = skills(a)
best_applicant = null
APPLICANT_LIST = new LIST
APPLICANT_LIST.add(a)
for(counter=0; counter < (t-1); counter ++)
{
foreach applicant b not in APPLICANT_LIST
{
if (count(skills(b) OR r) > count(r))
then
r = (skills(b) OR r)
best_applicant = b
}
APPLICANT_LIST.add(b)
}
基本上,我会选择一个申请人a
,并从他/她的技能集r
开始,然后搜索将向我现有的r
添加最多技能的申请人b
,以最大化它。我会将b
添加到我的列表中,并重复该过程,直到我有一组t
申请人。所有这些都是在O(n^2)
步骤中完成的(因为t
是常量,所以我忽略它)。从编程的目的来看,这段伪代码可能是不正确的(取决于语言,您可能想要检查退出条件、空指针等),但我相信您已经明白了。
恐怕这种方法并不总是产生最优解,如下例所示:
t = 3
a1 000000001111
a2 000011110000
a3 111100000000
a4 110111001101
如果一个人从a4
开始,他永远不会得到最优解{a1,a2,a3}
。这是我们为每个步骤都是最优的解决方案而付出的代价,但没有从全局角度考虑问题。
注意:在上面的例子中,选择不同的起始申请人没有帮助,因为a4仍然包括在内。不妨完全贪婪地选择拥有最多技能的申请人作为我们的第一个申请人。