質問編集履歴
3
どういう風にしたいかわからないとのご指摘を頂いたので直させていただきました。力になっていただければ幸いです。
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -1,11 +1,41 @@
|
|
|
1
1
|
C言語で2部グラフのマッチングを求めるプログラムを利用してラテン方陣を書きたいのですが、マッチングする行をfor文で回せばいいということがわかるのですが、マッチングしたものを保存して、再度マッチングさせるのがどうすれば上手く行くのかわかりませんでした。プログラムは６×６行列です。またマッチングしたものを最後行列として表示する方法についても悩んでいます。
|
|
2
2
|
下記は１つの２部グラフマッチングを求めるプログラムです。
|
|
3
|
+
一番下は元のプログラムで、教えてもらったもので
|
|
4
|
+
０１２３ ４ ５
|
|
5
|
+
６７８９１０１１の点でのマッチングを表しています。
|
|
6
|
+
|
|
7
|
+
ですが配列内の動きを見たかったと、少しマッチングしたものが見にくかったので表示を
|
|
8
|
+
１２３４５６
|
|
9
|
+
１２３４５６の点として表示を考えたのが上のプログラムです。
|
|
10
|
+
|
|
11
|
+
方法としては
|
|
12
|
+
２部グラフでのマッチングを求めるプログラムですので、マッチングした下の点を保存して、上の点として扱い再度マッチングすべきもとの点を探す様にしたいです。
|
|
13
|
+
|
|
14
|
+
さらに要領としては回目は1＝｛2，3，4，5，6｝の点とマッチングが可能で２を選んだ場合２回めでは2＝｛3，4，5，6｝の点から選べるという様に１回ずつ各点が選べる回数が減っていけば最終的に決定すると考えられます。なので、はじめは上の一つの点から自身を除いた全ての点にパスが出ている状態から、回数を重ねるごとにパスが減っていく様にすれば自然とラテン方陣としてできると考えられます。
|
|
15
|
+
|
|
16
|
+
例えば
|
|
17
|
+
１２３４５で作った場合で、２行目で
|
|
18
|
+
５４２３１となった場合
|
|
19
|
+
|
|
20
|
+
５４２３１の結果を元にマッチングを行い
|
|
21
|
+
３１４５２とマッチングさせる
|
|
22
|
+
という様にすれば
|
|
23
|
+
求めたい行の回数分行う事によってラテン方陣ができると思います。
|
|
24
|
+
最終的には
|
|
25
|
+
|
|
26
|
+
１２３４５
|
|
27
|
+
５４２３１
|
|
28
|
+
３１４５２
|
|
29
|
+
４５１２３
|
|
30
|
+
２３５１４
|
|
31
|
+
|
|
32
|
+
というような形に表示をしたいです。
|
|
33
|
+
|
|
3
34
|
教えてくださる方がいたらよろしくお願いします。
|
|
4
35
|
|
|
5
36
|
|
|
6
|
-
|
|
37
|
+
```ここに言語を入力
|
|
7
|
-
|
|
38
|
+
コード
|
|
8
|
-
/*２部グラフマッチング*/
|
|
9
39
|
#include <stdio.h>
|
|
10
40
|
#include <stdlib.h>
|
|
11
41
|
#define V 12
|
|
@@ -59,7 +89,7 @@
|
|
|
59
89
|
for(p=0;p<V;p++){
|
|
60
90
|
for(q=0;q<V;q++){
|
|
61
91
|
if(q%r==0)printf("|");
|
|
62
|
-
|
|
92
|
+
printf("%2d",A[q][p]);
|
|
63
93
|
}
|
|
64
94
|
printf("\n");
|
|
65
95
|
}
|
|
@@ -113,5 +143,107 @@
|
|
|
113
143
|
return(0); // could not find augmenting path
|
|
114
144
|
}
|
|
115
145
|
}
|
|
146
|
+
|
|
147
|
+
```
|
|
148
|
+
元のプログラム
|
|
149
|
+
|
|
150
|
+
```ここに言語を入力
|
|
116
151
|
コード
|
|
152
|
+
#include <stdio.h>
|
|
153
|
+
#include <stdlib.h>
|
|
154
|
+
#define V 12
|
|
155
|
+
#define L_IDX 6
|
|
156
|
+
int A[V][V];
|
|
157
|
+
int MV[V];
|
|
158
|
+
int P[V];
|
|
159
|
+
int aug(int, int *);
|
|
160
|
+
|
|
161
|
+
int main(){
|
|
162
|
+
int i, j, p, q;
|
|
163
|
+
int find;
|
|
164
|
+
|
|
165
|
+
for(i=0;i<V;i++){
|
|
166
|
+
for(j=0;j<V;j++){
|
|
167
|
+
A[i][j] = 0;
|
|
168
|
+
}
|
|
169
|
+
}
|
|
170
|
+
/*
|
|
171
|
+
A[0][6] = 1, A[0][7] = 1;
|
|
172
|
+
A[1][6] = 1, A[1][7] = 1;
|
|
173
|
+
A[2][6] = 1, A[2][7] = 1;
|
|
174
|
+
A[3][5] = 1, A[3][6] = 1;
|
|
175
|
+
A[4][5] = 1, A[4][7] = 1, A[4][8] = 1, A[4][9] = 1;
|
|
176
|
+
*/
|
|
177
|
+
A[0][6] = 1, A[0][7] = 1;
|
|
178
|
+
A[1][6] = 1, A[1][7] = 1, A[1][9] = 1;
|
|
179
|
+
A[2][6] = 1, A[2][7] = 1, A[2][8] = 1;
|
|
180
|
+
A[3][8] = 1, A[3][9] = 1, A[3][10] = 1;
|
|
181
|
+
A[4][8] = 1, A[4][9] = 1, A[4][11] = 1;
|
|
182
|
+
A[5][10] = 1, A[5][11] = 1;
|
|
183
|
+
|
|
184
|
+
for(i=0;i<V;i++){MV[i] = 0;}
|
|
185
|
+
|
|
186
|
+
find = 1;
|
|
187
|
+
while(find){
|
|
188
|
+
find = 0;
|
|
189
|
+
for(i=0;i<V;i++){P[i] = 0;}
|
|
190
|
+
|
|
191
|
+
for(i=0;i<L_IDX;i++){
|
|
192
|
+
if(MV[i]==0){
|
|
193
|
+
P[i] = 1;
|
|
194
|
+
find = aug(i,P);
|
|
195
|
+
if(find){
|
|
196
|
+
//***********************************************************
|
|
197
|
+
for(p=L_IDX;p<V;p++){
|
|
198
|
+
for(q=0;q<L_IDX;q++){
|
|
199
|
+
printf("%d ",A[p][q]);
|
|
200
|
+
}
|
|
201
|
+
printf("\n");
|
|
202
|
+
}
|
|
203
|
+
printf("++++++++++++++++++++++++++\n");
|
|
204
|
+
//***********************************************************
|
|
205
|
+
MV[i] = 1;
|
|
206
|
+
break;
|
|
207
|
+
}
|
|
208
|
+
P[i] = 0;
|
|
209
|
+
}
|
|
210
|
+
}
|
|
211
|
+
}
|
|
212
|
+
|
|
213
|
+
for(i=L_IDX;i<V;i++){
|
|
214
|
+
for(j=0;j<L_IDX;j++){
|
|
215
|
+
if(A[i][j]==1){ printf("A[%d][%d]=%d ",i,j,A[i][j]);}
|
|
216
|
+
}
|
|
217
|
+
}
|
|
218
|
+
printf("\n");
|
|
219
|
+
|
|
220
|
+
}
|
|
221
|
+
|
|
222
|
+
int aug(int v, int P[]){
|
|
223
|
+
int i,j,k;
|
|
224
|
+
int find,v1,v2;
|
|
225
|
+
|
|
226
|
+
for(j=0;j<V;j++){
|
|
227
|
+
|
|
228
|
+
if(A[v][j]==1&&P[j]==0){
|
|
229
|
+
P[j] = 1;
|
|
230
|
+
find = aug(j,P);
|
|
231
|
+
if(find==1){ //found augmenting path
|
|
232
|
+
A[v][j] = 0, A[j][v] = 1, MV[j] = 1;
|
|
233
|
+
return(1);
|
|
234
|
+
}
|
|
235
|
+
P[j] = 0;
|
|
236
|
+
}
|
|
237
|
+
|
|
238
|
+
}// end for j
|
|
239
|
+
|
|
240
|
+
if(v>=L_IDX&&MV[v]==0){
|
|
241
|
+
return(1); // found augmenting path
|
|
242
|
+
}else{
|
|
243
|
+
return(0); // could not find augmenting path
|
|
244
|
+
}
|
|
245
|
+
|
|
246
|
+
}
|
|
247
|
+
|
|
248
|
+
```
|
|
117
249
|
```
|
2
少し書き方を修正しました
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -52,20 +52,19 @@
|
|
|
52
52
|
if(MV[i]==0){
|
|
53
53
|
P[i] = 1;
|
|
54
54
|
find = aug(i,P);
|
|
55
|
+
|
|
55
|
-
|
|
56
|
+
if(find){
|
|
56
57
|
//***********************************************************
|
|
57
58
|
|
|
58
59
|
for(p=0;p<V;p++){
|
|
59
|
-
|
|
60
|
+
for(q=0;q<V;q++){
|
|
60
|
-
|
|
61
|
+
if(q%r==0)printf("|");
|
|
61
|
-
//if(p%r==0)printf("-");
|
|
62
|
-
// if(p%r==0)printf("-");
|
|
63
|
-
|
|
62
|
+
printf("%2d",A[q][p]);
|
|
64
|
-
|
|
63
|
+
}
|
|
65
64
|
printf("\n");
|
|
66
|
-
|
|
65
|
+
}
|
|
67
|
-
|
|
66
|
+
printf("+++++++++++++++++++++++++++\n");
|
|
68
|
-
|
|
67
|
+
printf("\n");
|
|
69
68
|
//***********************************************************
|
|
70
69
|
MV[i] = 1;
|
|
71
70
|
break;
|
|
@@ -77,19 +76,17 @@
|
|
|
77
76
|
|
|
78
77
|
for(i=r;i<V;i++){
|
|
79
78
|
for(j=0;j<r;j++){
|
|
80
|
-
if(A[i][j]==1){ printf("A[%d][%d]=%d ",i%6+1,j,A[i][j]);}
|
|
79
|
+
if(A[i][j]==1){ printf("A[%d][%d]=%d ",i%6+1,j,A[i][j]);} //マッチングしてる箇所を表示
|
|
81
80
|
}
|
|
82
81
|
}
|
|
83
82
|
printf("\n");
|
|
84
83
|
|
|
85
|
-
|
|
84
|
+
for(i=r;i<V;i++){
|
|
86
|
-
|
|
85
|
+
for(j=0;j<r;j++){
|
|
87
|
-
if(A[i][j]==1){ printf("%
|
|
86
|
+
if(A[i][j]==1){ printf("%3d",j);//マッチング後を表示
|
|
88
|
-
|
|
89
87
|
}
|
|
88
|
+
}
|
|
90
89
|
}
|
|
91
|
-
}
|
|
92
|
-
|
|
93
90
|
}
|
|
94
91
|
|
|
95
92
|
int aug(int v, int P[]){
|
|
@@ -114,9 +111,7 @@
|
|
|
114
111
|
return(1); // found augmenting path
|
|
115
112
|
}else{
|
|
116
113
|
return(0); // could not find augmenting path
|
|
117
|
-
}
|
|
114
|
+
}
|
|
118
|
-
|
|
119
|
-
|
|
120
115
|
}
|
|
121
116
|
コード
|
|
122
117
|
```
|
1
コードの書き方修正します
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -1,7 +1,10 @@
|
|
|
1
1
|
C言語で2部グラフのマッチングを求めるプログラムを利用してラテン方陣を書きたいのですが、マッチングする行をfor文で回せばいいということがわかるのですが、マッチングしたものを保存して、再度マッチングさせるのがどうすれば上手く行くのかわかりませんでした。プログラムは６×６行列です。またマッチングしたものを最後行列として表示する方法についても悩んでいます。
|
|
2
2
|
下記は１つの２部グラフマッチングを求めるプログラムです。
|
|
3
|
+
教えてくださる方がいたらよろしくお願いします。
|
|
3
4
|
|
|
4
5
|
|
|
6
|
+
|
|
7
|
+
```
|
|
5
8
|
/*２部グラフマッチング*/
|
|
6
9
|
#include <stdio.h>
|
|
7
10
|
#include <stdlib.h>
|
|
@@ -31,7 +34,7 @@
|
|
|
31
34
|
A[3][5] = 1, A[3][6] = 1;
|
|
32
35
|
A[4][5] = 1, A[4][7] = 1, A[4][8] = 1, A[4][9] = 1;
|
|
33
36
|
*/
|
|
34
|
-
A[0][6] = 1, A[0][7] = 1;
|
|
37
|
+
A[0][6] = 1, A[0][7] = 1;
|
|
35
38
|
A[1][6] = 1, A[1][7] = 1, A[1][9] = 1;
|
|
36
39
|
A[2][6] = 1, A[2][7] = 1, A[2][8] = 1;
|
|
37
40
|
A[3][8] = 1, A[3][9] = 1, A[3][10] = 1;
|
|
@@ -41,7 +44,7 @@
|
|
|
41
44
|
for(i=0;i<V;i++){MV[i] = 0;}
|
|
42
45
|
|
|
43
46
|
find = 1;
|
|
44
|
-
while(find){
|
|
47
|
+
while(find){
|
|
45
48
|
find = 0;
|
|
46
49
|
for(i=0;i<V;i++){P[i] = 0;}
|
|
47
50
|
|
|
@@ -114,4 +117,6 @@
|
|
|
114
117
|
}
|
|
115
118
|
|
|
116
119
|
|
|
117
|
-
}
|
|
120
|
+
}
|
|
121
|
+
コード
|
|
122
|
+
```
|