teratail
回答率
85.40%
teratail 10th-anniversary
teratail 10th-anniversary
質問するログイン新規登録
トップに関する質問ハンドルされていない例外への対処方法

編集履歴

質問編集履歴

9

プログラムの訂正、エラー内容を訂正しました。

2021/11/24 13:31

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -42,394 +42,6 @@
42
42
 
43
43
  ```C++
44
44
 
45
- #include <iostream>
46
-
47
- #include <vector>
48
-
49
- #include <algorithm>
50
-
51
- #include <list>
52
-
53
- #include <random>
54
-
55
- #include <queue>
56
-
57
-
58
-
59
- using namespace std;
60
-
61
-
62
-
63
- bool graph[1010][1010];
64
-
65
-
66
-
67
- class con_matrix
68
-
69
- {
70
-
71
- private:
72
-
73
- vector < vector<int>> matrix;
74
-
75
- public:
76
-
77
- con_matrix(int vn, int en) { set_vertex_num(vn, en); }
78
-
79
- void set_vertex_num(int vn, int en)
80
-
81
- {
82
-
83
- matrix.resize(vn); //行列行数を設定
84
-
85
- for (auto& line : matrix)
86
-
87
- line.resize(en); //行列列数を設定
88
-
89
- }
90
-
91
- int get_vertex_num() const { return matrix.size(); }
92
-
93
- int get_edge_num() const { return matrix.at(0).size(); }
94
-
95
-
96
-
97
- void set_random(unsigned int seed = 0) // seed:乱数シード(値を変えると乱数列が変化)
98
-
99
- {
100
-
101
- for (auto& row : matrix)
102
-
103
- {
104
-
105
- for (auto& v : row)
106
-
107
- v = 0; //要素をクリア
108
-
109
- }
110
-
111
-
112
-
113
- int vn = matrix.size(); //頂点数
114
-
115
- int en = matrix.at(0).size(); //辺数
116
-
117
- srand(seed);
118
-
119
- vector<pair<int, int>> es;
120
-
121
- for (int i = 0; i < vn - 1; ++i)
122
-
123
- for (int j = i + 1; j < vn; ++j)
124
-
125
- es.emplace_back(i, j);
126
-
127
- for (int i = 0; i < en; ++i)
128
-
129
- {
130
-
131
- swap(es[i], es[i + rand() % (es.size() - i)]);
132
-
133
- matrix[es[i].first][i] = 1;
134
-
135
- matrix[es[i].second][i] = 1;
136
-
137
- }
138
-
139
- }
140
-
141
-
142
-
143
- void disp_connection() const
144
-
145
- {
146
-
147
- for (auto& row : matrix) {
148
-
149
- for (auto v : row)
150
-
151
- cout << v << " "; //要素を表示
152
-
153
- cout << endl; //行列列数を設定
154
-
155
- }
156
-
157
- }
158
-
159
-
160
-
161
- void Coalescence(vector<int>& ev, int r1, vector<int>& r2) // 取り出した複数の行を一つの行になるよう組合す
162
-
163
- {
164
-
165
- int Vertex = get_vertex_num();
166
-
167
- int Edge = get_edge_num();
168
-
169
- random_shuffle(r2.begin(), r2.end());
170
-
171
- // 行を初期化
172
-
173
- for (int iE = 0; iE < Edge; iE++) {
174
-
175
- ev[iE] = 0;
176
-
177
- }
178
-
179
- for (int iV = 0; iV < r1; iV++) {
180
-
181
- for (int iE = 0; iE < Edge; iE++) {
182
-
183
- if (ev[iE] == 0 && matrix[r2[iV]][iE] == 1) {
184
-
185
- ev[iE] = 1;
186
-
187
- }
188
-
189
- }
190
-
191
- }
192
-
193
- }
194
-
195
- };
196
-
197
-
198
-
199
- // 頂点集合を取り出し、被覆かどうかをチェックする
200
-
201
- int Is_cover(con_matrix a, vector<int>& matrix, vector<int>& r, int r1, vector<int>& r2) {
202
-
203
- int iV = a.get_vertex_num(); // 頂点数
204
-
205
- int iE = a.get_edge_num(); // 辺数
206
-
207
- int num = 0;
208
-
209
- a.Coalescence(matrix,r1,r2);
210
-
211
- for (int i = 0; i < iE; i++) {
212
-
213
- num += matrix[i];
214
-
215
- }
216
-
217
- if (num == iE) {
218
-
219
- return true;
220
-
221
- }
222
-
223
- else return false;
224
-
225
- }
226
-
227
-
228
-
229
- void tabu_add(int num, vector<int>& tabu_list, int tabu_size, int& tabu_last)
230
-
231
- {
232
-
233
- tabu_list[tabu_last] = num;
234
-
235
- tabu_last++;
236
-
237
- if (tabu_last >= tabu_size)
238
-
239
- tabu_last = 0;
240
-
241
- }
242
-
243
-
244
-
245
- int tabu_cheak(int num,vector<int> tabu_list,int tabu_size)
246
-
247
- {
248
-
249
- for (int i = 0; i < tabu_size; i++) {
250
-
251
- if (tabu_list[i] == num)
252
-
253
- return true;
254
-
255
- }
256
-
257
- return false;
258
-
259
- }
260
-
261
-
262
-
263
- // 局所探索法
264
-
265
- void Cover_search(con_matrix a, vector<int>& matrix, vector<int>& tem, int& r1, vector<int>& r2)
266
-
267
- {
268
-
269
- int gm = rand() % (r1 - 1); // 取り出す要素
270
-
271
- sort(tem.begin(), tem.end());
272
-
273
- int x = tem[gm];
274
-
275
- tem.erase(tem.begin() + gm);
276
-
277
- if (Is_cover(a, matrix,tem,r1, r2) == true) {
278
-
279
- cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "true" << endl;
280
-
281
- r1--;
282
-
283
- }
284
-
285
- else if (Is_cover(a, matrix,tem, r1, r2) == false) {
286
-
287
- cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "false" << endl;
288
-
289
- tem.push_back(x);
290
-
291
- }
292
-
293
- }
294
-
295
-
296
-
297
- // タブー探索法
298
-
299
- void Tabu_Cover_search(con_matrix a, vector<int>& matrix, vector<int>& r, int& r1, vector<int>& r2, vector<int>& tabu_list, int& tabu_size,int& tabu_last)
300
-
301
- {
302
-
303
- int gm = rand() % (r1 - 1); // 取り出す要素
304
-
305
- sort(r.begin(), r.end());
306
-
307
- int x = r[gm];
308
-
309
- r.erase(r.begin() + gm);
310
-
311
- if (tabu_cheak(x, tabu_list, tabu_size) == false) {
312
-
313
- if (Is_cover(a, matrix, r, r1, r2) == true) {
314
-
315
- cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "true" << endl;
316
-
317
- r1--;
318
-
319
- }
320
-
321
- else if (Is_cover(a, matrix, r, r1, r2) == false) {
322
-
323
- cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "false" << endl;
324
-
325
- r.push_back(x);
326
-
327
- tabu_add(x, tabu_list, tabu_size, tabu_last);
328
-
329
- }
330
-
331
- }
332
-
333
- else {
334
-
335
- r.push_back(x);
336
-
337
- }
338
-
339
- }
340
-
341
-
342
-
343
- int main(void)
344
-
345
- {
346
-
347
- const int n = 10; //頂点数
348
-
349
- double r = 0.5; //辺数の比率
350
-
351
- const int e = ((n * (n - 1) / 2) * r); //辺数
352
-
353
- int ram1; // 取り出す行の数
354
-
355
- vector <int> tem; // 取り出した行の配列
356
-
357
- vector <int> ram2(n,0); // 取り出される行
358
-
359
- for (int i = 0; i < n; i++) {
360
-
361
- ram2[i] = i;
362
-
363
- }
364
-
365
-
366
-
367
- int search = 100; // 探索回数
368
-
369
- int tabu_size = 10; // タブーサイズ
370
-
371
- vector <int> tabu(tabu_size, -1); // タブーリスト
372
-
373
- int tabu_last = 0; // 今現在のタブーリストの位置
374
-
375
-
376
-
377
- con_matrix M(n, e);
378
-
379
- vector<int> matrix(e, 0); // 組合す行
380
-
381
- M.set_random(1);
382
-
383
- cout << "頂点数 = " << n << endl;
384
-
385
- cout << "グラフの辺数 = " << e << endl;
386
-
387
- //M.disp_connection(); // 接続行列表示
388
-
389
- cout << endl;
390
-
391
-
392
-
393
- for (int i = 0; i < 10; i++) {
394
-
395
- ram1 = rand() % n + 1;
396
-
397
- Is_cover(M, matrix,tem, ram1, ram2);
398
-
399
- if (Is_cover(M, matrix,tem, ram1, ram2) == true) {
400
-
401
- for (int i = 0; i < ram1; i++) {
402
-
403
- tem.push_back(ram2[i]);
404
-
405
- }
406
-
407
- cout << "初期解：" << ram1 << endl;
408
-
409
- cout << endl;
410
-
411
- break;
412
-
413
- }
414
-
415
- }
416
-
417
-
418
-
419
- for (int s = 0; s < search; s++) {
420
-
421
- Cover_search(M, matrix, tem, ram1, ram2);
422
-
423
- // Tabu_Cover_search(M, matrix, tem, ram1, ram2, tabu, tabu_size, tabu_last);
424
-
425
- }
426
-
427
- return 0;
428
-
429
- }
430
-
431
-
432
-
433
45
 
434
46
 
435
47
  ```

8

プログラムとエラー、質問内容の訂正しました。

2021/11/24 13:31

投稿

退会済みユーザー
test CHANGED
@@ -1 +1 @@
1
- どこが原因で実行できないのかわからない
1
+ ハンドルされていない例外への対処方法
test CHANGED
@@ -1,13 +1,5 @@
1
1
  ### 前提・実現したいこと
2
2
 
3
- 入力中の内容をテンプレートとして保存
4
-
5
- プレビュー
6
-
7
- 閉じる
8
-
9
- 他のユーザ
10
-
11
3
  生成した接続行列から行をランダムに取り出し、一つの行に組み合わせる。その後組み合わせた行は被覆しているかをチェックし、結果を「ture」「false」で出力する。
12
4
 
13
5
  出力した後、取り出した行を一つずつ減らしていき最小頂点被覆数を求める。
@@ -36,313 +28,423 @@
36
28
 
37
29
  ### 発生している問題・エラーメッセージ
38
30
 
31
+ 「ハンドルされない例外が 0x7A28FC66 (ucrtbased.dll) で発生しました: 無効なパラメーターを致命的と見なす関数に無効なパラメーターが渡されました」といった内容が出ます。
32
+
33
+
34
+
35
+ ![イメージ説明](73ee4f31c01cc58d27e4c715031bf89a.png)
36
+
37
+
38
+
39
+ ### 該当のソースコード
40
+
41
+
42
+
43
+ ```C++
44
+
45
+ #include <iostream>
46
+
47
+ #include <vector>
48
+
49
+ #include <algorithm>
50
+
51
+ #include <list>
52
+
53
+ #include <random>
54
+
55
+ #include <queue>
56
+
57
+
58
+
59
+ using namespace std;
60
+
61
+
62
+
63
+ bool graph[1010][1010];
64
+
65
+
66
+
67
+ class con_matrix
68
+
69
+ {
70
+
71
+ private:
72
+
73
+ vector < vector<int>> matrix;
74
+
75
+ public:
76
+
77
+ con_matrix(int vn, int en) { set_vertex_num(vn, en); }
78
+
79
+ void set_vertex_num(int vn, int en)
80
+
81
+ {
82
+
83
+ matrix.resize(vn); //行列行数を設定
84
+
85
+ for (auto& line : matrix)
86
+
87
+ line.resize(en); //行列列数を設定
88
+
89
+ }
90
+
91
+ int get_vertex_num() const { return matrix.size(); }
92
+
93
+ int get_edge_num() const { return matrix.at(0).size(); }
94
+
95
+
96
+
97
+ void set_random(unsigned int seed = 0) // seed:乱数シード(値を変えると乱数列が変化)
98
+
99
+ {
100
+
101
+ for (auto& row : matrix)
102
+
103
+ {
104
+
105
+ for (auto& v : row)
106
+
107
+ v = 0; //要素をクリア
108
+
109
+ }
110
+
111
+
112
+
113
+ int vn = matrix.size(); //頂点数
114
+
115
+ int en = matrix.at(0).size(); //辺数
116
+
117
+ srand(seed);
118
+
119
+ vector<pair<int, int>> es;
120
+
121
+ for (int i = 0; i < vn - 1; ++i)
122
+
123
+ for (int j = i + 1; j < vn; ++j)
124
+
125
+ es.emplace_back(i, j);
126
+
127
+ for (int i = 0; i < en; ++i)
128
+
129
+ {
130
+
131
+ swap(es[i], es[i + rand() % (es.size() - i)]);
132
+
133
+ matrix[es[i].first][i] = 1;
134
+
135
+ matrix[es[i].second][i] = 1;
136
+
137
+ }
138
+
139
+ }
140
+
141
+
142
+
143
+ void disp_connection() const
144
+
145
+ {
146
+
147
+ for (auto& row : matrix) {
148
+
149
+ for (auto v : row)
150
+
151
+ cout << v << " "; //要素を表示
152
+
153
+ cout << endl; //行列列数を設定
154
+
155
+ }
156
+
157
+ }
158
+
159
+
160
+
161
+ void Coalescence(vector<int>& ev, int r1, vector<int>& r2) // 取り出した複数の行を一つの行になるよう組合す
162
+
163
+ {
164
+
165
+ int Vertex = get_vertex_num();
166
+
167
+ int Edge = get_edge_num();
168
+
169
+ random_shuffle(r2.begin(), r2.end());
170
+
171
+ // 行を初期化
172
+
173
+ for (int iE = 0; iE < Edge; iE++) {
174
+
175
+ ev[iE] = 0;
176
+
177
+ }
178
+
179
+ for (int iV = 0; iV < r1; iV++) {
180
+
181
+ for (int iE = 0; iE < Edge; iE++) {
182
+
183
+ if (ev[iE] == 0 && matrix[r2[iV]][iE] == 1) {
184
+
185
+ ev[iE] = 1;
186
+
187
+ }
188
+
189
+ }
190
+
191
+ }
192
+
193
+ }
194
+
195
+ };
196
+
197
+
198
+
199
+ // 頂点集合を取り出し、被覆かどうかをチェックする
200
+
201
+ int Is_cover(con_matrix a, vector<int>& matrix, vector<int>& r, int r1, vector<int>& r2) {
202
+
203
+ int iV = a.get_vertex_num(); // 頂点数
204
+
205
+ int iE = a.get_edge_num(); // 辺数
206
+
207
+ int num = 0;
208
+
209
+ a.Coalescence(matrix,r1,r2);
210
+
211
+ for (int i = 0; i < iE; i++) {
212
+
213
+ num += matrix[i];
214
+
215
+ }
216
+
217
+ if (num == iE) {
218
+
219
+ return true;
220
+
221
+ }
222
+
223
+ else return false;
224
+
225
+ }
226
+
227
+
228
+
229
+ void tabu_add(int num, vector<int>& tabu_list, int tabu_size, int& tabu_last)
230
+
231
+ {
232
+
233
+ tabu_list[tabu_last] = num;
234
+
235
+ tabu_last++;
236
+
237
+ if (tabu_last >= tabu_size)
238
+
239
+ tabu_last = 0;
240
+
241
+ }
242
+
243
+
244
+
245
+ int tabu_cheak(int num,vector<int> tabu_list,int tabu_size)
246
+
247
+ {
248
+
249
+ for (int i = 0; i < tabu_size; i++) {
250
+
251
+ if (tabu_list[i] == num)
252
+
253
+ return true;
254
+
255
+ }
256
+
257
+ return false;
258
+
259
+ }
260
+
261
+
262
+
263
+ // 局所探索法
264
+
265
+ void Cover_search(con_matrix a, vector<int>& matrix, vector<int>& tem, int& r1, vector<int>& r2)
266
+
267
+ {
268
+
269
+ int gm = rand() % (r1 - 1); // 取り出す要素
270
+
271
+ sort(tem.begin(), tem.end());
272
+
273
+ int x = tem[gm];
274
+
275
+ tem.erase(tem.begin() + gm);
276
+
277
+ if (Is_cover(a, matrix,tem,r1, r2) == true) {
278
+
279
+ cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "true" << endl;
280
+
281
+ r1--;
282
+
283
+ }
284
+
285
+ else if (Is_cover(a, matrix,tem, r1, r2) == false) {
286
+
287
+ cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "false" << endl;
288
+
289
+ tem.push_back(x);
290
+
291
+ }
292
+
293
+ }
294
+
295
+
296
+
297
+ // タブー探索法
298
+
299
+ void Tabu_Cover_search(con_matrix a, vector<int>& matrix, vector<int>& r, int& r1, vector<int>& r2, vector<int>& tabu_list, int& tabu_size,int& tabu_last)
300
+
301
+ {
302
+
303
+ int gm = rand() % (r1 - 1); // 取り出す要素
304
+
305
+ sort(r.begin(), r.end());
306
+
307
+ int x = r[gm];
308
+
309
+ r.erase(r.begin() + gm);
310
+
311
+ if (tabu_cheak(x, tabu_list, tabu_size) == false) {
312
+
313
+ if (Is_cover(a, matrix, r, r1, r2) == true) {
314
+
315
+ cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "true" << endl;
316
+
317
+ r1--;
318
+
319
+ }
320
+
321
+ else if (Is_cover(a, matrix, r, r1, r2) == false) {
322
+
323
+ cout << "取り出した行：" << x << ",頂点数：" << r1 << "：" << "false" << endl;
324
+
325
+ r.push_back(x);
326
+
327
+ tabu_add(x, tabu_list, tabu_size, tabu_last);
328
+
329
+ }
330
+
331
+ }
332
+
333
+ else {
334
+
335
+ r.push_back(x);
336
+
337
+ }
338
+
339
+ }
340
+
341
+
342
+
343
+ int main(void)
344
+
345
+ {
346
+
347
+ const int n = 10; //頂点数
348
+
349
+ double r = 0.5; //辺数の比率
350
+
351
+ const int e = ((n * (n - 1) / 2) * r); //辺数
352
+
353
+ int ram1; // 取り出す行の数
354
+
355
+ vector <int> tem; // 取り出した行の配列
356
+
357
+ vector <int> ram2(n,0); // 取り出される行
358
+
359
+ for (int i = 0; i < n; i++) {
360
+
361
+ ram2[i] = i;
362
+
363
+ }
364
+
365
+
366
+
367
+ int search = 100; // 探索回数
368
+
369
+ int tabu_size = 10; // タブーサイズ
370
+
371
+ vector <int> tabu(tabu_size, -1); // タブーリスト
372
+
373
+ int tabu_last = 0; // 今現在のタブーリストの位置
374
+
375
+
376
+
377
+ con_matrix M(n, e);
378
+
379
+ vector<int> matrix(e, 0); // 組合す行
380
+
381
+ M.set_random(1);
382
+
383
+ cout << "頂点数 = " << n << endl;
384
+
385
+ cout << "グラフの辺数 = " << e << endl;
386
+
387
+ //M.disp_connection(); // 接続行列表示
388
+
389
+ cout << endl;
390
+
391
+
392
+
393
+ for (int i = 0; i < 10; i++) {
394
+
395
+ ram1 = rand() % n + 1;
396
+
397
+ Is_cover(M, matrix,tem, ram1, ram2);
398
+
399
+ if (Is_cover(M, matrix,tem, ram1, ram2) == true) {
400
+
401
+ for (int i = 0; i < ram1; i++) {
402
+
403
+ tem.push_back(ram2[i]);
404
+
405
+ }
406
+
407
+ cout << "初期解：" << ram1 << endl;
408
+
409
+ cout << endl;
410
+
411
+ break;
412
+
413
+ }
414
+
415
+ }
416
+
417
+
418
+
419
+ for (int s = 0; s < search; s++) {
420
+
421
+ Cover_search(M, matrix, tem, ram1, ram2);
422
+
423
+ // Tabu_Cover_search(M, matrix, tem, ram1, ram2, tabu, tabu_size, tabu_last);
424
+
425
+ }
426
+
427
+ return 0;
428
+
429
+ }
430
+
431
+
432
+
39
433
 
40
434
 
41
435
  ```
