有权重的无向图最大割

如图所示,现有无向图G=(V,E)。
设U是V的一个子集。对任意的顶点u,v: 如果(u,v)这条边属于E的一条边,此时u在U中,那么v一定不在U中,这样的边就称为顶点集合U的一个割边,所有的割边集合将集合V分成了两个顶点子集合。顶点集合U对应的所有的割边就构成图G的一个割。
最大割就是指含割边最多的割。

下图为这个无向图G的一个最大割,u集合为{1,6,8,9},v集合为{2,3,4,5,7,10},cut为8:

编程要求及思路

数据输入

第一行2个整数 n,e表示顶点个数和边个数。
第二行开始对应的数据分别为: 点1 点2 边(顶点编号从1-n)

上图G所对应的输入文件: simple.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10 14
1 8 1
2 4 1
2 6 1
2 9 1
2 10 -1
4 8 1
4 10 -1
5 8 1
5 9 1
5 10 -1
6 9 1
6 10 1
9 7 1
10 1 1

数据输出

第一行是最大割的边数。
第二行是顶点集的向量对应1-n,0表示不在集合,1表示在集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vertex number:10
edge number:14
each edge:
1 8 1
2 4 1
2 6 1
2 9 1
2 10 -1
4 8 1
4 10 -1
5 8 1
5 9 1
5 10 -1
6 9 1
6 10 1
9 7 1
10 1 1
maxcut is: 8
1 0 1 1 1 1 1 0 0 0

解题思想 (BFS)

这道题也是一个子集选取问题,所以它的解空间树是一个子集树。
**这个集合n个元素,每个元素可以有选取或不选取2种选择,所以共用2^n个子集。**这里用分支界限法。

分支界限法:类似宽度优先搜索,它每次都取一个节点,然后把它的所有的子节点都扩展,然后加到队列中,所以说,分支界限法,这种扩展方式导致每个节点每次最多一次扩展机会,它在扩展它的分支的时候,根据一定的界限条件,或淘汰不可能产生最优解的分支。

在这里我们用优先级队列(priority queue) + 分支界限法进行编程:

  1. 建立一个HeapNode的结构体,重载operator < 让节点在优先队列中按照cut值从大到小排序。
  2. 建立头结点,初始头结点的深度depth = 0, cut = 0, edges = e;
  3. 初始继承头结点,将depth = 0的结点放入割集,将所有与其构成边的权重加入cut。将其压入优先级队列。
  4. 将满足界限条件的E也压入优先级队列。
  5. 从优先级队列中取出top结点设为E,从depth+1开始重复上述过程。
  6. 直到depth == 点数,将最优割和割集放入bestcut中。(queue中所有的node都会测试到depth == 点数为止)

代码实现(BFS)

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
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int n,e,w=0; //顶点数和边数,总权重
int Graph[200][200]; //存储图的邻接矩阵
int bestcut = 0; //存储最优解
int bestx[200]; //存储最优解
struct HeapNode //队列节点
{
int dep;
int cut;
int edges;
int x[200];

HeapNode()
{
memset(x,0,sizeof(x));
}

bool operator < (const HeapNode&a)const
{
return cut<a.cut; //从大到小排序
}
};

void maxcut()
{
HeapNode E; //根节点
priority_queue<HeapNode> Q;
E.cut = 0;
E.edges = w;
E.i = 0;

while (1)
{
if (E.dep == n)
{
if (E.cut > bestcut)
{
bestcut = E.cut;
memcpy(bestx, E.x, sizeof(int)*n);
}
}
else
{
HeapNode temp = E;
int depth = E.dep;

for (int j = 0; j < n; j++)
{
if (Graph[depth][j])
{
if (temp.x[j])
{
temp.cut -= Graph[depth][j];
}
else
{
temp.cut += Graph[depth][j];
temp.edges -= Graph[depth][j];
}
}

}

temp.x[depth] =1;
temp.dep++;
Q.push(temp);

if(E.cut + E.edges > bestcut) //界限条件(在E的前提下,如果加上剩余的edge权重能好过bestcut,则深度加一并且push到优先队列中)
{
E.dep++;
Q.push(E);
}
}
if(Q.size()==0) //队列为空跳出循环
{
break;
}

E = Q.top(); //选取cut最大的node操作
Q.pop();
}
}


