11

问题

这是我要解决的问题的本质。我们有工人在周末的固定时间在托儿所照顾孩子。一个周末有 16 个不同的位置可以填补。因此，在为期 4 周的月份中，有 64 个空位可以填补。我们最多有 30 名托儿所工作人员（尽管我们需要更多。有人喜欢孩子吗？）。

编辑：每个时间段都是离散的——它们不重叠。

目前每个月都有一个人提出托儿所的时间表。根据每个人的喜好每个月制定这个时间表是一项复杂且耗时的任务。在考虑了这个问题后，我心想：“一定有更好的方法！”

算法

我注意到这个问题本质上是一个二分图。婚姻问题也是一个二分图，您可以使用像Edmonds 的匹配算法这样的匹配算法来解决它。

但这假设一个节点集中的每个节点只匹配另一个节点集中的一个节点。就我而言，每个托儿所工作人员只能工作一个时间段。由于我们人手严重不足，那是行不通的！一群人将不得不每月工作两次来填补所有的时间段。

这似乎意味着这更像是经典的“医院/居民问题”。它与婚姻问题的不同之处在于“女人”可以接受来自多个“男人”的“求婚”（例如，一家医院可以接收多个居民）。就我而言，一名托儿所工作人员可以占用多个时间段。

现在怎么办？

哇！

现在我已经设置好了....有人知道解释或显示这种算法的任何好的链接吗？有没有更好的方法来解决这个问题？我是不是想多了？我在谷歌上搜索了“医院居民算法”并找到了研究生论文。呸！我毕业于 CS 学位并参加了 AI 课程……但那是 6 年前的事了。帮助！

Aaaaany 建议表示赞赏！

4

2 回答 2

4

“医院/居民问题”确实可以解决，但这取决于您的限制：

  • 医院有最大的容量，并会命令居民（最想要的，不太想要的）。
  • 居民将订购医院。
  • 不可能有其他约束。

在您的情况下，医院是工人，居民是插槽。

  • 插槽可以订购工人（也许你更喜欢早上做实验的......）。
  • 工人可以订购插槽。
  • 但是你不能有其他约束，例如：“我早上工作，我不想在同一天晚上工作”。

如果这对您来说没问题，那么您必须有以下可能性：

  • 你想对工人有利：“医院导向案例”。

    您将尝试将工作人员分配到他们喜欢的插槽。

  • 您想利用插槽：“面向居民的案例”

    每个插槽都会有他们喜欢的工人。

去年我不得不对其进行编码，这是代码。

/* 
RO : needed for Resident-Oriented version
HO : needed for Hospital-Oriented version
*/
const int MAX_R = 1000;
const int MAX_H = 1000;
const int INF = 1000*1000*1000;

您需要填写输入变量。一切都很简单：

  • R_pref 和 H_pref 是居民/医院的偏好列表
  • H_rank[h][r] 是 r 在 H_pref[h] 中的排名： r 在 h 的偏好列表中的位置

就这样。

// Input data
int R, H;                   // Number of Residents/Hospitals
int C[MAX_H];               // Capacity of hospitals
vector<int> R_pref[MAX_R], H_pref[MAX_H]; // Preferences : adjency lists
/*RO*/int H_rank[MAX_H][MAX_R];   // Rank : rank of r in H_pref[h]
/*HO*/int R_rank[MAX_R][MAX_H];   // Rank : rank of h in R_pref[r]

无需触摸下方。

// Internal data
int RankWorst[MAX_H];   // Rank of the worst r taken by h
/*RO*/int BestH[MAX_R];       // Indice of the best h in R_pref the r can get
/*HO*/int BestR[MAX_H];       // Indice of the best r in H_pref the h can get
int Size[MAX_H];        // Number of residents taken by h

// Output data
int M[MAX_R];

