英文:
Creating a timetable from two lists. One of availability of interviewers and the other of preferences of interviewees
问题
我很确定这是一个研究较多的问题，可能存在某些算法，但我只是没有找到正确的术语来找到它。
我有两个列表，一个是候选人及其面试官偏好的列表。比如，[{"candidate1": ["interviewer1", "interviewer9"...}...]。另一个是面试官的可用时间列表，比如，[{"interviewer1": ["slot 1", "slot 4"]}]。
面试官最多有30个时间段，但并非所有时间段都可用。
候选人应至少见到他们前三名偏好中的一名面试官，而候选人会将所有可能的面试官排名在他们的偏好列表中。候选人超过30人，因此不是每个候选人都会见到每位面试官。
对我来说，这与稳定婚姻问题非常相似，但在那种情况下，每个集合只有一个婚姻。在这种情况下，每个候选人将进行多次面试。我一直试图以加权图和某种变体的最大配对的方式思考它，但可能走错了方向。
我正在使用Python进行工作，但没有示例代码可以分享，因为我真的在寻找正确的算法，一旦知道它是什么，就会猜想是否存在现有的实现。
英文:
I'm pretty sure this is a well studied problem and that there is some algorithm but I'm just not searching the right terms to find it.
I have two lists, one of a list of candiates and their preference of interviewer. Say, [{"candidate1": ["interviewer1", "interviewer9"...}...]
A second list of the interviewers' availability, say, [{"interviewer1": ["slot 1", "slot 4"].
The interviewers will have up to 30 slots but will not be available in all slots.
And the candidates should get to meet at least 1 of their top 3 preferences, and the candidates will have ranked all interviewers possible in their list of preferences. There will be more than 30 candidates, so not every candidate will meet every interviewer.
To me this is very similar to the stable marriage problem, but in that there's only one marriage for each set. In this case, each candidate will have multiple interviews. I've been trying to think about it in terms of a weighted graph and some variant of maximal pairing, but could be going down the wrong track.
I'm working in Python, but do not have any example code to share as I'm really looking for the right algorithm and would guess there are existing implementations for it once I know what it is.
答案1
得分: 2
这是一个分配问题。
首先，简化一下：假设没有偏好（或者所有偏好都相等）。
这是图中的最大流问题的一个特例，其中有多个源（代理）和汇（任务），所有边的容量都设置为1。如果从代理到任务存在“流”，则表示应该将代理分配给任务。
关于此问题的详细讨论和用于实现它的C++代码，请参阅 https://github.com/JamesBremner/PathFinder/wiki/Allocate
变量偏好。
我假设您希望最大化满足的高偏好数量，因为我不相信您的候选人会费心对30位面试官进行有意义的排名。为了做到这一点，您只能在“偏好”的源和汇之间建立链接（也许是前3个）。这可能会导致一些汇（面试官）被低估利用，如果是这种情况，您可以添加链接到低估利用的汇并重新计算新的图。
英文:
This is an allocation problem.
First, a simplification: Assume that there are no preferences ( or all preferences are equal ).
This is a special case of maximum flow through a graph, with multiple sources ( agents ) and sinks ( tasks ) and all edges have their capacity set to 1. If there is a 'flow' from an agent to a task, then it indicates the agent should be assigned to the task.
For a detailed discussion of this and C++ code to implement it see https://github.com/JamesBremner/PathFinder/wiki/Allocate
Variable preferences.
I assume you want to maximize the number of high preferences that are met, because I just do not believe that your candidates are going to take the trouble to rank all 30 interviewers in any meaningful way. To do this you could only make links between sources and sinks that are "preferred" ( perhaps the top 3 ). This may leave some sinks ( interviewers ) under-utilized, in which case you can add links to the under-utilized sinks and recalculate the new graph.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论