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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
01.07.2014, 17:31     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #1
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
UNIT1
 
unit Unit1;
 
interface
 
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ActnList, ExtDlgs, ExtCtrls, jpeg;
 
type
Tform1 = class(Tform)
StringGrid1: TstringGrid;
Button2: Tbutton;
Label1: Tlabel;
Edit1: Tedit;
Button1: Tbutton;
Label2: Tlabel;
Label3: Tlabel;
Button3: Tbutton;
StringGridDug: TstringGrid;
Edit3: Tedit;
StringGrid2: TstringGrid;
StringGrid3: TstringGrid;
Button4: Tbutton;
Button5: Tbutton;
Button6: Tbutton;
StringGrid4: TstringGrid;
StringGrid5: TstringGrid;
StringGrid6: TstringGrid;
Label4: Tlabel;
Label5: Tlabel;
StringGrid7: TstringGrid;
Button7: Tbutton;
Button8: Tbutton;
procedure Button1Click(Sender: Tobject);
procedure Button2Click(Sender: Tobject);
procedure FormCreate(Sender: Tobject);
procedure Button3Click(Sender: Tobject);
procedure Button4Click(Sender: Tobject);
procedure Button5Click(Sender: Tobject);
procedure Button6Click(Sender: Tobject);
procedure FormShow(Sender: Tobject);
procedure Button7Click(Sender: Tobject);
procedure Button8Click(Sender: Tobject);
 
private
{ Private declarations }
public
{ Public declarations }
end;
 
const
max = 100; { размер большего из двух множеств }
 
var
Form1: Tform1;
n, i, j, del, x, cnt, y, page, ch, s: integer;
osn, dop: array [1 .. max, 1 .. max] of string;
rez: array [1 .. max, 1 .. max] of integer;
str, stolb: array [1 .. 100] of integer;
t: TextFile;
 
implementation
 
uses Unit2;
 
{$R *.dfm}
 
/// Заполнение
procedure Tform1.Button1Click(Sender: Tobject);
begin
Button1.Visible := false;
page := 7;
StringGrid7.Visible := false;
StringGrid6.Visible := false;
StringGrid5.Visible := false;
StringGrid4.Visible := false;
StringGrid3.Visible := false;
StringGrid2.Visible := false;
StringGrid1.Visible := true;
StringGridDug.cols[1].add(‘x’);
StringGridDug.cols[2].add(‘y’);
for j := 1 to x do
begin
StringGridDug.Cells[1, j] := ‘’;
StringGridDug.Cells[2, j] := ‘’;
end;
x := strtoint(Edit1.Text);
y := strtoint(Edit3.Text);
StringGrid1.ColCount := x + 2;
StringGrid1.RowCount := y + 2;
for i := 1 to x do
StringGrid1.cols[i].add(‘х ‘ + inttostr(i));
for j := 1 to y do
StringGrid1.Rows[j].add(‘y ‘ + inttostr(j));
for i := 1 to x do
begin
for j := 1 to y do
StringGrid1.Cells[i, j] := inttostr(0);
end;
end;
 
/// Выход
procedure Tform1.Button2Click(Sender: Tobject);
begin
Form1.Close;
end;
 
