Алгоритм планирования работника

Ответ 1

"Проблема больниц/жителей" действительно может работать, но это зависит от ваших ограничений:

• Больница имеет максимальную пропускную способность и будет заказывать резидента (наиболее желаемого менее желаемого).
• Резиденты будут заказывать больницы.
• Никаких других ограничений не возможно.

В вашем случае больницы являются рабочими, а жители - слотами.

• Слоты могут заказывать работников (возможно, вы предпочитаете экспериментировать утром...).
• Рабочие могут заказать слоты.
• Но у вас не может быть других ограничений, таких как: "Я работал утром, я не хочу работать в тот же день вечером".

Если это нормально для вас, тогда у вас есть возможности:

• вы хотите использовать преимущества для работников: "больничный ориентированный случай".

  Вы попытаетесь назначить работников своим предпочтительным слотам.

• вы хотите использовать слоты преимуществ: "резидентный ориентированный случай"

  Каждый слот будет иметь своих предпочтительных работников.

Мне пришлось закодировать его в прошлом году, вот код.

/* 
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;
        }
    }
}

Пример использования, чтобы показать, как построить ранг из префов. (В этом случае списки предпочтений были на stdin).

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 находится в позиции 4 в H_pref [1], 3 не является)
• 2 → 3 2 5 1 6 4
• 3 → 1 2 INF INF INF INF

Аналогичен для R_rank.

Больница не должна оценивать всех, а также может оценивать меньше людей, чем их способность.

Ответ 2

В случае, если кто-то сталкивается с подобной проблемой, вот решение, с которым я пошел:

В итоге я использовал Алгоритм поиска обратного следа для проблем ограничения ограничений. Все, что он делает, выполняет обычный поиск в обратном направлении, но проверяет, удовлетворяются ли все ограничения, когда он пересекает дерево. Вот псевдокод:

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

Переменная - временной интервал. Возможными значениями, присвоенными переменной, являются рабочие. Комбинация переменной и ее фактическое назначение - это node в дереве. Таким образом, поисковое пространство - это все возможные комбинации временных интервалов и рабочих. Ограничения обрезают узлы из пространства поиска.

Ограничением может быть доступность рабочих. Поэтому, если временному слоту A назначен Рабочий X, но X не может работать во временном интервале A, тогда этот node будет управляться несовместимым.

Я решил проблему того, что конкретный временной интервал назначается нескольким работникам, рассматривая каждую комбинацию временных интервалов/работников как СОБСТВЕННЫЙ временной интервал. Поэтому, если в детском саду есть 2 рабочих, я считаю, что это два отдельных временных интервала, каждый из которых получает своего собственного работника. Таким образом, каждой переменной присваивается только одно значение. Он делает для МНОГО более простых алгоритмов.

Спасибо за всю помощь, уменьшив ее до разрешимой проблемы.