Лара шла вдоль полотна по тропинке, протоптанной странниками и богомольцами, и свернула на луговую стежку, ведшую к лесу. Тут она остановилась и, зажмурив глаза, втянула в себя путано-пахучий воздух окрестной шири. Он был роднее отца и матери, лучше возлюбленного и умнее книги. На одно мгновение смысл существования опять открылся Ларе. Она тут — постигала она — для того, чтобы разобраться в сумасшедшей прелести земли и все назвать по имени…

Борис Пастернак «Доктор Живаго», 1957 г.

Общие принципы

Несколько лет назад я столкнулся с одной задачей из области T-SQL. Со временем я понял, что у нее должно быть практическое применение. Если эту идею удастся реализовать, то, вероятно, можно будет найти оптимизированные алгоритмические решения и на их основе работать над адаптацией для T-SQL.

Для многих математика передает «сумасшедшую прелесть земли», хотя Борис Пастернак вряд ли разделял это мнение, когда писал свой роман. Люди сталкиваются с логическими задачами и придумывают математические алгоритмы, чтобы решать их. Человечество экономит время, повторно используя эти решения и непрерывно совершенствуя их. Секрет в том, чтобы дать имена задачам и решениям. Впоследствии, называя задачи правильными именами, вы сокращаете путь к эффективному решению.

Итак, вот с какой задачей из области T-SQL я столкнулся однажды.

Даны две таблицы. Таблица G со столбцами x, y и уникальным ключом, определенным на комбинации (x, y). Таблица M со столбцами x, y и двумя уникальными ключами, один из которых определен на x, а другой на y. В таблице G уже есть несколько строк, а таблица M пустая. Задача — скопировать из G в M как можно больше строк.

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

Недавно я понял, что у этой задачи должно быть интересное практическое применение, а также более формализованное условие. Если мне удастся найти их, то, вероятно, я найду и существующие оптимизированные алгоритмические решения и на их основе смогу работать над адаптацией для T-SQL? Эта мысль оказалась верной.

Начнем с практического применения. Предположим, что в таблице G содержатся пары соискателей рабочих мест (столбец x) и рабочих мест или задач, для выполнения которых у соискателей есть необходимая квалификация (столбец y). В данном временном интервале (например, в течение смены) каждый соискатель может занимать только одно рабочее место, и для замещения каждого рабочего места требуется только один соискатель. Необходимо записать в таблицу M максимальное число пар «соискатель — рабочее место». Естественно, можно подыскать множество других примеров, например распределение учителей по классам, пилотов по рейсам и т. д.

В математической теории графов эта задача известна как поиск максимального по размеру паросочетания (M) в невзвешенном двудольном графе (G). Существуют алгоритмические решения, например алгоритм Форда-Фалкерсона, согласно которому выполняется повторяющийся поиск M c увеличением размера в G и обновление M с использованием симметрической разности этого пути и M.

Если вы смотрите на этот текст бессмысленным взглядом и почесываете затылок — не переживайте. Скоро вы освоитесь в этой теме. Тогда, перечитав предыдущий абзац, вы воскликнете: «Ну конечно!».

Но для этого потребуется несколько статей. В данной статье изложены общие принципы и термины, применяемые в задачах паросочетания графов. Также здесь будут описаны классические задачи, такие как наибольшее...

Это не вся статья. Полная версия доступна только подписчикам журнала. Пожалуйста, авторизуйтесь либо оформите подписку.

Поделитесь материалом с коллегами и друзьями

Купить номер с этой статьей в PDF