42
436
 
437
+
438
+
439
+ ### 試したこと
440
+
43
- エラー内容が表示されないため、何が原因でエラーとなっているのかわからない状態です。
441
+ 以下の内容が115行目のint x = tem[gm];にて出ます。頂点数を10にしてみたり、100にしてみたりすると最後まで探索し実行できるのですが、頂点数を50とかにすると以下の出力をしてエラーが出ます。
44
-
45
- 警告文も特に何も出ていない状態です。
46
442
 
47
443
  ```
48
444
 
49
-
50
-
51
- ### 該当のソースコード
52
-
53
-
54
-
55
- ```C++
56
-
57
- #include <iostream>
58
-
59
- #include <vector>
60
-
61
- #include <algorithm>
62
-
63
- #include <list>
64
-
65
- #include <random>
66
-
67
- #include <queue>
68
-
69
-
70
-
71
- using namespace std;
72
-
73
-
74
-
75
- bool graph[1010][1010];
76
-
77
-
78
-
79
- class con_matrix
80
-
81
- {
82
-
83
- private:
84
-
85
- vector < vector<int>> matrix;
86
-
87
- public:
88
-
89
- con_matrix(int vn, int en) { set_vertex_num(vn, en); }
90
-
91
- void set_vertex_num(int vn, int en)
92
-
93
- {
94
-
95
- matrix.resize(vn); //行列行数を設定
96
-
97
- for (auto& line : matrix)
98
-
99
- line.resize(en); //行列列数を設定
100
-
101
- }
102
-
103
- int get_vertex_num() const { return matrix.size(); }
104
-
105
- int get_edge_num() const { return matrix.at(0).size(); }
106
-
107
-
108
-
109
- void set_random(unsigned int seed = 0) // seed:乱数シード(値を変えると乱数列が変化)
110
-
111
- {
112
-
113
- for (auto& row : matrix)
114
-
115
- {
116
-
117
- for (auto& v : row)
118
-
119
- v = 0; //要素をクリア
120
-
121
- }
122
-
123
-
124
-
125
- int vn = matrix.size(); //頂点数
126
-
127
- int en = matrix.at(0).size(); //辺数
128
-
129
- srand(seed);
130
-
131
- vector<pair<int, int>> es;
132
-
133
- for (int i = 0; i < vn - 1; ++i)
134
-
135
- for (int j = i + 1; j < vn; ++j)
136
-
137
- es.emplace_back(i, j);
138
-
139
- for (int i = 0; i < en; ++i)
140
-
141
- {
142
-
143
- swap(es[i], es[i + rand() % (es.size() - i)]);
144
-
145
- matrix[es[i].first][i] = 1;
146
-
147
- matrix[es[i].second][i] = 1;
148
-
149
- }
150
-
151
- }
152
-
153
-
154
-
155
- void disp_connection() const
156
-
157
- {
158
-
159
- for (auto& row : matrix) {
160
-
161
- for (auto v : row)
162
-
163
- cout << v << " "; //要素を表示
164
-
165
- cout << endl; //行列列数を設定
166
-
167
- }
168
-
169
- }
170
-
171
-
172
-
173
- void Coalescence(vector<int>& ev, vector<int>& r, int r1, vector<int>& r2) // 取り出した複数の行を一つの行になるよう組合す
174
-
175
- {
176
-
177
- int Vertex = get_vertex_num();
178
-
179
- int Edge = get_edge_num();
180
-
181
- random_shuffle(r2.begin(), r2.end());
182
-
183
- // 行を初期化
184
-
185
- for (int iE = 0; iE < Edge; iE++) {
186
-
187
- ev[iE] = 0;
445
+ 頂点数 = 50
188
-
189
- }
446
+
190
-
191
- for (int iV = 0; iV < r1; iV++) {
192
-
193
- r.push_back(r2[iV]);
194
-
195
- for (int iE = 0; iE < Edge; iE++) {
196
-
197
- if (ev[iE] == 0 && matrix[r2[iV]][iE] == 1) {
198
-
199
- ev[iE] = 1;
447
+ グラフの辺数 = 612
200
-
201
- }
202
-
203
- }
204
-
205
- }
206
-
207
- }
208
-
209
- };
210
-
211
-
212
-
213
- // 頂点集合を取り出し、被覆かどうかをチェックする
214
-
215
- int Is_cover(con_matrix a, vector<int> matrix, vector<int> r, int r1, vector<int> r2) {
216
-
217
- int iV = a.get_vertex_num(); // 頂点数
218
-
219
- int iE = a.get_edge_num(); // 辺数
220
-
221
- int num = 0;
222
-
223
- a.Coalescence(matrix,r,r1,r2);
224
-
225
- for (int i = 0; i < iE; i++) {
226
-
227
- num += matrix[i];
228
-
229
- }
230
-
231
- if (num == iE) {
232
-
233
- return true;
234
-
235
- }
236
-
237
- else return false;
238
-
239
- }
240
-
241
-
242
-
243
- void Cover_search(con_matrix a, vector<int>& matrix, vector<int>& r, int ram1, vector<int>& ram2)
244
-
245
- {
246
-
247
- int gm = rand() % (ram1-1);
248
-
249
- int am = r[gm];
250
-
251
- sort(r.begin(), r.end());
252
-
253
- r.erase(r.begin() + gm);
254
-
255
- if (Is_cover(a, matrix, r, ram1, ram2) == true) {
256
-
257
- cout << "取り出した行：" << am << ",頂点数：" << r.size() << "：" << "true" << endl;
258
-
259
- ram1--;
260
-
261
- }
262
-
263
- else if (Is_cover(a, matrix, r, ram1, ram2) == false) {
264
-
265
- cout << "取り出した行：" << am << ",頂点数：" << r.size() << "：" << "false" << endl;
266
-
267
- ram2.push_back(am);
268
-
269
- }
270
-
271
- }
272
-
273
-
274
-
275
- int main(void)
276
-
277
- {
278
-
279
- const int n = 10; //頂点数
280
-
281
- double r = 0.5; //辺数の比率
282
-
283
- const int e = ((n * (n - 1) / 2) * r); //辺数
284
-
285
- int ram1; // 取り出す行の数
286
-
287
- vector <int> ram2(n,0); // 取り出される行
288
-
289
- for (int i = 0; i < n; i++) {
290
-
291
- ram2[i] = i;
292
-
293
- }
294
-
295
- int search = 10; // 探索回数
296
-
297
- con_matrix M(n, e);
298
-
299
- vector<int> matrix(e, 0); // 組合す行
300
-
301
- vector <int> tem;
302
-
303
- M.set_random(1);
304
-
305
- cout << "頂点数 = " << n << endl;
306
-
307
- cout << "グラフの辺数 = " << e << endl;
308
-
309
- //M.disp_connection(); // 接続行列表示
310
-
311
- cout << endl;
312
-
313
-
314
-
315
- for (int i = 0; i < 10; i++) {
316
-
317
- ram1 = rand() % n + 1;
318
-
319
- tem.reserve(ram1);
320
-
321
- Is_cover(M, matrix, tem, ram1, ram2);
322
-
323
- if (Is_cover(M, matrix, tem, ram1, ram2) == true) {
324
-
325
- cout << "初期解：" << ram1 << endl;
326
-
327
- cout << endl;
328
-
329
- break;
330
-
331
- }
332
-
333
- else tem.clear();
334
-
335
- }
336
-
337
- for (int s = 0; s < search; s++) {
338
-
339
- Cover_search(M, matrix, tem, ram1, ram2);
340
-
341
- }
342
-
343
- return 0;
344
-
345
- }
346
448
 
347
449
 
348
450
 
@@ -350,26 +452,6 @@
350
452
 
351
453
 
352
454
 
353
- ### エラー内容と試したこと
354
-
355
- ram2から取り出した行(要素)を入れる配列temを追加し、出力しようと思ったのですが、97行目の int am = r[gm];でエラーが起きます。どのように改善すれば良いか分からない状態です。
356
-
357
- ```
358
-
359
- 頂点数 = 10
360
-
361
- グラフの辺数 = 22
362
-
363
-
364
-
365
- 初期解：9
366
-
367
- ```
368
-
369
- ![イメージ説明](73ee4f31c01cc58d27e4c715031bf89a.png)
370
-
371
-
372
-
373
455
 
374
456
 
375
457
  ### 補足情報（FW/ツールのバージョンなど）

7

プログラムの訂正をしました

2021/11/24 08:17

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -170,7 +170,7 @@
170
170
 
171
171
 
172
172
 
173
- void Coalescence (vector<int>& ev, int r1, vector<int>& r2) // 取り出した複数の行を一つの行になるよう組合す
173
+ void Coalescence(vector<int>& ev, vector<int>& r, int r1, vector<int>& r2) // 取り出した複数の行を一つの行になるよう組合す
174
174
 
175
175
  {
176
176
 
@@ -190,11 +190,11 @@
190
190
 
191
191
  for (int iV = 0; iV < r1; iV++) {
192
192
 
193
- int e = r2[iV];
193
+ r.push_back(r2[iV]);
194
194
 
195
195
  for (int iE = 0; iE < Edge; iE++) {
196
196
 
197
- if (ev[iE] == 0 && matrix[e][iE] == 1) {
197
+ if (ev[iE] == 0 && matrix[r2[iV]][iE] == 1) {
198
198
 
199
199
  ev[iE] = 1;
200
200
 
@@ -212,7 +212,7 @@
212
212
 
213
213
  // 頂点集合を取り出し、被覆かどうかをチェックする
214
214
 
215
- bool Is_cover(con_matrix a, vector<int> matrix, int r1, vector<int>& r2) {
215
+ int Is_cover(con_matrix a, vector<int> matrix, vector<int> r, int r1, vector<int> r2) {
216
216
 
217
217
  int iV = a.get_vertex_num(); // 頂点数
218
218
 
@@ -220,9 +220,7 @@
220
220
 
221
221
  int num = 0;
222
222
 
223
- a.Coalescence(matrix,r1,r2);
223
+ a.Coalescence(matrix,r,r1,r2);
224
-
225
- sort(r2.begin(), r2.end());
226
224
 
227
225
  for (int i = 0; i < iE; i++) {
228
226
 
@@ -242,27 +240,29 @@
242
240
 
243
241
 
244
242
 
245
- void Cover_search(con_matrix a, vector<int>& matrix, int& ram1, vector<int>& ram2)
243
+ void Cover_search(con_matrix a, vector<int>& matrix, vector<int>& r, int ram1, vector<int>& ram2)
246
244
 
247
245
  {
248
246
 
249
247
  int gm = rand() % (ram1-1);
250
248
 
251
- int am = ram2[gm];
249
+ int am = r[gm];
250
+
252
-
251
+ sort(r.begin(), r.end());
252
+
253
- ram2.erase(ram2.begin() + gm);
253
+ r.erase(r.begin() + gm);
254
-
254
+
255
- if (Is_cover(a, matrix, ram1, ram2) == 1) {
255
+ if (Is_cover(a, matrix, r, ram1, ram2) == true) {
256
-
256
+
257
- cout << "true" << endl;
257
+ cout << "取り出した行：" << am << ",頂点数：" << r.size() << "：" << "true" << endl;
258
258
 
259
259
  ram1--;
260
260
 
261
261
  }
262
262
 
263
- else if (Is_cover(a, matrix, ram1, ram2) == 0) {
263
+ else if (Is_cover(a, matrix, r, ram1, ram2) == false) {
264
-
264
+
265
- cout << "false" << endl;
265
+ cout << "取り出した行：" << am << ",頂点数：" << r.size() << "：" << "false" << endl;
266
266
 
267
267
  ram2.push_back(am);
268
268
 
@@ -276,15 +276,15 @@
276
276
 
277
277
  {
278
278
 
279
- const int n = 100; //頂点数
279
+ const int n = 10; //頂点数
280
280
 
281
281
  double r = 0.5; //辺数の比率
282
282
 
283
283
  const int e = ((n * (n - 1) / 2) * r); //辺数
284
284
 
285
- int ram1 = 0; // 取り出す行の数
285
+ int ram1; // 取り出す行の数
286
-
286
+
287
- vector <int> ram2(n,0);
287
+ vector <int> ram2(n,0); // 取り出される行
288
288
 
289
289
  for (int i = 0; i < n; i++) {
290
290
 
@@ -298,7 +298,7 @@
298
298
 
299
299
  vector<int> matrix(e, 0); // 組合す行
300
300
 
301
-
301
+ vector <int> tem;
302
302
 
303
303
  M.set_random(1);
304
304
 
@@ -316,9 +316,11 @@
316
316
 
317
317
  ram1 = rand() % n + 1;
318
318
 
319
+ tem.reserve(ram1);
320
+
319
- Is_cover(M, matrix, ram1, ram2);
321
+ Is_cover(M, matrix, tem, ram1, ram2);
320
-
322
+
321
- if (Is_cover(M, matrix, ram1, ram2) == true) {
323
+ if (Is_cover(M, matrix, tem, ram1, ram2) == true) {
322
324
 
323
325
  cout << "初期解：" << ram1 << endl;
324
326
 
@@ -328,25 +330,13 @@
328
330
 
329
331
  }
330
332
 
333
+ else tem.clear();
334
+
331
335
  }
332
336
 
333
337
  for (int s = 0; s < search; s++) {
334
338
 
335
- cout << ram2.size() << ":";
336
-
337
- Cover_search(M, matrix, ram1, ram2);
339
+ Cover_search(M, matrix, tem, ram1, ram2);
338
-
339
- /*
340
-
341
- for (int j = 0; j < ram1; j++) {
342
-
343
- cout << ram2[j] << ",";
344
-
345
- }
346
-
347
- */
348
-
349
- cout << endl;
350
340
 
351
341
  }
352
342
 
@@ -356,29 +346,23 @@
356
346
 
357
347
 
358
348
 
359
-
360
-
361
349
  ```
362
350
 
363
351
 
364
352
 
365
353
  ### エラー内容と試したこと
366
354
 
367
- 頂点数を10や20にして、探索回数を10回に変更してみるとエラーなく実行できたのですが、頂点数を100にすると以下の実行途中でdebug assertion failedとなっている状態です。
355
+ ram2から取り出した行(要素)を入れる配列temを追加し、出力しようと思ったのですが、97行目の int am = r[gm];でエラーが起きます。どのように改善すれば良いか分からない状態です。
368
-
356
+
369
- ```
357
+ ```
370
-
358
+
371
- 頂点数 = 100
359
+ 頂点数 = 10
372
-
360
+
373
- グラフの辺数 = 2475
361
+ グラフの辺数 = 22
374
-
375
-
376
-
362
+
363
+
364
+
377
- 初期解：100
365
+ 初期解：9
378
-
379
-
380
-
381
- 100:
382
366
 
383
367
  ```
384
368
 

6

プログラムとエラーの訂正をしました。

2021/11/23 17:43

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -212,7 +212,7 @@
212
212
 
213
213
  // 頂点集合を取り出し、被覆かどうかをチェックする
214
214
 
215
- int Is_cover(con_matrix a, vector<int> matrix, int r1, vector<int>& r2) {
215
+ bool Is_cover(con_matrix a, vector<int> matrix, int r1, vector<int>& r2) {
216
216
 
217
217
  int iV = a.get_vertex_num(); // 頂点数
218
218
 
@@ -246,19 +246,97 @@
246
246
 
247
247
  {
248
248
 
249
- int r = ram1 - 1;
250
-
251
249
  int gm = rand() % (ram1-1);
252
250
 
253
251
  int am = ram2[gm];
254
252
 
255
253
  ram2.erase(ram2.begin() + gm);
256
254
 
255
+ if (Is_cover(a, matrix, ram1, ram2) == 1) {
256
+
257
+ cout << "true" << endl;
258
+
257
- ram1--;
259
+ ram1--;
260
+
258
-
261
+ }
262
+
263
+ else if (Is_cover(a, matrix, ram1, ram2) == 0) {
264
+
265
+ cout << "false" << endl;
266
+
267
+ ram2.push_back(am);
268
+
269
+ }
270
+
271
+ }
272
+
273
+
274
+
275
+ int main(void)
276
+
277
+ {
278
+
279
+ const int n = 100; //頂点数
280
+
281
+ double r = 0.5; //辺数の比率
282
+
283
+ const int e = ((n * (n - 1) / 2) * r); //辺数
284
+
285
+ int ram1 = 0; // 取り出す行の数
286
+
287
+ vector <int> ram2(n,0);
288
+
289
+ for (int i = 0; i < n; i++) {
290
+
291
+ ram2[i] = i;
292
+
293
+ }
294
+
295
+ int search = 10; // 探索回数
296
+
297
+ con_matrix M(n, e);
298
+
299
+ vector<int> matrix(e, 0); // 組合す行
300
+
301
+
302
+
303
+ M.set_random(1);
304
+
305
+ cout << "頂点数 = " << n << endl;
306
+
307
+ cout << "グラフの辺数 = " << e << endl;
308
+
309
+ //M.disp_connection(); // 接続行列表示
310
+
311
+ cout << endl;
312
+
313
+
314
+
315
+ for (int i = 0; i < 10; i++) {
316
+
317
+ ram1 = rand() % n + 1;
318
+
319
+ Is_cover(M, matrix, ram1, ram2);
320
+
321
+ if (Is_cover(M, matrix, ram1, ram2) == true) {
322
+
323
+ cout << "初期解：" << ram1 << endl;
324
+
325
+ cout << endl;
326
+
327
+ break;
328
+
329
+ }
330
+
331
+ }
332
+
333
+ for (int s = 0; s < search; s++) {
334
+
335
+ cout << ram2.size() << ":";
336
+
337
+ Cover_search(M, matrix, ram1, ram2);
338
+
259
- /*
339
+ /*
260
-
261
- if (Is_cover(a, matrix, ram1, ram2) == true) {
262
340
 
263
341
  for (int j = 0; j < ram1; j++) {
264
342
 
@@ -266,110 +344,18 @@
266
344
 
267
345
  }
268
346
 
347
+ */
348
+
269
- cout << "true" << endl;
349
+ cout << endl;
270
-
271
- ram1--;
350
+
272
-
273
- }
351
+ }
274
-
275
- else if (Is_cover(a, matrix, ram1, ram2) == false) {
352
+
276
-
277
- cout << "false" << endl;
278
-
279
- ram2.push_back(am);
280
-
281
- }
282
-
283
- */
353
+ return 0;
284
354
 
285
355
  }
286
356
 
287
357
 
288
358
 
289
- int main(void)
290
-
291
- {
292
-
293
- const int n = 10; //頂点数
294
-
295
- double r = 0.5; //辺数の比率
296
-
297
- const int e = ((n * (n - 1) / 2) * r); //辺数
298
-
299
- int ram1 = 0; // 取り出す行の数
300
-
301
- vector <int> ram2(n,0);
302
-
303
- for (int i = 0; i < n; i++) {
304
-
305
- ram2[i] = i;
306
-
307
- }
308
-
309
- int search = 5; // 探索回数
310
-
311
- con_matrix M(n, e);
312
-
313
- vector<int> matrix(e, 0); // 組合す行
314
-
315
-
316
-
317
- M.set_random(1);
318
-
319
- cout << "頂点数 = " << n << endl;
320
-
321
- cout << "グラフの辺数 = " << e << endl;
322
-
323
- //M.disp_connection(); // 接続行列表示
324
-
325
- cout << endl;
326
-
327
-
328
-
329
- for (int i = 0; i < 10; i++) {
330
-
331
- ram1 = rand() % n + 1;
332
-
333
- Is_cover(M, matrix, ram1, ram2);
334
-
335
- if (Is_cover(M, matrix, ram1, ram2) == true) {
336
-
337
- cout << "初期解：" << ram1 << endl;
338
-
339
- for (int j = 0; j < ram1; j++) {
340
-
341
- cout << ram2[j] << ",";
342
-
343
- }
344
-
345
- cout << endl;
346
-
347
- break;
348
-
349
- }
350
-
351
- }
352
-
353
- for (int s = 0; s < 5; s++) {
354
-
355
- Cover_search(M, matrix, ram1, ram2);
356
-
357
- for (int j = 0; j < ram1; j++) {
358
-
359
- cout << ram2[j] << ",";
360
-
361
- }
362
-
363
- cout << endl;
364
-
365
- }
366
-
367
- return 0;
368
-
369
- }
370
-
371
-
372
-
373
359
 
374
360
 
375
361
  ```
@@ -378,21 +364,21 @@
378
364
 
379
365
  ### エラー内容と試したこと
380
366
 
381
- どの部分でエラーとなっているのかを調べるために、プログラムの部分部分を消して実行してみているのですが、以下の実行途中でdebug assertion failedとなっている状態です。
367
+ 頂点数を10や20にして、探索回数を10回に変更してみるとエラーなく実行できたのですが、頂点数を100にすると以下の実行途中でdebug assertion failedとなっている状態です。
382
-
383
- またmain文内のCover_search()を配列の要素を減らすのみにすると問題なく実行はできています。
368
+
384
-
385
- ```
369
+ ```
386
-
370
+
387
- 頂点数 = 7
371
+ 頂点数 = 100
388
-
372
+
389
- グラフの辺数 = 10
373
+ グラフの辺数 = 2475
390
-
391
-
392
-
374
+
375
+
376
+
393
- 初期解：7
377
+ 初期解：100
394
-
378
+
379
+
380
+
395
- 0,1,2,3,4,5,6,
381
+ 100:
396
382
 
397
383
  ```
398
384
 

5

プログラムを訂正しました。

2021/11/22 08:09

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -178,6 +178,8 @@
178
178
 
179
179
  int Edge = get_edge_num();
180
180
 
181
+ random_shuffle(r2.begin(), r2.end());
182
+
181
183
  // 行を初期化
182
184
 
183
185
  for (int iE = 0; iE < Edge; iE++) {
@@ -210,7 +212,7 @@
210
212
 
211
213
  // 頂点集合を取り出し、被覆かどうかをチェックする
212
214
 
213
- int Is_cover(con_matrix a, vector<int>& matrix, int ram1, vector<int>& ram2) {
215
+ int Is_cover(con_matrix a, vector<int> matrix, int r1, vector<int>& r2) {
214
216
 
215
217
  int iV = a.get_vertex_num(); // 頂点数
216
218
 
@@ -218,7 +220,9 @@
218
220
 
219
221
  int num = 0;
220
222
 
221
- a.Coalescence(matrix,ram1,ram2);
223
+ a.Coalescence(matrix,r1,r2);
224
+
225
+ sort(r2.begin(), r2.end());
222
226
 
223
227
  for (int i = 0; i < iE; i++) {
224
228
 
@@ -238,19 +242,117 @@
238
242
 
239
243
 
240
244
 
241
- void Cover_search(con_matrix a, vector<int> matrix, int ram1, vector<int> ram2)
245
+ void Cover_search(con_matrix a, vector<int>& matrix, int& ram1, vector<int>& ram2)
242
246
 
243
247
  {
244
248
 
249
+ int r = ram1 - 1;
250
+
251
+ int gm = rand() % (ram1-1);
252
+
253
+ int am = ram2[gm];
254
+
255
+ ram2.erase(ram2.begin() + gm);
256
+
257
+ ram1--;
258
+
259
+ /*
260
+
261
+ if (Is_cover(a, matrix, ram1, ram2) == true) {
262
+
263
+ for (int j = 0; j < ram1; j++) {
264
+
265
+ cout << ram2[j] << ",";
266
+
267
+ }
268
+
269
+ cout << "true" << endl;
270
+
271
+ ram1--;
272
+
273
+ }
274
+
275
+ else if (Is_cover(a, matrix, ram1, ram2) == false) {
276
+
277
+ cout << "false" << endl;
278
+
279
+ ram2.push_back(am);
280
+
281
+ }
282
+
283
+ */
284
+
285
+ }
286
+
287
+
288
+
289
+ int main(void)
290
+
291
+ {
292
+
293
+ const int n = 10; //頂点数
294
+
295
+ double r = 0.5; //辺数の比率
296
+
297
+ const int e = ((n * (n - 1) / 2) * r); //辺数
298
+
299
+ int ram1 = 0; // 取り出す行の数
300
+
245
- vector<int> x(ram2);
301
+ vector <int> ram2(n,0);
302
+
303
+ for (int i = 0; i < n; i++) {
304
+
305
+ ram2[i] = i;
306
+
307
+ }
308
+
309
+ int search = 5; // 探索回数
310
+
311
+ con_matrix M(n, e);
312
+
313
+ vector<int> matrix(e, 0); // 組合す行
314
+
315
+
316
+
317
+ M.set_random(1);
318
+
319
+ cout << "頂点数 = " << n << endl;
320
+
321
+ cout << "グラフの辺数 = " << e << endl;
322
+
323
+ //M.disp_connection(); // 接続行列表示
324
+
325
+ cout << endl;
326
+
327
+
246
328
 
247
329
  for (int i = 0; i < 10; i++) {
248
330
 
249
- int gm = rand() % ram1 + 1;
331
+ ram1 = rand() % n + 1;
250
-
251
- int am = ram2[gm];
332
+
252
-
253
- ram2.erase(ram2.begin() + gm);
333
+ Is_cover(M, matrix, ram1, ram2);
334
+
335
+ if (Is_cover(M, matrix, ram1, ram2) == true) {
336
+
337
+ cout << "初期解：" << ram1 << endl;
338
+
339
+ for (int j = 0; j < ram1; j++) {
340
+
341
+ cout << ram2[j] << ",";
342
+
343
+ }
344
+
345
+ cout << endl;
346
+
347
+ break;
348
+
349
+ }
350
+
351
+ }
352
+
353
+ for (int s = 0; s < 5; s++) {
354
+
355
+ Cover_search(M, matrix, ram1, ram2);
254
356
 
255
357
  for (int j = 0; j < ram1; j++) {
256
358
 
@@ -260,94 +362,14 @@
260
362
 
261
363
  cout << endl;
262
364
 
263
- if (Is_cover(a, matrix, ram1, ram2) == true) {
264
-
265
- cout << "true" << endl;
266
-
267
- ram1--;
268
-
269
- }
365
+ }
270
-
271
- else if (Is_cover(a, matrix, ram1, ram2) == false) {
366
+
272
-
273
- std::cout << "false" << endl;
274
-
275
- ram2.push_back(am);
367
+ return 0;
276
-
277
- }
278
-
279
- }
280
368
 
281
369
  }
282
370
 
283
371
 
284
372
 
285
- int main(void)
286
-
287
- {
288
-
289
- const int n = 7; //頂点数
290
-
291
- double r = 0.5; //辺数の比率
292
-
293
- const int e = ((n * (n - 1) / 2) * r); //辺数
294
-
295
- int ram1 = rand() % n + 1; // 取り出す行の数
296
-
297
- vector <int> ram2(n,0);
298
-
299
- for (int i = 0; i < n; i++) {
300
-
301
- ram2[i] = i;
302
-
303
- }
304
-
305
- int search = 10; // 探索回数
306
-
307
- con_matrix M(n, e);
308
-
309
- vector<int> matrix(e, 0); // 組合す行
310
-
311
-
312
-
313
- M.set_random(1);
314
-
315
- random_shuffle(ram2.begin(), ram2.end());
316
-
317
- cout << endl;
318
-
319
- cout << "頂点数 = " << n << endl;
320
-
321
- cout << "グラフの辺数 = " << e << endl;
322
-
323
- //M.disp_connection(); // 接続行列表示
324
-
325
- cout << endl;
326
-
327
-
328
-
329
- for (int i = 0; i < n; i++) {
330
-
331
- Is_cover(M, matrix, ram1, ram2);
332
-
333
- if (Is_cover(M, matrix, ram1, ram2) == true) {
334
-
335
- cout << "初期解：" << ram1 << endl;
336
-
337
- break;
338
-
339
- }
340
-
341
- }
342
-
343
- Cover_search(M, matrix, ram1, ram2);
344
-
345
- return 0;
346
-
347
- }
348
-
349
-
350
-
351
373
 
352
374
 
353
375
  ```
@@ -358,7 +380,7 @@
358
380
 
359
381
  どの部分でエラーとなっているのかを調べるために、プログラムの部分部分を消して実行してみているのですが、以下の実行途中でdebug assertion failedとなっている状態です。
360
382
 
361
- またmain文内のCover_search()を消すと問題なく実行はできています。
383
+ またmain文内のCover_search()を配列の要素を減らすのみにすると問題なく実行はできています。
362
384
 
363
385
  ```
364
386
 

4

debug assertion failedの内容を足しました

2021/11/22 07:26

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -1,6 +1,12 @@
1
1
  ### 前提・実現したいこと
2
2
 
3
-
3
+ 入力中の内容をテンプレートとして保存
4
+
5
+ プレビュー
6
+
7
+ 閉じる
8
+
9
+ 他のユーザ
4
10
 
5
11
  生成した接続行列から行をランダムに取り出し、一つの行に組み合わせる。その後組み合わせた行は被覆しているかをチェックし、結果を「ture」「false」で出力する。
6
12
 
@@ -368,6 +374,8 @@
368
374
 
369
375
  ```
370
376
 
377
+ ![イメージ説明](73ee4f31c01cc58d27e4c715031bf89a.png)
378
+
371
379
 
372
380
 
373
381
 

3

エラー内容の詳細を加えました。

2021/11/22 03:48

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -348,9 +348,29 @@
348
348
 
349
349
 
350
350
 
351
- ### 試したこと
351
+ ### エラー内容と試したこと
352
-
352
+
353
- エラーどの部分でエラーとなっているのかを調べるために、プログラムの部分部分を消して実行してみているのですが、同じ結果となって分からない状態です。
353
+ どの部分でエラーとなっているのかを調べるために、プログラムの部分部分を消して実行してみているのですが、以下の実行途中でdebug assertion failedとなっている状態です。
354
+
355
+ またmain文内のCover_search()を消すと問題なく実行はできています。
356
+
357
+ ```
358
+
359
+ 頂点数 = 7
360
+
361
+ グラフの辺数 = 10
362
+
363
+
364
+
365
+ 初期解：7
366
+
367
+ 0,1,2,3,4,5,6,
368
+
369
+ ```
370
+
371
+
372
+
373
+
354
374
 
355
375
  ### 補足情報（FW/ツールのバージョンなど）
356
376
 

2

質問内容、プログラム内容を訂正しました。

2021/11/22 02:33

投稿

退会済みユーザー
test CHANGED
@@ -1 +1 @@
1
- 頂点被覆であるかチェックし、結果を出力したい。
1
+ どこが原因で実行できないのかわからない
test CHANGED
@@ -4,6 +4,8 @@
4
4
 
5
5
  生成した接続行列から行をランダムに取り出し、一つの行に組み合わせる。その後組み合わせた行は被覆しているかをチェックし、結果を「ture」「false」で出力する。
6
6
 
7
+ 出力した後、取り出した行を一つずつ減らしていき最小頂点被覆数を求める。
8
+
7
9
  ```
8
10
 
9
11
  0 0 0 0 0 0 1 1 1 1
@@ -162,23 +164,31 @@
162
164
 
163
165
 
164
166
 
165
- void Coalescence (int* ev, int* r) // 取り出した複数の行を一つの行になるよう組合す
167
+ void Coalescence (vector<int>& ev, int r1, vector<int>& r2) // 取り出した複数の行を一つの行になるよう組合す
166
168
 
167
169
  {
168
170
 
171
+ int Vertex = get_vertex_num();
172
+
169
173
  int Edge = get_edge_num();
170
174
 
171
- int Vertex = get_vertex_num();
175
+ // 行を初期化
172
-
176
+
173
- for (int i = 0; i < Vertex; i++) {
177
+ for (int iE = 0; iE < Edge; iE++) {
178
+
174
-
179
+ ev[iE] = 0;
180
+
181
+ }
182
+
183
+ for (int iV = 0; iV < r1; iV++) {
184
+
175
- int e = r[i];
185
+ int e = r2[iV];
176
-
186
+
177
- for (int v = 0; v < Edge; v++) {
187
+ for (int iE = 0; iE < Edge; iE++) {
178
-
188
+
179
- if (ev[v] == 0 && matrix[v][e] == 1) {
189
+ if (ev[iE] == 0 && matrix[e][iE] == 1) {
180
-
190
+
181
- ev[v] = 1;
191
+ ev[iE] = 1;
182
192
 
183
193
  }
184
194
 
@@ -192,21 +202,73 @@
192
202
 
193
203
 
194
204
 
205
+ // 頂点集合を取り出し、被覆かどうかをチェックする
206
+
207
+ int Is_cover(con_matrix a, vector<int>& matrix, int ram1, vector<int>& ram2) {
208
+
209
+ int iV = a.get_vertex_num(); // 頂点数
210
+
211
+ int iE = a.get_edge_num(); // 辺数
212
+
213
+ int num = 0;
214
+
215
+ a.Coalescence(matrix,ram1,ram2);
216
+
195
- void random_shuffle(int* ary, int size)
217
+ for (int i = 0; i < iE; i++) {
218
+
219
+ num += matrix[i];
220
+
221
+ }
222
+
223
+ if (num == iE) {
224
+
225
+ return true;
226
+
227
+ }
228
+
229
+ else return false;
230
+
231
+ }
232
+
233
+
234
+
235
+ void Cover_search(con_matrix a, vector<int> matrix, int ram1, vector<int> ram2)
196
236
 
197
237
  {
198
238
 
239
+ vector<int> x(ram2);
240
+
199
- for (int i = 0; i < size; i++)
241
+ for (int i = 0; i < 10; i++) {
200
-
201
- {
242
+
202
-
203
- int j = rand() % size;
243
+ int gm = rand() % ram1 + 1;
204
-
244
+
205
- int t = ary[i];
245
+ int am = ram2[gm];
246
+
206
-
247
+ ram2.erase(ram2.begin() + gm);
248
+
249
+ for (int j = 0; j < ram1; j++) {
250
+
251
+ cout << ram2[j] << ",";
252
+
253
+ }
254
+
255
+ cout << endl;
256
+
257
+ if (Is_cover(a, matrix, ram1, ram2) == true) {
258
+
259
+ cout << "true" << endl;
260
+
261
+ ram1--;
262
+
263
+ }
264
+
265
+ else if (Is_cover(a, matrix, ram1, ram2) == false) {
266
+
267
+ std::cout << "false" << endl;
268
+
207
- ary[i] = ary[j];
269
+ ram2.push_back(am);
208
-
270
+
209
- ary[j] = t;
271
+ }
210
272
 
211
273
  }
212
274
 
@@ -214,23 +276,19 @@
214
276
 
215
277
 
216
278
 
217
- // 頂点集合を取り出し、被覆かどうかをチェックする
218
-
219
- void Is_cover(con_matrix a,int* matrix) {
279
+ int main(void)
280
+
220
-
281
+ {
282
+
221
- int e = a.get_vertex_num(); // 頂点数
283
+ const int n = 7; //頂点数
222
-
284
+
223
- int n = a.get_edge_num(); // 辺数
285
+ double r = 0.5; //辺数の比率
286
+
224
-
287
+ const int e = ((n * (n - 1) / 2) * r); //辺数
225
-
226
-
288
+
227
- int ram1 = rand() % e + 1; // 取り出す行の数
289
+ int ram1 = rand() % n + 1; // 取り出す行の数
228
-
229
- cout << "頂点数：" << ram1 << endl;
290
+
230
-
231
- int* ram2 = new int[n];
291
+ vector <int> ram2(n,0);
232
-
233
- int num = 0;
234
292
 
235
293
  for (int i = 0; i < n; i++) {
236
294
 
@@ -238,76 +296,52 @@
238
296
 
239
297
  }
240
298
 
299
+ int search = 10; // 探索回数
300
+
301
+ con_matrix M(n, e);
302
+
303
+ vector<int> matrix(e, 0); // 組合す行
304
+
305
+
306
+
307
+ M.set_random(1);
308
+
241
- random_shuffle(ram2,e);
309
+ random_shuffle(ram2.begin(), ram2.end());
242
-
243
-
244
-
310
+
245
- a.Coalescence(matrix,ram2);
311
+ cout << endl;
312
+
246
-
313
+ cout << "頂点数 = " << n << endl;
314
+
315
+ cout << "グラフの辺数 = " << e << endl;
316
+
317
+ //M.disp_connection(); // 接続行列表示
318
+
319
+ cout << endl;
320
+
321
+
322
+
247
- for (int i = 0; i < ram1; i++) {
323
+ for (int i = 0; i < n; i++) {
248
-
324
+
249
- num += matrix[i];
325
+ Is_cover(M, matrix, ram1, ram2);
326
+
250
-
327
+ if (Is_cover(M, matrix, ram1, ram2) == true) {
328
+
329
+ cout << "初期解：" << ram1 << endl;
330
+
331
+ break;
332
+
251
- }
333
+ }
252
-
253
- if (num < n) {
334
+
254
-
255
- cout << "false" << endl;
256
-
257
- }
335
+ }
258
-
336
+
259
- else { cout << "true" << endl; }
337
+ Cover_search(M, matrix, ram1, ram2);
338
+
339
+ return 0;
260
340
 
261
341
  }
262
342
 
263
343
 
264
344
 
265
- int main(void)
266
-
267
- {
268
-
269
- const int n = 5; //頂点数
270
-
271
- double r = 0.5; //辺数の比率
272
-
273
- const int e = ((n * (n - 1) / 2) * r); //辺数
274
-
275
- con_matrix M(n, e);
276
-
277
- int* matrix = new int [n];
278
-
279
- for (int i = 0; i < n; i++) {
280
-
281
- matrix[i] = 0;
282
-
283
- }
284
-
285
-
286
-
287
- M.set_random(1);
288
-
289
- cout << endl;
290
-
291
- cout << "頂点数 = " << n << endl;
292
-
293
- cout << "グラフの辺数 = " << e << endl;
294
-
295
- M.disp_connection();
296
-
297
- cout << endl;
298
-
299
- for (int i = 0; i < 10; i++) {
300
-
301
- Is_cover(M, matrix);
302
-
303
- i++;
304
-
305
- }
306
-
307
- return 0;
308
-
309
- }
310
-
311
345
 
312
346
 
313
347
  ```
@@ -316,11 +350,7 @@
316
350
 
317
351
  ### 試したこと
318
352
 
319
-
320
-
321
- 頂点数を5個にしてみると最後まで出力されたのですが、頂点数を10個や7個にすると最後まで出力されず、謎のエラーで止まってしまいます。
353
+ エラーどの部分でエラーとなっているのかを調べるために、プログラムの部分部分を消して実行してみているのですが、同じ結果となって分からない状態です。
322
-
323
-
324
354
 
325
355
  ### 補足情報（FW/ツールのバージョンなど）
326
356
 

1

エラー内容を訂正しました。

2021/11/21 03:18

投稿

退会済みユーザー
test CHANGED
File without changes
test CHANGED
@@ -34,7 +34,7 @@
34
34
 
35
35
  エラー内容が表示されないため、何が原因でエラーとなっているのかわからない状態です。
36
36
 
37
- 警告文として
37
+ 警告文も特に何も出ていない状態です。
38
38
 
39
39
  ```
40
40