Новость из категории: Информация

Поиск паросочетаний графов с помощью T-SQL

Содержание:
1. Часть I (Вы читаете данный раздел);
2. Часть II ;
3. Часть III;
4. Часть IV .
Поиск паросочетаний графов с помощью T-SQL

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

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

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

Поиск паросочетаний графов с помощью T-SQL

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

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

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

Поиск паросочетаний графов с помощью T-SQL

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

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

Поиск паросочетаний графов с помощью T-SQL

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

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

Рейтинг статьи

Оценка
0/5
голосов: 0
Ваша оценка статье по пятибальной шкале:
 
 
   

Поделиться

Похожие новости

Комментарии

^ Наверх