Формулировка задачи

Чтобы добраться до сути концепции, задачу следует по возможности очистить от всего лишнего. В мире компаний и кандидатов существует асимметрия, которая только отвлекает от главного. Каждый кандидат подбирает одну компанию, но каждая компания подбирает нескольких кандидатов; более того, количество канди- датов может оказаться больше (или, как это бывает, меньше) количества доступных вакансий.
Наконец, в реальной жизни каждый кандидат редко подает заявки во все имеющиеся компании.

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

Вслед за Гейлом и Шепли мы заметим, что этот частный случай можно рас- сматривать как задачу разработки системы, в которой n мужчин и n женщин могут подыскать себе пару. В нашей задаче существует естественная аналогия для двух «полов» (кандидаты и компании), а в рассматриваемом случае каждый участник подыскивает себе ровно одного участника противоположного пола[1].

Итак, имеется множество M = {m1, ..., mn} из n мужчин и множество W = {wv ..., wn} из n женщин. Пусть запись M χ W обозначает множество всех возможных

упорядоченных пар в форме (m, w), где m

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Формулировка задачи:

  1. Глава 3. ФОРМУЛИРОВКА ВОПРОСОВ И КАЧЕСТВО АНКЕТЫ
  2. 4.3. «Эффект имени» при формулировке вопросов
  3. Требование формулировки "по Уставу"
  4. 3.1. Основные правила формулировки вопросов1
  5. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  6. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  7. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  8. ЗАДАЧА
  9. ЗАДАЧА: РЕШЕНИЕ
  10. Основные задачи.
  11. в) Задачи
  12. в) Задачи
  13. ПСИХОАНАЛИЗ: ЗАДАЧА
  14. Задачи и упражнения
  15. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  16. Основные задачи