int main()
{
ifstream fin("simple.txt"); //输入文件
cout << "vertex number:";
fin >> n; cout << n;
cout << "\nedge number:";
fin >> e; cout << e;
cout << "\neach edge:\n";

int a, b, c, i;
for(i=0; i<e; i++)
{
fin >> a >> b >> c;
w += c;
Graph[a-1][b-1] = Graph[b-1][a-1] = c; //将线段权重存储在邻接矩阵中
cout << a << " " << b << " " << c << endl;
}

maxcut();
cout << "maxcut is: " << bestcut << endl; //输出最大割

for (int k = 0; k < n; k++)
{
cout << bestx[k] << " ";
}
cout << endl;
return 0;
}

解题思想 (Genetic Algorithm)

遗传算法理论:

遗传算法(英语:genetic algorithm (GA) )是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等等。

遗传算法模拟了达尔文的自然选择,这意味着一个人口要想生存就必须不断地自我完善。 最好的个体应该通过其健身价值来激发后代。。对于一个最优化问题,一定数量的候选解(称为个体)可抽象表示为染色体,使种群向更好的解进化。传统上,解用二进制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中评价整个种群的适应度,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。

遗传算法步骤:

1)产生初始种群
2)获取第一人口的健身价值并记录最佳个体
3)通过适应性选择父母,并从选定的父母中抚养孩子,变异新一代的基因(基因的交叉和变异)
4)更新新人群的适应度并记录最佳个人
5)新一代换代(基因的交叉和变异)

遗传算法的结构:

1)基因型结构:int cut, float fitness(适应度), int gene[1000]
2)染色体设计:设置整数类型顶点数数组,0表示不属于集合S,1表示属于集合S。
3)选择:使用适应度值随机生成父索引
4)交叉:从0到顶点之间随机选择一个数字,将父母基因以此索引为基准分开,然后将父母基因重组成为子代基因。
5)突变:使用突变率改变基因,如果基因为1,则将其更改为0,如果基因为0,则将其更改为1。

代码实现(Genetic Algorithm)

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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <string>
#include <string.h>
using namespace std;

#define VertexMaxSize 1000
#define EdgeMaxSize 10000
#define PopulationSize 120 // Number of population
#define CrossoverRate 0.9 // Probablity of crossover
#define MutateRate 0.2 // Probablity of mutation
#define ReplaceRate 0.5 // Probablity of replacement

int vertex, edges; // vertex, edge
int bestcut = 0; // store the best cut value of population
int worstcut = 0; // store the worst cut value of population
float allFit = 0;
int limitCut;
int timeStamp = 5;
string filename = "maxcut.in"; //input file's name
struct Edge
{
int startIndex;
int endIndex;
int weight;
};

struct Genotype
{
int cut; // Cut value
float fitness; // Fi = (Cw-Ci) + (Cw-Cb)/(k-1)
int gene[VertexMaxSize]; // store points which belongs to S set

Genotype()
{
memset(gene, 0, sizeof(gene));
}

void printGene()
{
ofstream SaveFile("maxcut.out");
for (int i = 0; i < vertex; i++)
{
if (gene[i] == 1)
SaveFile << i+1 << " ";
}
SaveFile << endl;
SaveFile.close();
}
};
Genotype best;

struct Genotype population[PopulationSize + 1];
struct Genotype newpopulation[PopulationSize + 1];
struct Edge edgelist[EdgeMaxSize + 1];

void randomSet(int index);
void initial(string filename);
int calCut(Genotype GT);
float calFit(Genotype GT);
void crossover(Genotype *P1, Genotype *P2, Genotype *C1, Genotype *C2);
int selectIndex(Genotype Pop[PopulationSize + 1]);
void mutation(int index, float mRate);
void replace();
void localSearch(int range);
void maxcut();
void UpdateGroupValue();


void randomSet(int index)
{
int num = rand() % 3;
population[index].gene[0] = 1;

if (num == 0)
{
for (int j = 1; j < vertex; j++)
{
int temp = rand() % 10;
if (temp < 3)
{
population[index].gene[j] = 1; // generate random number
}
else
{
population[index].gene[j] = 0; // generate random number
}
}
}

if (num == 1)
{
for (int j = 1; j < vertex; j++)
{
int temp = rand() % 10;
if (temp < 5)
{
population[index].gene[j] = 1; // generate random number
}
else
{
population[index].gene[j] = 0; // generate random number
}
}
}

if (num == 2)
{
for (int j = 1; j < vertex; j++)
{
int temp = rand() % 10;
if (temp < 7)
{
population[index].gene[j] = 1; // generate random number
}
else
{
population[index].gene[j] = 0; // generate random number
}
}
}

population[index].cut = calCut(population[index]);
}

