Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Решение нелинейного уравнения методом простых итераций http://www.cyberforum.ru/cpp-beginners/thread1220762.html
Здравствуйте, помогите пожалуйста написать программу для решения нелинейного уравнения методом простых итераций f(x)=cos(x)-(-x+5) c погрешностью 0.002. Просто в информатике я полный ноль, подсобите...
C++ Найти первое вхождение подстроки и передать указатель Есть cимвoльная cтрока и подcтpока. Нужно найти пepвоe вхождение подстроки в строку и передать указатель на первый симвoл данного вхождения. Суть задачи понимаю, алгоритм тоже. Но дело доходит до... http://www.cyberforum.ru/cpp-beginners/thread1220756.html
C++ Решение нелинейных неравенств с двумя переменными
Здраствуйте. Мне нужно написать программу которая должна решать системы нелинейных неравенств с двумя переменными. Но проблема в том, что я даже и незнаю как можно решать нелинейные неравенства с...
C++ В одномерном массиве посчитать сумму элементов до последнего нулевого значения. Использовать контейнер - List
не могу сделать...
C++ Компиляция программы VS2010 http://www.cyberforum.ru/cpp-beginners/thread1220744.html
Когда компилирую программу (Debug) всё нормально. Но если выбрать (Release) то появляются куча ошибок: 1>sfml-graphics-s-d.lib(RenderWindow.cpp.obj) : error LNK2038: обнаружено несоответствие для...
C++ Определить наличие восклицательного знака в вводимой строке Вводится набор символов, если есть восклицательный знак, выводится true, если нет - false. #include "stdafx.h" #include <iostream> using namespace std; int main() { char k; char a =... подробнее

Показать сообщение отдельно
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
01.07.2014, 22:51  [ТС]
Алгоритм нахождения наибольшего паросочетания в двудольном графе

Мы опишем сейчас алгоритм выбора наибольшего сочетания в двудольном графе, опираясь на только что введенное понятие матрицы двудольного графа.

Шаг 0. По матрице M=(mij), i=1,...,p, j=1,2,...,q данного двудольного графа строим рабочую таблицу: она представляет собой матрицу тех же размеров; в клетку с номером (i,j) поместим символ "x" и назовем ее недопустимой, если в матрице двудольного графа mij=0 ; если же mij=1, то в клетку рабочей таблицы не запишем ничего и назовем такую клетку допустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов.

Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ "1". Если в первой строке все клетки недопустимы, то перейдем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поставим "1". Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом "1" в третьей строке. Если окажется, что во всей таблице все клетки недопустимы, то на этом все действия заканчиваются и выдается ответ: "в графе нет ребер". Если же все-таки удастся поставить первую "1", то после этого просмотрим все остальные строки таблицы в порядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева направо и фиксируем первую по ходу просмотра допустимую клетку такую, которая является независимой по отношению к допустимым клеткам, в которых уже стоит символ "1", и проставляем в эту клетку "1", после чего переходим к тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку.
Фиксируем набор ребер в графе, соответствующих проставленным в таблице символам "1". (Под ребром, соответствующим символу "1" в рабочей таблице, подразумевается следующее: если "1" стоит в клетке с номером (i,j), то соответствующим будет ребро xi,yj .) Легко заметить, что этот набор ребер - максимальное паросочетание.

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

Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Просмотр очередной строки состоит в следующем: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматриваемой строки. При этом соблюдается принцип (φ ): если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей.

Если в результате этого шага ни один из столбцов не будет помечен, то это означает, что уже имеющееся паросочетание (полученное на Шаге 1) является искомым наибольшим и все действия прекращаются. Если же среди столбцов появятся помеченные, то переходим к следующему шагу.

Шаг 3. Просмотрим помеченные столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскивается символ "1" и строка, в которой он расположен, помечается номером просматриваемого столбца.

Физически пометки выставляются справа от таблицы, на уровне соответствующих строк. Всегда соблюдается принцип (φ).
Если в результате действий по этому шагу возникнет ситуация, когда в просматриваемом столбце нет символа "1", то действия на данном шагу прерываются и надо перейти к следующему шагу - Шагу 4. Если же в результате действий по этому шагу будут просмотрены все помеченные ранее столбцы и, тем самым, возникнет набор помеченных строк (одни будут помечены символом "-", другие - номерами столбцов), то следует вернуться к Шагу 2 и повторить предусмотренные им действия.

Если в результате этих действий по
01.07.14
Шагу 2 не возникнет новых помеченных столбцов, то это означает, что имеющееся паросочетание является искомым и процесс останавливается. Если же среди помечаемых столбцов возникнут новые помеченные столбцы, то следует повторить Шаг 3 с новым набором помеченных столбцов. Если в результате этих действий не возникнет новых помеченных строк, то это означает, что имеющееся паросочетание является искомым.

Шаг 4. Рассматривается столбец, имеющий пометку и не содержащий символа "1". Мы сейчас изменим набор символов "1", расположенных в рабочей таблице.

В рассматриваемый столбец поставим символ "1" в строку, номер которой равен пометке этого столбца. Затем в этой строке отыщем "старый" символ "1" и переместим его по его столбцу в строку, номер которой равен пометке при этом столбце. (Можно доказать, что описанное действие реально всегда осуществимо.) Затем в строке, куда попал последний символ "1" отыщем "старый" символ "1" и с ним проделаем то же самое. В конце концов очередной перемещаемый "старый" символ "1" окажется в строке, где больше символов "1" нет. Возник новый набор символов "1", в котором уже элементов на один больше, чем в исходном наборе символов "1". По этому новому набору можно построить паросочетание так же, как это делалось в самом начале и после этого повторить все сначала.

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

Рассмотрим пример. Найти наибольшее паросочетание в следующем двудольном графе со следующей матрицей:

Сам двудольный граф в этом примере выглядит так:

Будем проводить шаг за шагом описанный выше алгоритм. Рабочая таблица:

Выполняем первый шаг: расставляем независимые единицы и отмечаем строки, в которые единицы не попали:

Паросочетание, которое соответствует выбранным единицам:
Далее столбцы допустимых клеток помеченных строк пометим номерами этих строк, следуя принципу (φ):

Далее в помеченных столбцах отыщем единицы и их строки пометим номерами их столбцов:

Теперь снова пометим столбцы, отправляясь от помеченных строк и соблюдая принцип (φ):

Теперь снова просмотрим помеченные столбцы и пометим строки:

Теперь снова пометим столбцы (при принципе (φ)):

Теперь снова пометим строки:

Сложилась ситуация, когда в столбце №5 с пометкой "4" нет единицы. Следовательно, набор единиц можно увеличить на одну
(старые единицы остаются черными, новые - красные):

Мы получили новый набор независимых единиц:

Теперь вся процедура повторяется сначала, и на последней таблице уже указана единственная пометка "-" у строки №8. Пометим столбцы допустимых клеток этой строки ее номером:

Затем в помеченных столбцах найдем единицы и их строки пометим
номерами столбцов:

Затем столбцы допустимых клеток помеченных строк:

Затем снова строки:

Затем снова столбцы:

Сложилась ситуация, когда расстановка пометок "зациклилась". Это означает, что искомое паросочетание состоит из ребер, соответствующих проставленным единицам.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru