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

Я решил подготовить хранимую процедуру с именем MaximalMatching, которая заполняет M с применением наибольшего паросочетания. То есть паросочетанием, которое не может быть расширено путем добавления дополнительных ребер из G. Напомню, что наибольшее паросочетание — не обязательно паросочетание максимальной мощности. Последнее — паросочетание с максимальным возможным числом ребер. На рисунке 1 показаны различные типы паросочетаний.

 

Примеры паросочетания в графе
Рисунок 1. Примеры паросочетания в графе

 

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

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

Тестовые данные

Работая над решениями для задачи T-SQL, я обычно использую два набора тестовых данных: малый набор для быстрой оценки правильности решения и большой набор для измерения производительности.

Используйте программный код листинга 1 для создания малого набора тестовых данных, а для создания большого набора тестовых данных — программный код листинга 2.

В случае с большим набором тестовых данных вы инициализируете @n с общим числом строк, которые должны присутствовать в G. Вы получите приблизительно это число на практике. Оно представляет собой сумму арифметической последовательности. Например, если инициализировать @n числом 10, это число представляет сумму арифметической последовательности 1 + 2 + 3 + 4. Назначение SET @n = SQRT (@n * 2) вычисляет количество членов последовательности (4 в нашем примере). Затем программный код заполняет таблицу значениями x от 1 до @n и сопоставляет различным значениям x значения @n, @n-1, @n-2, …, 1...

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

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

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