/// Основное решение
procedure Tform1.Button3Click(Sender: Tobject);
label
shag2, shag3, shag4, shag5;
begin
StringGrid1.Visible := false;
StringGrid2.Visible := true;
StringGrid2.ColCount := x + 2;
StringGrid2.RowCount := y + 2;
/// //////////// шаг 0
for i := 1 to x do
StringGrid2.cols[i].add(‘х ‘ + inttostr(i));
for i := 1 to y do
StringGrid2.Rows[i].add(‘y ‘ + inttostr(i));
for i := 1 to x do
begin
for j := 1 to y do
if StringGrid1.Cells[i, j] = inttostr(0) then
StringGrid2.Cells[i, j] := ‘x’
else
StringGrid2.Cells[i, j] := ‘’
end;
/// ///////////////////
StringGrid3.ColCount := x + 2;
StringGrid3.RowCount := y + 2;
for i := 1 to x do
StringGrid3.cols[i].add(‘х ‘ + inttostr(i));
for i := 1 to y do
StringGrid3.Rows[i].add(‘y ‘ + inttostr(i));
for i := 1 to x do
begin
for j := 1 to y do
StringGrid3.Cells[i, j] := StringGrid2.Cells[i, j];
end;
for i := 1 to x do
stolb[i] := 0;
for i := 1 to y do
str[i] := 0;
/// ////////////// шаг 1
for i := 1 to x do
begin
for j := 1 to y do
if (StringGrid3.Cells[i, j] = ‘’) and (stolb[i] <> 1) and (str[j] <> 1)
then
begin
StringGrid3.Cells[i, j] := inttostr(1);
stolb[i] := 1;
str[j] := 1;
end;
end;
cnt := 0;
for i := 1 to y do
begin
if str[i] <> 1 then
StringGrid3.Cells[x + 1, i] :=-;
end;
for i := 1 to y do
begin
if str[i] = 1 then
cnt := cnt + 1;
end;
/// ////////////////
StringGrid2.Visible := false;
StringGrid3.Visible := true;
if y = cnt then
begin
showmessage(‘Максимальное паросочетание найдено’);
n := 1;
for i := n to x do
begin
for j := 1 to y do
if StringGrid3.Cells[i, j] = inttostr(1) then
begin
StringGridDug.Cells[1, n] := intto
Возможно ли перевести этот код из делфи в си?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2014, 17:31     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе)
Посмотрите здесь:

C++ Алгоритм Габова для поиска максимального паросочетания в произвольном графе за O(V^3)
Написать программу нахождения наибольшего и наименьшего значения функции C++
Нужно немного переделать программу нахождения компонент сильной связности в графе C++
C++ составить алгоритм нахождения суммы наибольшего и наименьшего из заданных чисел
C++ Написать подпрограмму нахождения наибольшего общего делителя двух чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volvo
Супер-модератор
 Аватар для volvo
21815 / 14178 / 3949
Регистрация: 22.10.2011
Сообщений: 25,055
Записей в блоге: 2
01.07.2014, 17:53     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #2
В какой Си? Каким компилятором пользуешься?
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
01.07.2014, 19:11  [ТС]     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #3
Dev-C++ там встроенный компилятор
volvo
Супер-модератор
 Аватар для volvo
21815 / 14178 / 3949
Регистрация: 22.10.2011
Сообщений: 25,055
Записей в блоге: 2
01.07.2014, 22:46     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #4
Тема перенесена в правильный раздел. Теперь увидеть бы код на Дельфи полностью, а не этот огрызок, и, если можно, задачу, которую код призван решать.
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
01.07.2014, 22:51  [ТС]     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #5
Алгоритм нахождения наибольшего паросочетания в двудольном графе

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

Шаг 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. Пометим столбцы допустимых клеток этой строки ее номером:

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

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

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

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

Сложилась ситуация, когда расстановка пометок "зациклилась". Это означает, что искомое паросочетание состоит из ребер, соответствующих проставленным единицам.
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
02.07.2014, 18:25  [ТС]     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #6
UI, Весь код не влезает,поэтому кину в архиве:
Вложения
Тип файла: rar Листинг.rar (3.0 Кб, 42 просмотров)
Mekan
0 / 0 / 0
Регистрация: 24.12.2014
Сообщений: 34
24.12.2014, 20:59     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #7
дайте пжл вес код
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2015, 13:29     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе)
Еще ссылки по теме:

C++ Алгоритмы нахождения наибольшего числа
C++ Написать функцию для нахождения наибольшего числа
Рекурсивный алгоритм Евклида нахождения наибольшего общего делителя C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Sofia22
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 1
24.04.2015, 13:29     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) #8
Где можно увидеть программу к данной задаче на Си ++?
Yandex
Объявления
24.04.2015, 13:29     Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе)
Ответ Создать тему
Опции темы

Текущее время: 12:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru