2018算法设计期中项目

题目描述

 Suppose there are n facilities and m customers. We wish
to choose:

 (1) which of the n facilities to open

 (2) the assignment of customers to facilities

 The objective is to minimize the sum of the opening cost
and the assignment cost.

 The total demand assigned to a facility must not exceed
its capacity.

Example:

upload successful
upload successful

题目分析

  这道题目的意思是有多个工厂和消费者，要找到一个组合，使得能够服务所有的客户，并且消耗最少，约束为工厂有一定的容量，一个工厂不能容纳过多的客户，而且客户到不同工厂的消耗也是不一样的。因此这个题目需要我们找到最优近似解。

解题思路

  这道题我想的是既然是一个NPhard的问题，那么就使用搜索去寻找接近最优的解，而这和最近做的TSP问题十分地相似，TSP问题是寻找最短的路径，那么也可以用到这一个题目上，只要弄好数据结构，即解的表示方法，就可以使用几种搜索方法：邻域搜索，模拟退火，遗传算法。

  初始解可以随机也可以使用贪心策略来进行初始化解。

数据结构

  已知有工厂，客户这两个类型，所以做成一个解，把客户的消耗表放在工厂这个类型里，因为给出的数据集是每一个工厂对应的客户的消耗。

  工厂类存储对应服务的客户id以及他们的消耗表。客户类仅需存储demand判断是否超过工厂容量即可，为了之后的方便查询，也存放工厂的id，便于最后的输出。

upload successful
upload successful
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class facility {
	int id = 0;
	int opencost = 0;
	int capacity = 0;
	int allcost = 0;
	Vector<Integer> clients;
	Vector<Integer> cost;
···

public class customer {
	int id = 0;
	int demand = 0;
	int fid = -1;
···

模拟退火

算法介绍

  模拟退火是邻域搜索的一种改进的方法，在邻域搜索上加上了温度这一元素，两重循环，这里我用的是外层温度下降，内层达到热平衡的循环，内层循环进行邻域解的搜索，在搜索到差解的时候，也有一定概率会接受，但是随着温度逐渐下降，接受差解的概率也会逐渐减少，最后收敛。

  模拟退火的主要作用就是跳出局部最小值，因为达到局部最小时，因为步幅过小，导致无法跳出局部解，最后使得只能达到局部最优。所以要跳出局部最优，只能接受差解，到达另一个局部最优，这样逐步能接近全局最优，并且在最后接受差解概率变低，使得能够达到最优的解。

算法代码

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
public void search() {
	times *= 1.01;
    int t = times;
    while (t != 0) {
        Random rand = new Random();
        int fpos1 = rand.nextInt(fnum);
        int fpos2 = rand.nextInt(fnum);
        if (fpos1 == fpos2 || !facilities[fpos1].isOpened()) {
            continue;
        }
        facility facility1 = facilities[fpos1];
        facility facility2 = facilities[fpos2];
        Vector<Integer>client1 = facility1.getClient();
        int cpos1 = rand.nextInt(client1.size());
        int cid = client1.get(cpos1);
        customer customer1 = customers[client1.get(cpos1)];
        
        double newcost = getCost();
        if(facility2.getCapacity() > customer1.getDemand()) {
        	newcost -= facility1.getCostTo(customer1.getId());
        	newcost += facility2.getCostTo(customer1.getId());
        }else {
        	continue;
        }

        double offset = newcost - getCost();
        if (offset <= 0 || Math.pow(E, -offset * 1.0 / temperature) >= Math.random()) {
        	facilities[fpos1].removeClient(customer1);
        	facilities[fpos2].addClient(customer1);
        	customers[cid].setfid(fpos2);
        }
        t--;
        cost = getCost();
    }
}

遗传算法

算法介绍

  遗传算法是利用种群的优势，让优势解能够将基因遗传下来，得到更好的解，发挥种群的优胜劣汰的准则，同时因为交叉得到的解有更好的效果。到后期则需要一些变异来防止其收敛过慢，增大扰动，促进算法的进行。

  遗传算法主要是表示种群里的个体的基因，对每一个个体进行评价，然后采用轮盘法来筛选交配的父代，由父代基因交换来生成子代，这里使用的是交叉基因，采用基因映射的方法来解决冲突，最后再给子代进行突变，这样就能形成新的解。

  1. 初始解：一般建议先使用贪心来获得初始。
  2. 循环迭代：
    • 评价：评价个体确定适应值
    • 选择：根据适应积累值，采用多种方法选择作为交配的父代
    • 交配：有概率地交换基因片段，产生子代。
    • 变异：子代有一定概率发生变异。

基因编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Genome
{
public:
 
	 friend class GenAlg;
	 friend class GenEngine;
 
	 Genome():fitness(0){}
		
     Genome(vector <double> vec, double f): vecGenome(vec), fitness(f){} //初始化参数。
private:
	 vector <facility[]> vecGenome;  // 装载基因的容器
	
	 double fitness; //适应度
 
};

算法代码

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
public void GASearch() {
	int generation = 0;
	init();
	while(generation < maxgen) {
		assess();
		select();
		crossover();
		mutate();
		generation ++;
		population.removeAllElements();
		population.addAll(newpopulation);
		System.out.println("此时最佳消耗为：" + getCost(population.get(bestsolve)) + 
				"适应度为 " + bestfitness);
	}
}

   //选择交配个体
private void select() {
	newpopulation.removeAllElements();
	for(int i = 0; i < population.size(); i++) {
		Random rand = new Random();
		double p = rand.nextInt(1000)/1000.0;
		
		if(p<liveper[0]) {
			int[] temp = new int[count];
			copyArray(temp,population.get(0));
			newpopulation.add(temp);
		}else {
			for(int j = 0; j < population.size(); j++) {
				if(p >= liveper[j] && p < liveper[j+1]) {
					int[] temp = new int[count];
					copyArray(temp,population.get(j+1));
					newpopulation.add(temp);
				}
			}
		}
	}
}

   //进行交配
private void crossover() {
	int first = 0; // 被选择的个数。
	int one = 0;
	for(int i = 0; i< newpopulation.size(); i++) {
		Random rand = new Random();
		double p = rand.nextInt(1000)/1000.0;
		if(p < PXOVER)
		{
			first++;
			if(first%2 == 0) {
				Xover(one,i);
			}else {
				one = i;
			}
		}
	}
}

//进行染色体互换
private void Xover(int one, int two) {
	Random rand = new Random();
	int point1 = rand.nextInt(count);
	int point2 = rand.nextInt(count);
	
	//选择交换点
	if(point1>point2) {
		int temp = point1;
		point1 = point2;
		point2 = temp;
	}
	int[] child1 = new int[count];
	int[] child2 = new int[count];
	copyArray(child1, newpopulation.get(one));
	copyArray(child2, newpopulation.get(two));
	
	//交换基因片段
	for(int i = point1; i < point2; i++) {
		child1[i] = newpopulation.get(two)[i];
		child2[i] = newpopulation.get(one)[i];
	}
	
	//解决子代冲突
	for(int i = 0; i< point1;i++) {
		//替换冲突的为父代对应位置的基因
		for(int j = point1; j < point2; j++) {
			if(child1[i] == child1[j]) {
				child1[i] = newpopulation.get(one)[j];
				j = point1 - 1;
			}
		}
	}
	
	for(int i = 0; i< point1;i++) {
		//替换冲突的为父代对应位置的基因
		for(int j = point1; j < point2; j++) {
			if(child2[i] == child2[j]) {
				child2[i] = newpopulation.get(two)[j];
				j = point1 - 1;
			}
		}
	}
	
	for(int i = point2; i<count;i++) {
		for(int j = point1; j < point2; j++) {
			if(child1[i] == child1[j]) {
				child1[i] = newpopulation.get(one)[j];
				j = point1 - 1;
			}
		}
	}
	
	for(int i = point2; i<count;i++) {
		for(int j = point1; j < point2; j++) {
			if(child2[i] == child2[j]) {
				child2[i] = newpopulation.get(two)[j];
				j = point1 - 1;
			}
		}
	}
	newpopulation.remove(one);
	newpopulation.insertElementAt(child1, one);
	newpopulation.remove(two);
	newpopulation.insertElementAt(child2, two);
}


//子代发生变异
private void mutate() {
	for(int i = 0; i < newpopulation.size(); i++) {
		Random rand = new Random();
		double p = rand.nextInt(1000)/1000.0;
		if(p < PMUTATION) {
            int pos1 = rand.nextInt(count);
            int pos2 = rand.nextInt(count);

            if (pos1 > pos2) {
                int temp = pos1;
                pos1 = pos2;
                pos2 = temp;
            }
            
            if (pos1 == pos2 || (pos1 == 0 && pos2 == count - 1)) {
                continue;
            }
            
               while (pos1 < pos2) {
                   int temPoint = newpopulation.get(i)[pos1];
                   newpopulation.get(i)[pos1] = newpopulation.get(i)[pos2];
                   newpopulation.get(i)[pos2] = temPoint;
                   pos1++;
                   pos2--;
               }
		}
	}
}

Result table

Result Time(ms)
p1 9145.0 220ms
p2 7942.0 104ms
p3 9913.0 150ms
p4 11526.0 156ms
p5 9173.0 140ms
p6 7855.0 161ms
p7 9577.0 123ms
p8 11899.0 120ms
p9 8976.0 130ms
p10 7726.0 120ms
p11 9703.0 76ms
p12 11391.0 41ms
p13 10747.0 163ms
p14 8163.0 297ms
p15 11277.0 130ms
p16 13855.0 169ms
p17 9896.0 230ms
p18 8250.0 240ms
p19 11337.0 250ms
p20 13175.0 261ms
p21 9876.0 193ms
p22 8181.0 286ms
p23 10599.0 221ms
p24 13547.0 89ms
p25 12679.0 1550ms
p26 11534.0 130ms
p27 13373.0 360ms
p28 15498.0 244ms
p29 13957.0 1227ms
p30 12166.0 378ms
p31 14788.0 1485ms
p32 18028.0 117ms
p33 12721.0 1509ms
p34 11424.0 313ms
p35 13901.0 241ms
p36 16488.0 710ms
p37 12212.0 1347ms
p38 11418.0 269ms
p39 13515.0 564ms
p40 15230.0 346ms
p41 7104.0 104ms
p42 8150.0 196ms
p43 9158.0 374ms
p44 7154.0 110ms
p45 8567.0 210ms
p46 9275.0 348ms
p47 6312.0 49ms
p48 7307.0 173ms
p49 8632.0 356ms
p50 9109.0 124ms
p51 8683.0 457ms
p52 9290.0 93ms
p53 9512.0 539ms
p54 9227.0 171ms
p55 9005.0 446ms
p56 23882.0 130ms
p57 32882.0 244ms
p58 52762.0 106ms
p59 39121.0 30ms
p60 23882.0 140ms
p61 32882.0 144ms
p62 53321.0 86ms
p63 39121.0 230ms
p64 23882.0 244ms
p65 32882.0 180ms
p66 52949.0 180ms
p68 23882.0 178ms
p69 32882.0 162ms
p70 53203.0 286ms
p71 38648.0 235ms

Detailed solution

9119.0
1 1 1 1 1 1 1 0 1 1
8 2 1 6 3 8 2 4 4 1 9 0 3 2 8 3 4 0 9 4 3 4 6 4 2 6 1 5 0 5 2 6 0 3 4 4 4 3 0 4 3 8 1 5 4 0 9 0 2 0

7957.0
1 1 1 1 1 1 1 1 1 1
8 2 1 6 3 8 2 4 4 1 9 0 3 2 8 3 4 0 9 7 3 4 6 4 2 5 1 5 0 5 2 6 0 3 4 4 4 3 0 4 1 8 1 6 7 0 4 0 4 0

9897.0
1 1 1 1 1 0 1 1 1 1
8 2 1 6 3 8 2 4 4 1 9 8 3 2 0 3 4 0 9 7 3 4 6 4 2 6 1 6 0 1 6 6 0 3 4 4 4 3 0 4 2 8 1 6 7 0 4 0 4 0

12005.0
1 1 1 1 1 1 1 1 1 1
0 2 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 3

9175.0
1 1 1 1 1 1 1 1 1 1
8 8 1 6 1 8 2 4 4 1 9 8 0 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 2 0 7 3

7873.0
1 1 1 1 1 1 1 1 1 1
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 2 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 6 7 0 9 3 4 0

9899.0
1 1 1 1 1 1 1 1 1 1
8 2 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 8 4 1 8 1 5 7 0 9 0 7 0

11855.0
1 1 1 1 1 1 1 1 1 1
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 2 3 7 0

8928.0
1 1 1 1 1 0 1 1 1 1
8 8 1 6 3 8 2 4 4 1 9 8 0 2 8 3 2 0 9 7 3 8 6 4 2 6 1 1 0 1 2 6 0 3 9 4 4 3 0 4 3 8 1 6 7 0 2 0 4 0

7726.0
1 1 1 1 1 1 1 1 1 1
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0

9726.0
1 1 1 1 1 1 1 1 1 1
8 8 1 6 3 8 2 4 4 1 9 8 3 2 8 3 4 0 9 7 3 8 6 4 2 5 1 5 0 5 2 6 0 3 9 4 4 3 0 4 1 8 1 5 7 0 4 0 4 0

11587.0
1 1 1 1 1 1 1 0 1 1
8 8 1 6 3 8 2 4 4 1 9 8 0 2 8 3 2 0 9 4 3 8 6 4 2 5 1 5 8 5 4 6 0 3 4 4 4 3 0 4 5 8 3 5 4 0 2 0 4 0

10350.0
1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1
16 12 10 10 12 15 17 13 12 17 7 19 19 10 13 3 15 10 17 9 12 15 15 19 9 17 0 17 1 17 13 7 13 16 3 10 11 19 19 13 9 0 0 7 8 13 14 10 19 9

8340.0
1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1
16 14 10 10 19 15 17 13 14 17 15 19 19 10 13 3 15 10 17 9 14 15 15 19 6 17 0 17 1 17 13 7 13 16 3 10 11 1 19 13 6 0 0 0 8 15 14 10 19 9

10865.0
1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1
16 3 10 10 19 13 17 2 14 17 15 19 19 6 13 3 15 10 4 9 14 15 15 19 6 17 16 17 17 17 13 14 2 16 3 10 17 19 19 13 6 0 15 15 9 13 14 10 19 9

13502.0
1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1
0 17 10 10 19 19 17 13 14 17 15 19 19 6 13 3 15 10 4 9 14 15 7 19 6 17 0 17 1 17 13 7 19 0 3 10 3 19 19 13 14 0 15 0 6 13 14 6 19 9

9598.0
1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1
16 1 10 10 1 15 17 13 14 17 15 4 1 6 13 3 15 10 4 9 14 15 15 19 6 1 16 17 1 17 13 15 13 16 3 10 3 19 19 13 10 0 0 0 3 15 14 10 19 9

8152.0
1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1
0 3 10 10 19 18 17 13 14 17 15 4 19 6 13 3 15 10 4 9 14 15 15 19 6 17 16 17 3 17 13 7 13 16 3 10 11 19 19 13 6 0 0 0 11 15 14 10 19 9

11267.0
1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1
0 12 10 10 1 15 17 13 12 17 15 19 1 6 13 3 15 10 4 9 12 15 7 19 6 17 0 17 3 17 13 7 13 0 3 10 3 19 19 19 9 0 0 7 8 13 12 10 19 9

13513.0
1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1
16 1 16 10 1 19 17 13 14 17 15 19 1 10 13 11 15 6 4 9 15 15 15 19 6 1 16 17 1 17 13 15 19 16 1 10 11 19 19 13 6 0 15 16 11 13 14 10 19 9

10423.0
1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1
16 1 10 10 1 13 17 13 14 17 14 4 1 10 13 3 15 10 4 9 14 15 15 19 10 17 16 17 1 17 13 14 13 0 3 10 3 19 19 13 6 0 0 16 8 0 14 10 4 9

8152.0
1 1 0 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 1 1
0 14 10 10 1 18 17 13 14 17 15 19 1 10 13 14 15 10 17 9 14 15 15 19 6 17 0 17 19 17 13 0 13 0 3 10 11 1 19 13 6 0 0 0 3 15 14 10 19 9

10946.0
1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1
0 3 10 10 1 18 17 13 14 17 15 19 1 10 13 3 15 10 17 6 14 15 15 19 6 17 16 17 3 17 13 15 13 16 19 10 11 19 19 13 6 0 0 0 6 15 14 6 19 6

13985.0
1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1
16 1 10 10 1 18 17 13 14 17 7 1 19 10 13 11 15 10 17 6 14 15 15 19 6 17 0 17 1 17 13 7 18 0 1 10 11 19 19 13 10 0 0 7 9 15 14 10 19 9

12567.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 11 20 14 20 5 2 24 14 17 24 20 8 20 0 14 14 17 5 11 2 0 24 0 24 8 2 24 5 24 5 25 20 25 20 20 24 15 11 14 0 14 15 8 24 14 11 20 11 8 11 14 14 5 20 20 17 11 11 14 0 5 20 11 11 11 24 0 5 24 20 20 11 0 24 8 24 20 14 24 20 0 20 17 2 17 17 0 20 5 2 24 17 11 0 5 2 14 0 8 8 0 17 0 2 25 17 11 14 8 14 14 2 11 11 25 24 15 5 24 5 8 25 20 20 11 5 24 0 5 0 11 24 25 20 14 0 5 20 17 0 8 20 14 8 25 25 5 2 5

11402.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0
20 11 20 14 8 5 2 24 14 17 24 20 20 20 0 14 14 17 11 11 14 0 24 2 5 8 2 24 5 24 5 11 20 0 20 20 24 24 11 14 0 8 15 20 24 14 5 20 11 8 5 14 14 5 20 20 17 5 0 14 0 5 20 11 11 0 24 0 11 5 8 20 11 17 24 8 24 20 14 24 20 0 20 17 0 17 0 11 20 5 2 24 0 11 0 5 2 0 0 8 14 0 17 11 2 5 0 11 14 8 14 14 2 11 11 11 24 24 24 24 5 14 11 20 20 17 5 24 11 5 0 11 24 0 20 14 11 5 20 17 0 8 20 14 8 11 11 5 2 5

13410.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0
20 11 20 14 20 5 0 24 11 17 5 14 20 20 2 14 17 0 5 11 14 17 24 0 24 20 2 24 24 24 11 11 20 5 20 20 24 24 0 14 0 8 24 20 24 14 0 20 0 14 5 14 14 5 20 20 14 17 17 14 0 5 20 11 11 11 24 0 5 24 20 20 5 0 24 20 24 20 0 24 20 11 20 17 0 17 2 0 20 11 2 24 0 11 17 5 2 11 11 8 20 2 17 11 2 11 2 11 8 14 14 14 2 11 11 5 24 24 5 24 5 20 11 20 20 11 5 24 0 11 0 17 24 5 8 14 0 5 20 17 0 8 20 14 8 0 0 5 2 5

16049.0
1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 25 20 2 20 5 14 24 14 17 5 8 20 20 0 14 14 17 5 11 14 0 5 17 25 20 2 24 24 24 25 11 8 11 20 20 24 24 0 14 0 14 24 14 24 14 11 20 11 8 11 14 14 5 20 20 17 25 0 14 0 24 20 0 0 11 24 0 24 24 20 20 11 0 24 20 24 20 14 5 20 0 20 17 2 17 2 0 20 5 2 24 0 11 0 5 2 14 25 13 20 0 17 25 2 11 0 11 14 8 14 14 2 11 11 11 24 24 24 24 5 8 11 13 20 0 5 5 0 11 0 0 24 24 20 14 0 5 20 17 0 8 20 14 8 25 25 5 2 5

14091.0
1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0
13 11 13 2 13 5 2 24 8 17 25 8 8 20 17 14 14 17 5 11 2 0 22 0 22 8 2 24 5 22 5 25 13 11 20 20 24 15 0 14 0 14 15 14 24 14 0 13 11 8 11 14 14 5 20 20 17 25 0 14 0 5 20 0 11 11 24 0 22 22 13 13 11 17 24 8 24 20 2 24 20 0 20 17 2 17 17 0 20 5 2 24 17 11 0 24 2 8 25 8 8 17 17 25 2 25 17 11 14 28 14 14 2 11 11 25 24 24 5 24 5 8 25 13 13 17 5 15 0 11 0 25 24 5 8 14 17 5 20 17 0 8 20 14 8 25 25 5 2 5

12068.0
1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 11 20 2 8 5 2 24 14 17 5 20 8 20 17 14 14 17 25 11 2 17 5 0 9 8 17 24 24 9 5 11 13 25 20 20 24 24 0 14 0 14 15 8 24 14 0 20 11 8 25 2 14 5 13 20 17 11 11 14 0 5 20 11 11 11 9 0 9 24 13 13 11 17 24 8 24 20 2 9 20 17 8 17 2 17 17 0 20 5 2 24 17 0 2 24 2 14 25 8 14 0 17 25 2 25 0 11 14 8 14 14 2 11 11 5 24 24 5 24 5 8 25 20 8 0 5 9 0 25 0 0 24 11 8 14 17 5 20 17 0 8 20 14 8 25 25 5 2 5

14841.0
1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
13 25 20 2 8 5 2 24 14 17 24 20 8 20 17 14 17 17 25 11 14 0 0 0 25 8 2 24 24 9 25 25 8 25 20 20 24 15 0 14 0 14 15 8 24 14 25 13 25 8 0 8 14 5 13 20 17 11 11 14 0 5 20 11 11 11 5 0 25 9 13 13 11 17 24 8 9 20 14 5 13 0 13 17 0 17 17 11 20 5 2 24 17 11 17 5 2 11 5 13 8 17 17 11 2 25 0 0 14 8 14 14 2 11 25 11 24 24 24 24 5 13 11 20 13 0 5 15 17 5 0 11 24 24 8 14 0 11 20 17 0 8 20 14 8 25 11 5 2 5

16580.0
1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 11 13 2 20 5 2 24 2 17 5 20 8 20 0 14 14 17 25 11 2 0 15 2 5 8 2 24 5 24 5 25 13 25 20 20 24 15 0 14 0 14 15 8 24 14 17 13 11 8 5 14 14 5 20 20 17 11 11 14 0 5 20 0 0 11 24 0 5 5 8 20 11 0 24 8 15 20 14 24 13 0 13 17 2 17 17 17 20 11 2 24 17 25 17 5 2 11 25 8 8 17 17 25 2 25 17 0 14 8 14 2 2 11 11 25 24 24 24 24 5 8 25 20 8 17 5 15 11 11 0 0 24 25 8 14 11 5 20 17 0 8 20 14 8 25 25 5 2 5

13090.0
1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0
20 11 20 2 20 5 2 24 14 17 24 8 8 20 17 14 14 17 5 11 2 0 5 17 5 8 2 24 5 24 5 25 6 25 20 20 24 15 0 14 0 14 15 8 24 14 0 20 11 8 5 14 14 5 20 20 17 11 11 14 0 5 20 11 11 11 24 0 5 5 20 6 11 17 24 8 24 20 14 24 20 0 20 17 17 17 17 17 20 5 2 24 17 11 17 5 2 14 25 8 8 17 17 25 2 25 17 11 14 28 14 14 2 11 11 25 24 15 24 24 5 8 25 20 8 0 5 24 0 25 0 11 24 5 8 14 17 5 20 17 0 8 20 14 8 11 25 5 2 5

11648.0
1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0
20 11 8 2 8 5 14 24 14 17 5 16 8 20 17 14 14 17 5 11 2 0 5 0 5 8 2 24 5 24 11 11 13 11 20 20 24 24 17 14 0 14 24 8 24 14 11 20 11 8 11 14 14 5 20 20 17 11 0 14 0 5 20 11 11 11 5 0 11 5 8 20 11 17 24 8 24 20 14 24 20 0 20 17 17 17 17 17 20 5 2 24 17 11 17 24 2 17 11 20 8 0 14 11 17 11 17 0 14 8 14 2 2 11 11 5 24 24 24 24 5 20 0 20 8 0 5 24 0 24 0 5 24 0 8 14 11 5 20 17 0 8 20 14 8 11 11 5 2 5

13718.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 11 20 2 8 5 2 24 14 17 24 20 8 20 2 14 14 17 5 11 2 0 5 17 5 8 2 24 5 24 5 25 8 25 20 20 24 24 11 14 17 14 15 14 24 14 0 20 25 8 0 14 14 5 20 20 17 17 25 14 0 5 20 11 0 11 24 0 5 5 8 20 11 17 24 8 24 20 14 24 20 0 20 17 2 17 17 17 20 25 2 24 2 11 17 5 14 14 11 14 8 17 17 25 2 25 17 0 14 8 14 2 2 11 11 17 24 24 24 24 5 8 25 20 8 0 5 24 11 11 0 11 24 5 8 14 11 5 20 17 0 8 20 14 8 5 25 5 2 5

16114.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0
20 0 20 14 8 5 17 24 14 0 21 20 8 20 17 14 14 17 11 0 14 11 0 17 5 8 0 24 5 24 11 11 8 0 20 8 24 24 17 14 17 14 24 20 24 14 5 20 11 14 0 2 14 5 20 20 17 11 11 14 0 5 20 11 11 11 5 0 0 5 20 8 5 0 24 8 24 20 8 24 20 0 8 17 2 17 17 11 20 5 0 24 2 0 17 11 17 14 17 20 14 17 17 11 2 11 11 11 8 8 14 14 2 11 0 17 24 24 5 24 5 20 11 20 14 0 5 24 0 2 0 11 24 24 8 14 17 11 20 17 0 8 20 14 8 0 11 5 2 5

12566.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1
20 11 20 14 20 5 2 24 14 17 24 20 20 20 17 14 14 17 5 11 14 0 24 17 24 8 17 24 24 24 5 11 20 11 20 20 24 24 0 14 0 14 15 8 24 14 17 20 11 8 11 14 14 5 20 20 17 17 11 14 0 5 20 11 11 11 24 0 24 24 20 20 11 17 24 8 24 20 14 24 20 17 20 17 17 17 17 17 20 5 17 24 17 11 17 24 2 5 11 20 8 17 17 11 2 29 17 11 14 8 14 14 2 11 11 29 24 24 24 24 5 20 11 20 20 17 5 24 17 11 0 0 24 5 8 14 0 5 20 17 0 8 20 14 8 11 11 5 2 5

11488.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 0 20 14 20 5 17 24 14 17 24 8 8 20 17 14 14 17 5 11 2 17 24 17 24 8 2 24 24 24 24 25 20 11 20 20 24 24 0 14 0 14 15 2 24 14 0 20 25 8 5 14 14 5 20 20 17 11 11 14 0 5 20 11 11 11 24 0 5 5 20 20 11 17 24 8 24 20 14 24 20 17 20 17 17 17 17 17 20 5 2 24 17 0 17 24 14 17 11 20 20 17 17 11 2 25 17 11 14 14 14 14 2 11 11 17 24 24 24 24 5 8 0 20 20 0 5 24 0 11 0 11 24 5 14 14 17 5 20 17 0 20 20 14 8 11 25 5 2 5

13643.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0
20 11 20 14 20 5 2 24 14 17 5 20 14 20 17 14 14 17 5 11 14 17 5 17 5 20 2 24 5 24 5 11 20 5 20 20 24 24 25 14 0 14 15 8 24 14 17 20 11 8 5 14 14 5 20 20 17 11 17 14 0 5 20 11 11 11 24 0 5 5 20 20 11 17 24 8 24 20 14 24 20 17 20 17 17 17 17 0 20 5 2 24 17 11 17 5 2 2 11 8 8 17 17 11 2 25 17 11 14 8 14 2 2 11 11 11 24 24 24 24 5 8 25 20 20 0 5 24 11 17 0 0 24 24 8 14 0 5 20 17 0 8 20 14 8 25 25 5 17 5

14608.0
1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0
20 11 20 2 20 5 2 24 14 17 24 8 20 20 17 14 14 17 5 11 14 0 5 17 24 8 2 24 24 24 5 5 8 11 20 20 24 24 17 14 0 14 24 8 24 14 11 20 11 8 5 14 14 5 20 20 17 11 11 14 0 5 20 11 11 11 24 0 24 24 8 20 11 17 24 8 5 20 14 5 20 0 20 17 17 17 17 0 20 5 2 24 2 11 17 24 14 17 17 8 20 17 17 11 17 5 17 11 14 8 14 14 2 11 11 5 24 24 24 24 5 20 11 20 8 11 5 24 17 11 0 17 24 24 8 14 11 5 20 17 0 8 20 14 8 11 11 5 2 5

7117.0
1 1 1 1 1 1 1 1 1 1
5 6 4 1 7 9 3 7 8 8 4 9 2 6 2 7 7 3 0 6 6 1 4 1 6 5 5 4 8 5 8 0 0 0 3 9 2 6 6 9 2 7 3 3 3 5 0 5 6 4 1 1 6 6 2 7 2 8 8 8 0 0 1 5 0 6 6 6 4 4 0 4 4 0 7 7 2 2 6 5 7 2 2 9 9 7 9 9 9 2

8215.0
0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
12 10 11 9 19 18 16 13 17 1 11 19 19 10 19 19 12 13 14 14 14 9 9 11 12 8 11 12 17 13 1 19 6 19 14 19 19 15 1 1 1 11 11 16 9 14 18 19 15 19 1 17 1 13 13 9 17 14 14 14 11 11 11 13 11 13 15 15 19 19 19 18 19 19 19 18 19 19 19 19

9143.0
1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1
27 22 12 24 25 22 26 21 27 5 24 24 13 17 18 18 21 15 12 0 25 26 22 22 17 13 29 18 27 5 29 24 2 26 0 22 25 27 15 11 18 18 27 24 29 25 26 17 17 11 21 0 0 18 18 18 21 22 2 27 5 27 24 29 27 28 27 27 24 27

7142.0
1 1 1 1 1 1 1 1 1 1
4 4 4 4 4 4 4 4 6 0 0 0 0 0 0 0 1 1 1 7 1 1 6 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 0 1 1 2 8 7 5 9 7 7 6 5 5 8 8 7 7 9 5 5 5 9 3 0 6 6 8 1 5 4 7 9 7 7 8 6 6 5 8 7 9 9 9 9 9 6 5 7 5

8385.0
1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1
0 0 0 0 0 0 0 6 18 6 6 6 18 6 6 3 3 3 3 3 10 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 0 0 3 3 4 3 18 16 18 3 18 19 3 18 17 17 18 5 5 15 3 10 3 3 15 17 18 3 17 12 3 3 18 4 19 17 18 17 17 16 10 3

9484.0
1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0
10 10 0 10 8 0 0 11 11 11 11 11 11 11 11 2 3 2 2 24 2 6 6 6 6 5 5 7 9 8 8 8 9 7 0 2 3 5 14 11 28 18 19 0 24 3 26 27 27 28 0 27 27 11 3 26 26 18 14 18 19 19 28 26 27 27 14 27 19 18

6429.0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 2 0 1 2 1 1 2 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 6 7 6 0 7 7 7 7 7 7 8 8 8 6 6 8 6 8 9 9 9 8 0 9 9 9

7605.0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1
0 1 0 0 0 1 1 1 1 2 3 2 2 3 2 4 5 4 5 4 5 5 5 5 6 6 6 6 6 6 6 9 9 8 8 9 9 9 9 4 9 9 10 10 11 10 11 10 13 13 12 12 13 12 12 14 14 12 14 12 0 14 14 14 14 17 17 17 17 17 17 17 17 19 19 19 19 19 19 19

8550.0
0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1
2 2 2 2 2 2 2 2 3 5 3 3 5 6 15 6 7 7 7 6 7 7 9 9 9 9 10 12 12 20 12 12 15 15 17 12 17 17 17 17 12 17 20 20 20 19 20 20 23 17 23 19 2 23 23 23 23 26 26 26 25 26 26 25 28 29 28 28 28 29

9197.0
1 1 1 1 0 1 1 1 0 1
7 6 3 0 2 1 5 5 3 7 7 0 6 9 0 9 9 5 5 3 6 6 0 3 0 6 7 3 3 7 7 7 3 3 3 5 1 9 0 6 6 9 9 9 5 5 5 5 5 3 3 5 6 0 0 0 6 1 5 2 2 7 7 7 3 7 0 3 3 7 3 6 6 0 6 3 3 3 3 0 3 5 2 2 2 2 1 7 5 7 9 1 1 2 6 1 9 1 1 9

8386.0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1
15 6 19 10 12 13 5 5 15 1 5 10 6 13 6 13 12 5 5 15 14 10 10 14 14 14 15 19 19 15 1 1 19 19 15 5 13 13 10 6 10 13 13 13 5 5 5 5 5 19 15 5 10 14 14 10 6 14 13 13 13 5 1 5 15 15 10 14 1 15 15 10 10 10 10 19 19 19 19 19 15 5 12 12 18 13 18 5 5 1 13 18 13 12 18 13 13 18 13 13

9272.0
0 0 0 1 1 1 1 1 1 1
7 7 7 7 7 7 7 7 4 4 4 4 3 4 4 4 4 8 3 8 8 8 3 8 3 9 9 9 9 9 9 9 9 5 6 6 6 6 6 6 6 6 6 6 7 7 4 8 8 5 5 3 4 6 4 5 3 3 3 4 6 5 5 3 3 3 5 7 4 7 6 6 4 3 3 5 3 4 7 6 6 3 3 5 5 3 3 7 5 7 5 5 6 5 5 6 3 4 3 7

9427.0
0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0
5 5 5 5 5 5 5 5 1 7 7 7 7 7 7 7 7 12 13 13 12 13 13 12 12 9 9 9 9 9 9 9 9 15 18 18 18 18 18 18 18 18 18 18 5 5 7 12 12 15 15 1 7 18 7 15 3 3 1 7 18 15 15 13 13 3 15 18 7 5 17 18 7 3 3 15 3 7 5 15 18 1 13 15 15 3 3 7 15 1 13 15 17 17 15 15 1 7 3 5

9320.0
1 0 1 1 1 0 1 1 1 1
7 2 7 7 7 2 7 2 7 2 2 2 2 2 2 2 2 2 2 3 3 3 2 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 8 6 8 6 8 6 8 3 8 3 3 3 3 6 6 6 6 6 6 6 6 6 0 4 6 6 6 0 6 6 0 0 6 0 4 7 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 4 9 4 9 9 9 9 9 2 7

8509.0
0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0
18 18 18 18 18 2 18 13 8 2 2 8 8 8 2 8 2 2 2 7 6 2 2 6 2 12 2 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 9 13 7 13 7 9 7 7 13 13 7 9 13 18 13 9 13 9 9 13 15 15 15 15 15 15 15 15 18 18 18 18 18 18 18 18 18 18 18

23882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

32882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

53219.0
1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
18 6 21 27 2 12 15 27 22 28 4 28 8 5 28 18 3 8 22 0 18 16 5 24 10 18 27 28 29 21 19 19 4 15 27 6 9 8 24 16 18 9 6 26 8 19 3 21 19 14 27 16 24 16 8 6 18 9 18 11 4 0 7 8 10 11 5 14 28 25 7 12 6 9 23 10 10 5 9 16 23 17 9 7 29 3 6 5 27 7 28 6 18 25 5 3 28 25 0 28 28 15 12 18 4 24 4 24 22 3 19 4 27 12 12 8 28 7 17 8 9 11 28 19 26 16 16 11 26 17 28 24 11 10 23 9 3 3 28 10 12 27 6 25 12 5 24 15 18 25 24 17 5 0 8 27 5 15 3 3 23 27 10 2 23 27 2 29 3 21 23 8 28 10 26 2 27 8 29 10 2 24 24 19 12 8 11 23 17 2 21 21 19 29 7 6 7 21 23 19

39121.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

23882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

32882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

53882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

39121.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

23882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

32882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

52779.0
1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
18 6 16 27 21 12 15 27 22 28 4 28 8 1 19 18 1 14 22 27 18 16 5 24 23 7 27 19 29 5 19 19 4 16 27 6 8 8 24 16 18 8 12 4 8 4 8 2 19 20 0 16 2 21 8 12 7 26 18 7 29 0 7 8 3 12 0 14 28 25 25 12 19 8 23 23 10 10 8 22 23 0 26 25 29 10 6 5 27 12 27 6 12 25 0 3 27 28 0 28 28 21 12 18 4 0 4 24 22 3 19 4 18 12 12 8 28 7 14 8 20 25 27 19 26 16 21 12 19 0 12 24 25 3 1 26 3 3 28 20 12 27 12 25 25 5 24 21 27 25 0 0 23 0 8 28 2 21 3 3 23 27 10 24 10 27 5 4 3 21 5 8 28 10 26 21 0 20 29 10 5 21 24 19 25 8 28 23 0 21 2 21 19 6 25 12 7 21 10 6

23882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

32882.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

53168.0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 28 22 11 4 28 20 1 28 7 3 20 22 27 27 16 5 24 23 7 27 19 29 2 19 19 4 16 27 6 8 8 24 15 18 9 6 29 8 19 3 21 19 14 0 16 2 16 8 12 11 9 7 7 29 0 7 20 13 11 0 14 6 25 18 12 19 9 23 23 20 23 8 24 23 0 9 7 29 13 19 2 27 7 28 6 7 25 2 3 11 6 0 28 28 15 25 7 4 0 4 24 22 3 19 4 27 12 12 8 28 25 28 8 20 11 28 19 26 16 2 11 19 0 28 2 12 20 23 9 3 3 28 23 12 24 6 11 25 5 24 21 27 25 24 0 23 0 8 11 2 21 3 3 13 27 23 24 5 27 5 4 3 21 5 20 28 14 4 21 0 20 29 20 5 15 24 28 12 8 28 23 0 21 2 21 6 4 7 12 7 21 23 19

39121.0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 19 21 27 2 12 15 27 22 28 4 28 13 1 28 18 1 20 22 0 18 16 5 24 10 18 27 19 29 2 19 19 4 16 27 6 20 8 24 16 18 9 6 4 8 19 13 21 19 14 24 16 24 16 8 6 11 9 18 7 29 0 7 8 13 11 5 14 28 25 18 12 19 9 23 23 20 23 8 16 10 0 9 25 29 13 6 5 27 7 28 6 25 25 2 3 11 6 0 28 28 15 25 18 4 0 4 24 22 3 19 4 27 12 12 8 28 7 17 8 26 11 17 19 26 16 2 11 26 17 28 24 25 20 23 9 3 3 28 10 12 22 11 11 25 5 24 15 27 25 24 17 23 0 8 11 2 15 3 13 13 27 10 24 5 27 5 4 3 21 1 20 19 14 26 2 0 10 29 10 5 21 2 19 12 8 28 23 0 21 2 21 6 4 7 12 7 15 10 19

总结

  和TSP问题很相似，寻找最优的时候，初始化可以使用贪心策略来进行初始解的生成，不过在这里遇到了一个坑，那就是我错估了贪心的效果了，没想到使用了贪心策略之后，得到的解已经很接近最优了，因此在使用模拟退火和遗传算法的时候，反而得到了一个更加糟糕的结果，所以要选择一个比较低的温度，因为已经比较接近最优了，就不要接受太多的差解了，如果接受太多差解的话，有可能导致之后回不到刚开始更好的位置了。

  在这次的实验中我也学到了交换方式是多么的重要，一开始因为做惯了TSP问题，想着是随机挑两个工厂交换一对消费者，结果一直得不到好的结果，因为我都用了贪心的算法，让他们选择了当前较好的位置，这样交换就一定会得到很坏的结果。后来我换了一种方式，只移动一个消费者，这样的变动就随机多了，而且通常影响不大，更有利于在目前已经很稳定的局面下寻找一个更好的解。