求职algorithm

我的问题对我来说似乎很简单,但是我不能把它分解成能够将它编入我的游戏的基本要素。

首先不同的职业需要不同的技能,这些技能都包含在class里面的Person 。 我有一个world map ,我可以要求所有空的建筑物,从而find所有可用的工作。

有了这些信息,我想从一些权重来计算,玩家可以在每个职业上修改填补某个职位的重要性。

所以我目前的做法是这样的伪代码:

  Job findJob(wm : WorldMap) { Queue priority <- empty; for each building { queue.add(skill * need); } return prority.max(); } 

这听起来愚蠢无效,或者你看到任何你认为我应该知道的特殊情况吗?

  1. 如果没有使用相对于游戏其他部分的CPU,则效率不高。 :)从简单的实现开始,然后返回并稍后改进,只有在需要的时候。

  2. 你的伪代码使用一个队列,但你并不需要整个队列; 你只需要最大的。

  3. 如果你有很多的工人和大量的建筑物,用你的algorithm,最终可能会有很多工人在同一栋建筑物里。 如果你正在努力find最好的任务,那就是没有一个建筑物的工人多于一个,你可能会发现Munkres-Kuhnalgorithm是有用的。 不过,我建议先从最简单的algorithm(你发布的内容)开始,而Munkres-Kuhn并不是最简单的algorithm。

您可能还想看看在双分图中最大加权匹配中描述的其他algorithm。

就你而言,所有找工作的人都应该放在同一个团队里,所有的工作都应该放在另一个工作岗位上。 显然,在同一组中的顶点之间没有边,对于weight(Person,Job) = person.skill * job.need边缘,它的权重等于那个工作weight(Person,Job) = person.skill * job.need需要多less人weight(Person,Job) = person.skill * job.need