// Initialize the vertex number, edge number through input file.
// Store every edge into the edgelist
// Random generate PopulationSize Genotype's gene array
// Calculate each Genotype's cut
// Record the best cut and worst cut
// Calculate each Genotype's fitness value
void initial(string filename)
{
int temp1, temp2, temp3;
ifstream input;
input.open(filename.c_str());
srand((unsigned)time(NULL));

if (!input) // File check
{
cout << "Can not read input file, please check the input filename again\n";
exit(1);
}

input >> vertex >> edges;
cout << "vertex is :" << vertex << endl;
cout << "edge is :" << edges << endl;

if (vertex < 2) //Vertex number check
cout << "Can not crossover, please modify vertex number bigger than 2" << endl;

//Store each edge's weight into edgelist
for (int i = 0; i < edges; i++)
{
input >> temp1 >> temp2 >> temp3;
edgelist[i].startIndex = temp1 - 1;
edgelist[i].endIndex = temp2 - 1;
edgelist[i].weight = temp3;
}

/*initialize each genotype's fitness and cut*/
for (int i = 0; i < PopulationSize; i++)
{
randomSet(i);

if (i == 0)
{
if (population[i].cut < 0)
bestcut = 0;
else
{
bestcut = population[i].cut;
best = population[i];
}
}

// Set best cut and worst cut in loop
else
{
if (population[i].cut > bestcut)
{
bestcut = population[i].cut;
best = population[i];
}
if (population[i].cut < worstcut)
worstcut = population[i].cut;
}
// localSearch(i);
}

UpdateGroupValue();

cout << endl;
cout << "Initial Generation: bestcut is: " << bestcut << endl;
}

void localSearch(int index)
{
int cut;
int array[VertexMaxSize];
for (int i = 0; i < vertex; i++)
{
array[i] = i;
}
for (int i = 0; i < vertex/2; i++)
{
int temp1 = rand() % vertex;
int temp2 = rand() % vertex;
if (temp1 != temp2)
{
int temp = array[temp1];
array[temp1] = array[temp2];
array[temp2] = temp;
}
}

for (int i = 0; i < vertex; i++)
{
population[index].gene[array[i]] = 1 - population[index].gene[array[i]];
cut = calCut(population[index]);
if (cut > population[index].cut)
{
if (cut > bestcut)
{
bestcut = cut;
best = population[index];
cout << "From local search: best cut is: " << bestcut << endl;
best.printGene();
}
population[index].cut = cut;
}
else
{
population[index].gene[array[i]] = 1 - population[index].gene[array[i]];
}
}
}

int calCut(Genotype GT)
{
int cutValue = 0, index1, index2;
for (int i = 0; i < edges; i++)
{
index1 = edgelist[i].startIndex;
index2 = edgelist[i].endIndex;
if (GT.gene[index1] != GT.gene[index2])
{
cutValue += edgelist[i].weight;
}
}
return cutValue;
}

float calFit(Genotype GT)
{
float result;
float fixedValue = 1.0 * (worstcut - bestcut) / (PopulationSize - 1);
result = (worstcut - GT.cut) + fixedValue;
return result;
}

void crossover(Genotype *P1, Genotype *P2, Genotype *C1, Genotype *C2)
{
int sum = 0, temp;
int num = rand() % vertex;

for (int i = 0; i < num; i++) // new child
{
C1->gene[i] = P1->gene[i];
C2->gene[i] = P2->gene[i];
}
for (int i = num; i < vertex; i++)
{
C1->gene[i] = P2->gene[i];
C2->gene[i] = P1->gene[i];
}
C1->cut = calCut(*C1);
C2->cut = calCut(*C2);
}

int selectIndex(Genotype Pop[PopulationSize + 1])
{
int sum = 0;
int ranNum = -rand() % (int)(allFit);

for (int i = 0; i < PopulationSize; i++)
{
if (sum < ranNum)
{
return i;
}
sum += Pop[i].fitness;
}
return PopulationSize - 1;
}