void stable_hospitals_RO()
{
    for(int h = 0 ; h < H ; h++)
      RankWorst[h] = H_pref[h].size()-1;
    fill_n(BestH, R, 0);
    fill_n(Size, H,0);
    fill_n(M,R,INF);
    for (int i = 0; i < R; i++)
        for (int r = i; r >= 0;)
        {
        if(BestH[r] == int(R_pref[r].size()))
            break;
            const int h = R_pref[r][BestH[r]++];
            if(Size[h]++ < C[h])
            {
                M[r] = h;
                break;
            }
            int WorstR = H_pref[h][RankWorst[h]];
            while(WorstR == INF || M[WorstR] != h) // Compute the worst
                WorstR = H_pref[h][--RankWorst[h]];
            if(H_rank[h][r] < RankWorst[h])        // Ranked better that worst
            {
                M[r] = h;
                M[r = WorstR] = INF;    // We have eliminate it, he need to put it somewhere
            }
        }
}
void stable_hospitals_HO()
{
    fill_n(BestR, H, 0);
    fill_n(Size, H,0);
    fill_n(M,R,INF);
    vector<int> SH;
    for (int h = 0; h < H; h++)
        SH.push_back(h);
    while(!SH.empty())
    {
        int h = SH.back();
        if(Size[h] == C[h] || BestR[h] == int(H_pref[h].size())) // Full or no r available
        {
            SH.pop_back();
            break;
        }
    const int r = H_pref[h][BestR[h]++];
    // r is unassigned or prefer h to current hospital
        if(M[r] == INF || R_rank[r][h] < R_rank[r][M[r]]) 
        {
            if(++Size[h] == C[h]) // Will be full
                SH.pop_back();
            if(M[r] != INF) // Delete from M[r]
            {
                Size[M[r]]--;
                SH.push_back(M[r]);
            }
            M[r] = h;
        }
    }
}

用于展示如何从首选项建立排名的示例。（在那种情况下，偏好列表在标准输入上）。

int main()
{
    scanf("%d%d",&R,&H);
    int num;
    // put inf

    for(int r = 0 ; r < R ; r++)
    {
        scanf("%d",&num);
        R_pref[r].resize(num);
        for(int h = 0 ; h < num ; h++)
        {
            scanf("%d",&R_pref[r][h]);
            R_rank[r][R_pref[r][h]] = h;
        }
    }
    for(int h = 0 ; h < H ; h++)
    {
        scanf("%d",&C[h]);
        scanf("%d",&num);
        H_pref[h].resize(num);
        for(int r = 0 ; r < num ; r++)
        {
            scanf("%d",&H_pref[h][r]);
            H_rank[h][H_pref[h][r]] = r;
        }
    } 
    stable_hospitals_RO();
    printf("\n\n\n\n");
    stable_hospitals_HO();
    return 0;
}

举个例子：医院 1 到 3，6 位居民。

H_pref ：

  • 1 -> 2 5 6 1（首选 2 然后 5 然后 6 然后 1）
  • 2 -> 4 2 1 6 3 5
  • 3 -> 1 2

R_pref ：

  • 1 -> 1 2 3
  • 2 -> 3 1
  • 3 -> 2 1
  • 4 -> 1 3 2
  • 5 -> 3 2 1
  • 6 -> 3

H_rank :

  • 1 -> 4 1 INF INF 2 3（1 在 H_pref[1] 中的位置 4，3 不存在）
  • 2 -> 3 2 5 1 6 4
  • 3 -> 1 2 INF INF INF INF

R_rank 类似。

医院不必对每个人进行排名，也可以对低于其能力的人进行排名。

于 2010-09-23T12:32:27.260 回答
1

如果有人遇到类似的问题，这是我采用的解决方案：

我最终使用回溯搜索算法来解决约束满足问题。它所做的只是进行正常的回溯搜索，但在遍历树时检查是否满足所有约束。这是伪代码：

function BACKTRACKING-SEARCH(csp) returns a solution, or failure
     return BACKTRACK({ }, csp)

function BACKTRACK(assignment, csp) returns a solution, or failure
     if assignment is complete then return assignment
     var = SELECT-UNASSIGNED-VARIABLE(csp)
     for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        if value is consistent with assignment then
           add {var = value} to assignment
           result = BACKTRACK(assignment, csp)
           if result != failure then
              return result
           remove {var = value} 
     return failure

变量是一个时隙。分配给变量的可能值是工人。变量及其实际赋值的组合是树中的一个节点。因此，搜索空间是时隙和工作人员的所有可能组合。约束从搜索空间中修剪节点。

约束可以是工人的可用性。所以如果时间槽A被分配了Worker X，但是X不能在时间槽A工作，那么这个节点就会被判定为不一致。

我通过将每个时隙/工作者组合视为它的 OWN 时隙，解决了为特定时隙分配多个工作者的问题。因此，如果儿童托儿所有 2 名工人要填补，我认为这是两个单独的时间段来填补，每个时间段都分配了自己的工人。这样，每个变量只分配一个值。它使算法更简单。

感谢所有帮助将其缩减为可解决的问题。

于 2011-01-09T03:05:13.713 回答