Стабильные встречи в C#

В этом примере предполагается, что у вас есть люди, которые должны зарегистрироваться для ограниченного числа встреч. Каждому человеку разрешается выбирать первый, второй и третий варианты. Программа назначает людей на встречи «стабильным» способом, когда «стабильный» означает, что два человека не захотят торговать встречами.

Класс Person представляет человека и его предпочтения.

Следующий код выполняет задания.

// Сделать присвоения
private void btnGo_Click(object sender, EventArgs e)
{
    // Получить предпочтения людей.
    string txt = txtPreferences.Text;
    while (txt.EndsWith("\r\n"))
    {
        txt = txt.Substring(0, txt.Length - "\r\n".Length);
    }
    txt=txt.Replace("\r\n", "\n");
    string[] lines = txt.Split('\n');
    int num_people = lines.Length;

    Person[] people = new Person[num_people];
    for (int i = 0; i < num_people; i++)
        people[i] = new Person(lines[i]);

    // Очистить присвоения.
    Person[] assigned_to = new Person[Person.NUM_CHOICES];
    for (int i = 0; i < Person.NUM_CHOICES; i++)
    {
        assigned_to[i] = null;
    }

    // Сделать начальные выборки.
    for (int pref = 0; pref < Person.NUM_PREFERENCES; pref++)
    {
        // Попробуйте назначить этот выбор для Лица.
        foreach (Person per in people)
        {
            // Посмотрим, есть ли у этого Человека еще какое-то задание.
            if (per.Assignment < 0)
            {
                // Этот человек не назначен.
                // Посмотрим, доступен ли этот выбор.
                int desired_choice = per.Preferences[pref];
                if (assigned_to[desired_choice] == null)
                {
                    // Назначить этого человека.
                    assigned_to[desired_choice] = per;
                    per.Assignment = desired_choice;
                }
            }
        }
    }

    // Назначьте любого без назначения.
    foreach (Person per in people)
    {
        // Посмотрим, есть ли у этого Человека еще какое-то задание.
        if (per.Assignment < 0)
        {
            // Этот человек не назначен.
            // Найдите доступный выбор.
            for (int i = 0; i < Person.NUM_CHOICES; i++)
            {
                if (assigned_to[i] == null)
                {
                    // Назначить этого человека.
                    assigned_to[i] = per;
                    per.Assignment = i;
                    break;
                }
            }
        }
    }

    // Попытаемся улучшить назначения.
    bool had_improvement;
    do
    {
        had_improvement = false;

                foreach (Person per in people)
        {
            foreach (Person per2 in people)
            {
                int per2_assignment = per2.Assignment;
                int per_assignment = per.Assignment;

                                int old_cost = per.Value + per2.Value;
                int new_cost =
                    per.ValueOf(per2_assignment) +
                    per2.ValueOf(per_assignment);
                if (new_cost < old_cost)
                {
                                        per.Assignment = per2_assignment;
                    per2.Assignment = per_assignment;
                    assigned_to[per_assignment] = per2;
                    assigned_to[per2_assignment] = per;
                    had_improvement = true;
                }
            }
        }
    } while (had_improvement);

        txtAssignments.Text = AssignmentSummary(assigned_to, people);
}

Код считывает информацию о предпочтениях из текстового поля и использует его для создания объектов Person.

Далее код выполняет начальные задания. Для каждого уровня предпочтений (в этом примере люди занимают три встречи 0, 1 или 2), код проверяет объекты Person. Если a Person еще не назначен и что Person предпочтение объекта для этого уровня не было назначено, программа выполняет это назначение.

Например, предположим, что программа смотрит на предпочтение 1 (второй выбор). Салли еще не назначена на прием, а ее выбор № 1 - слот для встреч 6. Если этот слот еще не был сделан другим Person, программа назначает его Салли.

После того, как он выполнил эти преференциальные назначения, программа назначает любое непризнанное Person любую доступную встречу.

Далее программа входит в цикл, ищущий улучшения. Для каждой пары объектов Person программа определяет, должны ли эти лица торговать встречами. Например, предположим, что Биллу было назначено его первое назначение на прием № 3, а Синди была назначена должность № 7, которую она не указала в качестве одного из своих выборов. Предположим, что Билл назвал назначение 7 своим третьим выбором, а Синди назвал назначение 3 своим вторым выбором. В этом случае программа свопит встречи Билла и Синди. Он предпочитает третий / второй выбор по первому / никому варианту.

Обратите внимание, что этот пример не гарантирует какой-либо оптимальности. Могут быть более сложные сделки с участием более двух человек, которые приведут к лучшему окончательному решению. Я могу работать над другой программой, чтобы посмотреть на это более внимательно.

Источник: http://csharphelper.com/blog/2016/12/make-stable-appointments-in-c/

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Adblock
detector