void UpdateGroupValue()
{
allFit = 0; //reset allfit
for (int i = 0; i < PopulationSize; i++)
{
if (i == 0)
{
worstcut = population[i].cut;
}
else
{
if(population[i].cut < worstcut)
worstcut = population[i].cut;
}
population[i].fitness = calFit(population[i]);
allFit = allFit + population[i].fitness;
}
}

void mutation(int index, float mRate) //mutationRate = 1, delete bad mutation individual
{
int num = mRate * 100;
for (int k = 0; k < vertex; k++)
{
if (rand() % 100 < num)
{
population[index].gene[k] = 1 - population[index].gene[k];
int cut = calCut(population[index]);
if (bestcut < cut)
{
int dec = rand()%100;
if(dec < 98)
{
bestcut = cut;
best = population[index];
population[index].cut = cut;
cout << "From mutation: best cut is: " << bestcut << endl;
best.printGene();
}
else{
population[index].gene[k] = 1 - population[index].gene[k];
}
}
else
{
if (population[index].cut < cut) {
population[index].cut = cut;
}
else {
population[index].gene[k] = 1 - population[index].gene[k];
}
}
}
}
}

void replace()
{
int choose = rand()%3;
int cutList[PopulationSize];
int limit;
for (int i = 0; i < PopulationSize; i++)
{
cutList[i] = population[i].cut;
}

sort(cutList, cutList + PopulationSize);
limit = (int)(PopulationSize * (ReplaceRate + 0.1 * choose));
for (int i = 0; i < PopulationSize; i++)
{
if (population[i].cut < cutList[limit])
{
randomSet(i);
}
}

}

void maxcut()
{
clock_t cstart, cend;
int sIndex, eIndex;
float sFit, eFit;
cstart = clock();
while (1)
{
cend = clock();
if (cend - cstart > 180 * CLOCKS_PER_SEC) //end in 3 min
{
cout << "bestcut is "<<bestcut<<endl;
break;
}
for (int i = 0; i < PopulationSize/2; i++)
{
sIndex = selectIndex(population);
eIndex = selectIndex(population);
memcpy(newpopulation, population, sizeof(Genotype)*(PopulationSize + 1));
// if (rand() % 10 < 8) //crossoverRate = 0.8
{
// population crossover
crossover(&population[sIndex], &population[eIndex], &newpopulation[sIndex], &newpopulation[eIndex]);
if (newpopulation[sIndex].cut > population[sIndex].cut || newpopulation[sIndex].cut > population[eIndex].cut)
{
if(population[sIndex].cut > population[eIndex].cut)
memcpy(&population[eIndex], &newpopulation[sIndex], sizeof(Genotype));
else
memcpy(&population[sIndex], &newpopulation[sIndex], sizeof(Genotype));
}
if (newpopulation[eIndex].cut > population[sIndex].cut || newpopulation[eIndex].cut > population[eIndex].cut)
{
if(population[sIndex].cut > population[eIndex].cut)
memcpy(&population[eIndex], &newpopulation[eIndex], sizeof(Genotype));
else
memcpy(&population[sIndex], &newpopulation[eIndex], sizeof(Genotype));
}
}

if (bestcut < newpopulation[sIndex].cut || bestcut < newpopulation[eIndex].cut) {
if (newpopulation[eIndex].cut > newpopulation[sIndex].cut) {
bestcut = newpopulation[eIndex].cut;
best = newpopulation[eIndex];
}
else
{
bestcut = newpopulation[sIndex].cut;
best = newpopulation[sIndex];
}

cout << "From crossover: best cut is: " << bestcut << endl;
// best.printGene();
}
}
for (int i = 0; i < PopulationSize; i++)
{
mutation(i, MutateRate);
}
int aa = (int)(cend - cstart);
int now = aa/CLOCKS_PER_SEC;
if (now >= timeStamp) //end in 3 min
{
cout << "restart" << endl;
replace();
timeStamp = timeStamp + 3;
}
else
{
for (int i = 0; i < PopulationSize; i++)
{
localSearch(i);
}
}
UpdateGroupValue();
}
cout << "3 min finish" << endl;
}

int main()
{
clock_t cstart, cend;
initial(filename);
maxcut();
getchar();
getchar();
return 0;
}

Linux下运行C++程序

  1. 新建一个文件夹,添加simple.txt和maxcut.cpp
  2. 运行命令 g++ -o exe maxcut.cpp
  3. 确认文件夹中生成exe文件后,运行命令 ./exe