Рассмотрим алгоритм Стабильный брак :
В математике и информатике проблемой стабильного брака (SMP) является проблема нахождения стабильного соответствия между двумя наборами элементов с учетом набора предпочтений для каждого элемента. Сопоставление - это сопоставление элементов одного набора с элементами другого набора. Сопоставление стабильно всякий раз, когда не совпадают оба:
Алгоритм стабильного брака - это полное и оптимальное решение проблемы стабильного брака.
Однако у меня есть другая, но похожая проблема. Мне нужен алгоритм, который при задании пары элементов найдет устойчивое и оптимальное спаривание между ними. Суть в том, что в моей проблеме только одна пара элементов имеет предпочтения, другой стороне все равно .
Чтобы провести аналогию с реальной жизнью, рассмотрим проблему назначения работы:
В групповом проекте по разработке программного обеспечения работают m сотрудников и n
различные задачи, которые необходимо выполнить. У каждого сотрудника есть свой
опыт и знания, поэтому заботится о том, какую задачу он / она получает
работа над. Менеджер просит каждого сотрудника записать предпочтение
список задач, ранжирование каждой задачи. Какой будет алгоритм для
Соедините каждого сотрудника с ОДНОЙ задачей, чтобы удовлетворение
максимизируется.
Если n> m, над задачами останутся, это нормально, они могут быть
заполнено стажерами или подрядчиками.
Примечание: один простой способ определить степень удовлетворенности сотрудника - просто сложить рейтинги рабочих мест, которые получил каждый сотрудник.
Например, : если работник a получил свой первый выбор, а работник b получил третий выбор, а работник c получил второй выбор, общая удовлетворенность сотрудника составляет 1 + 3 + 2 = 6.
Минимизация этого числа максимизирует удовлетворение.