[算法期末项目] Capacitated Facility Location Problem
题目
给定m个工厂和n个用户,每个用户有一定的需求,并将需要被指定(assign)给某一个工厂,但工厂的承载量时有限的,被指定给某一个工厂的用户的需求总和不能超过工厂的容量(capacity).工厂的开启和用户的指定都有花费.现在我们设计一个工厂开启和用户分配的方案,需要最小化工厂开启和用户分配的花费.
思路
算法框架
这题是一个组合优化问题,在不超过工厂容量的情况下,每一个用户都可以分配到不同的工厂,复杂度将是一个指数级别的问题.因此我们不能使用遍历所有情况的方法求得最优解,这启发我们使用启发式的算法,这里我们采用模拟退火(SA)和遗传算法(GA),尝试解决这个问题.
无论我们使用SA还是GA,需要解决的最重要的问题是如何有效的生成可行解的问题.因为SA和GA都已经有了一个完整的计算模型,这个模型讨论的都是在得到新的解以后,如何合理的选取,避免达到局部最优的问题.而如果我们本身就无法有效地产生优良的解,那么无论有多么好的选择算法,都无法使算法达到一个足够好的解.因此这份报告将会把重点放在新解的生成上.
新解产生
生成新解的一个自然的思路是:拿到一个已有的解,如何产生另外一个有可能更好的解呢?这需要我们考虑:在这个有限容量工厂定址问题中,一个"优秀"的解是如何组成的?
显然,这样的一个解将会以工厂为单位构成.直觉告诉我们.最优解应该会有较高的工厂利用率,这样子既可以满足用户的需要,又不会有太多的工厂开启的消耗.试想,如果在某个产生解的过程中,恰好产生了某种分配,这个分配刚好最大限度地利用了工厂的容量,而且花费不会太高,那么,在SA的领域操作和GA的遗传变异过程中尽可能的保留这个大限度利用工厂容量的操作,将会有更大的可能性找到更好的解.
注:我们还有其他一些常用的交叉遗传变异等新解产生的办法.比如,reverse:把结果中的一段完全反过来.这在类似TSP等路径求解问题中十分适用.因为在路径求解问题中,最优解的构成单位是一个一个的路径片段.使用这种以一段路径为单位的变异不会破坏解内的良好结构.但是在这个问题中,良好结构并不是以一个序列为单位出现的,更多的是以某个"块"出现:几个被分配到同一工厂的用户可以被称为一个"块".因此,传统的crossover方法直接用到这个新解产生上,效果并不是太好.
解的表示
若用户的个数为n,那么解是一个长度为n的数组,每个元素是一个整数,表示被分配到了哪个工厂.
算法设计
模拟退火
模拟退火最关键的部分是领域操作,我们这里的领域操作是随机在解中随机选择一段,全部重新随机换成另外一个工厂.
但实验发现模拟退火的收敛效果没有遗传算法好,因此我们后面的计算都使用遗传算法.
下图是调整不同参数后模拟退火算法的收敛曲线,事实上效果并不算太好.
遗传算法
交叉
前面提到,我们在交叉操作中,我们尽可能地要把父代解中同一个工厂内的分配保留到子代,因此我们的交叉算法为:
先在父代一中选取若干个已经被分配用户的工厂,直接传给下一代,并用父代二的数值填满剩余未分配的用户,形成一个子代个体
变异
同样,我们尽可能要保留同一个工厂内的个体,个体中每个用户有一定概率会变异,变异的概率反比于这个用户被分配到工厂的服务用户的数量.当变异在某一个位置发生时,在这个位置的用户会被重新分配给另外一个工厂.
自然选择
这里我们简单地使用k-锦标赛的方法,当一个新个体加入种群后,随机从种群中选取k个个体,这些个体中适应度最低的(使目标函数最大)的一个个体将被抛弃
参数影响
参加交配的个体数在群体中的比例
种群大小:可以看出,这是对最后收敛结果影响最大的一个参数,种群数量较大,可以取得更好的结果,但种群数量过大,会降低算法的计算速度
进行k-锦标赛的k.只要新个体打败k个个体中最弱的一个时,就有机会进入种群,所以当k比较大时,种群有更大的概率接受新解,此处当k=5时,明显没有k更大时得到的结果好.
遗传的比例,决定个体会从父代一遗传多少基因.注意到,这个参数的影响力较弱.
实验环境
linux ubuntu 18.04, python 3.6
python的计算效率可以说是十分低下,同样的时间,其他同学的C++版本代码能跑几千代,而我的python代码只能跑几百代,二者几乎有数量级上的差异.可以说,python十分不适合处理这种计算密集型的程序.并且囿于效率,下面的计算结果迭代次数仍然较小,还有一定的提升空间.
result table
| Result | Time(s) | |
|---|---|---|
| p1 | 10017.0 | 19.15 |
| p2 | 8952.0 | 17.79 |
| p3 | 10722.0 | 15.28 |
| p4 | 12286.0 | 17.32 |
| p5 | 11047.0 | 18.36 |
| p6 | 10330.0 | 18.83 |
| p7 | 11966.0 | 18.92 |
| p8 | 14447.0 | 18.86 |
| p9 | 9592.0 | 13.09 |
| p10 | 8781.0 | 12.52 |
| p11 | 10342.0 | 12.80 |
| p12 | 12029.0 | 13.18 |
| p13 | 9678.0 | 15.03 |
| p14 | 8238.0 | 14.15 |
| p15 | 10493.0 | 14.29 |
| p16 | 12528.0 | 15.60 |
| p17 | 9421.0 | 14.85 |
| p18 | 8085.0 | 16.76 |
| p19 | 10410.0 | 14.37 |
| p20 | 12796.0 | 15.60 |
| p21 | 9140.0 | 13.41 |
| p22 | 8014.0 | 12.84 |
| p23 | 10056.0 | 14.12 |
| p24 | 12316.0 | 15.50 |
| p25 | 19659.0 | 33.38 |
| p26 | 16663.0 | 34.22 |
| p27 | 18789.0 | 33.68 |
| p28 | 25468.0 | 35.54 |
| p29 | 23771.0 | 35.70 |
| p30 | 20848.0 | 35.17 |
| p31 | 26131.0 | 41.66 |
| p32 | 29252.0 | 38.31 |
| p33 | 18826.0 | 30.91 |
| p34 | 16808.0 | 30.99 |
| p35 | 19619.0 | 32.25 |
| p36 | 23006.0 | 31.44 |
| p37 | 17082.0 | 29.87 |
| p38 | 15441.0 | 29.91 |
| p39 | 16812.0 | 29.93 |
| p40 | 21441.0 | 30.63 |
| p41 | 8359.0 | 20.36 |
| p42 | 10573.0 | 23.05 |
| p43 | 10858.0 | 21.77 |
| p44 | 11893.0 | 20.44 |
| p45 | 12498.0 | 23.18 |
| p46 | 10587.0 | 20.32 |
detail solution
p1
10017.0
1 0 1 1 0 1 1 1 1 1
5 7 8 2 9 9 5 6 3 2 6 3 0 0 6 9 5 0 3 9 7 6 3 5 6 9 5 7 0 3 3 8 2 0 3 7 9 3 6 8 5 7 8 2 5 7 0 2 5 6
p2
8952.0
0 0 1 1 1 1 1 1 1 1
5 7 8 2 9 9 5 6 7 2 6 6 4 9 6 4 5 6 3 9 7 6 3 5 6 9 5 7 3 3 3 8 2 4 3 7 9 3 6 4 5 7 8 2 5 7 8 2 4 6
p3
10722.0
1 0 1 1 1 1 1 1 1 1
5 7 8 2 9 9 5 6 7 2 6 3 4 0 6 4 5 0 3 9 7 6 3 5 6 9 5 7 0 3 3 8 2 0 3 7 9 3 6 4 5 7 8 8 5 7 0 2 4 6
p4
12286.0
0 0 1 1 1 1 1 1 1 1
5 7 8 2 9 9 5 6 3 2 6 3 4 9 6 4 5 6 7 9 7 6 3 5 6 9 5 9 3 3 3 8 2 4 3 7 9 3 6 4 5 7 8 8 5 7 6 2 4 6
p5
11047.0
1 1 1 1 1 1 1 1 1 1
5 7 8 2 9 9 5 9 3 2 6 6 1 0 6 4 5 0 2 0 7 6 3 6 4 9 5 7 3 3 3 8 5 1 3 7 9 3 4 4 5 7 8 8 1 7 0 2 4 6
p6
10330.0
1 1 1 1 1 1 1 1 1 1
1 7 8 8 1 2 5 0 7 2 6 6 4 4 6 4 5 0 1 9 7 0 3 5 6 2 5 7 0 3 3 8 5 1 3 8 9 1 6 4 5 4 8 8 1 7 0 2 4 6
p7
11966.0
1 1 1 1 1 1 1 1 1 1
4 7 8 2 5 9 5 9 7 2 6 3 4 4 6 4 5 0 7 9 7 6 1 9 8 9 5 7 7 3 3 8 2 1 3 8 9 3 6 4 5 4 8 8 5 7 0 2 4 6
p8
14447.0
1 1 1 1 0 1 1 1 1 1
5 3 8 2 7 9 2 6 7 2 6 6 9 0 6 1 5 0 7 0 7 8 3 9 6 9 6 9 0 0 3 8 2 1 3 8 9 3 5 8 5 7 8 7 1 7 8 9 0 6
p9
9592.0
1 1 0 1 0 1 1 0 1 1
5 5 8 8 9 9 5 9 3 0 6 3 3 0 6 9 5 0 3 9 8 6 3 5 6 9 5 9 0 3 3 8 5 1 3 8 9 3 6 8 5 1 8 8 1 3 0 3 0 6
p10
8781.0
1 0 0 1 1 1 1 1 1 1
5 7 8 8 9 9 5 6 3 0 6 3 4 0 6 4 5 0 7 9 7 6 3 5 6 9 5 7 0 3 3 8 5 0 3 7 9 3 6 4 5 7 8 8 5 7 0 3 4 6
p11
10342.0
0 1 0 1 0 1 1 1 1 1
5 7 8 8 9 9 5 6 3 3 6 3 3 9 6 9 5 6 7 9 7 6 3 5 6 9 5 7 3 3 3 8 5 1 3 7 9 3 6 8 5 7 8 8 1 7 8 3 5 6
p12
12029.0
1 0 1 1 1 1 1 1 0 0
5 7 0 2 7 2 5 6 3 2 6 3 4 0 6 4 5 0 3 7 7 6 3 5 6 2 5 7 3 3 3 0 2 0 3 7 6 3 6 4 5 7 0 2 5 7 0 2 4 6
p13
9678.0
1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1
0 13 1 15 4 14 19 11 5 4 11 5 8 6 15 13 4 13 0 1 15 4 4 14 19 13 15 11 5 6 4 8 6 4 0 8 0 6 11 1 0 13 19 19 6 5 1 14 13 8
p14
8238.0
1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1
0 6 14 15 4 14 12 8 5 4 6 5 8 6 15 13 4 0 12 13 15 4 4 14 19 17 15 19 5 6 4 0 17 4 0 8 0 6 6 15 0 13 19 19 4 5 17 14 13 8
p15
10493.0
1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0
0 13 1 18 4 14 18 16 5 4 18 5 15 6 15 13 4 0 16 1 15 14 4 14 14 13 15 16 5 4 1 0 6 4 0 1 0 6 6 16 0 13 16 15 6 4 18 14 13 18
p16
12528.0
1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0
0 13 14 18 4 14 3 18 5 4 18 5 15 6 15 13 4 13 0 13 15 4 4 14 14 3 15 18 5 14 15 0 6 4 0 15 5 6 6 18 0 13 3 18 6 5 3 5 13 18
p17
9421.0
1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0
0 6 14 5 8 14 12 8 5 4 12 5 8 12 12 13 4 0 0 1 15 8 4 14 14 13 15 4 5 6 1 0 15 4 0 8 0 6 12 1 0 6 1 8 4 5 12 14 13 8
p18
8085.0
1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1
0 6 1 18 7 14 19 19 18 4 18 18 15 6 15 19 4 0 7 1 19 14 4 14 19 17 15 7 17 6 1 0 17 4 0 1 0 6 6 1 0 6 19 17 4 7 19 14 1 7
p19
10410.0
1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0
0 6 1 15 7 14 3 11 5 4 11 5 15 11 15 3 4 7 7 1 15 4 4 14 14 3 4 7 5 6 1 0 6 4 0 15 0 6 11 1 0 6 3 15 6 5 0 14 1 7
p20
12796.0
1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0
0 6 1 1 7 7 3 16 5 4 15 5 15 6 15 3 4 7 7 3 15 16 4 5 5 3 15 7 5 6 1 0 0 4 0 5 0 6 6 1 3 6 16 15 4 7 3 5 15 7
p21
9140.0
1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0
0 6 1 15 4 5 12 8 5 4 6 5 8 12 12 13 4 0 12 1 15 4 4 5 5 13 15 0 5 6 1 0 6 4 0 8 0 6 6 1 0 6 1 15 6 5 0 5 13 8
p22
8014.0
1 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0
0 6 1 18 4 14 3 18 5 4 18 5 15 6 15 3 4 0 0 1 15 14 4 14 14 3 15 3 5 6 1 0 6 4 0 1 0 6 6 1 0 6 3 15 4 5 0 14 1 18
p23
10056.0
1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0
0 13 1 15 4 14 12 14 5 4 12 5 15 12 12 13 4 0 12 1 15 14 4 14 14 13 15 0 5 14 1 0 15 4 0 1 0 15 12 13 0 13 1 5 4 5 12 14 13 15
p24
12316.0
1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1
0 2 2 2 4 5 0 5 5 6 6 5 15 6 15 19 4 0 0 1 15 0 4 5 19 2 15 6 5 19 1 0 4 4 0 5 2 6 6 1 0 6 19 19 4 5 1 5 2 2
p25
19659.0
0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0
2 20 25 25 16 8 13 10 25 13 8 20 13 10 14 14 16 8 9 13 8 16 9 10 14 10 27 9 8 13 8 24 8 9 14 24 8 24 4 25 4 24 10 10 24 7 20 9 8 7 8 13 8 7 13 10 13 4 25 13 10 13 9 25 13 8 8 8 10 14 8 9 24 10 24 10 8 8 27 9 10 13 10 9 13 14 27 25 14 8 10 13 10 9 4 20 16 8 9 13 4 25 10 9 14 8 8 8 7 13 10 8 9 25 9 10 27 16 25 7 7 20 16 8 13 10 8 8 8 25 10 16 8 25 9 20 8 9 25 25 8 8 10 7 14 8 8 16 7 25
p26
16663.0
0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0
11 27 27 11 5 22 13 18 25 9 8 20 18 11 5 10 8 8 25 9 8 8 27 25 11 18 20 5 5 9 10 13 10 9 9 22 8 18 18 13 25 25 18 21 13 22 27 9 5 25 22 13 8 9 13 22 20 9 5 5 22 13 8 25 9 8 5 22 9 18 11 13 18 25 5 10 20 16 25 13 11 13 18 9 9 21 18 25 22 25 8 13 18 9 9 20 20 18 21 9 25 13 10 25 22 10 20 9 5 9 22 8 18 5 9 22 27 8 25 13 22 27 9 25 25 18 27 8 5 5 22 20 9 9 9 18 27 8 8 5 8 13 10 18 21 21 8 9 25 25
p27
18789.0
0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0
8 10 24 25 8 10 13 8 9 4 4 21 13 25 13 10 16 24 10 13 21 8 9 16 8 27 16 9 9 13 8 13 10 10 4 24 8 16 21 8 8 21 10 10 24 24 16 8 27 13 10 13 8 9 13 24 27 9 10 25 24 13 8 25 9 8 25 9 10 13 8 13 8 25 9 24 16 8 25 13 4 24 8 10 4 24 10 13 9 16 4 21 8 9 4 24 27 8 9 9 4 25 8 9 24 10 13 16 8 5 24 13 8 9 9 24 8 8 25 5 24 16 9 25 13 10 27 8 8 9 10 13 8 9 13 24 13 8 25 8 4 13 24 10 4 8 27 8 5 25
p28
25468.0
0 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1
8 18 27 4 8 22 13 18 5 13 22 13 8 10 9 10 27 9 9 5 20 20 9 5 8 5 27 9 5 13 4 13 22 9 13 10 9 8 13 7 4 27 10 9 7 10 8 8 27 7 10 13 8 9 9 8 27 18 4 8 10 16 8 7 9 4 13 22 7 13 20 13 9 10 9 22 20 16 27 13 4 20 10 9 13 8 27 27 9 4 4 13 18 10 9 4 20 9 5 13 8 13 10 9 13 8 20 8 20 5 22 13 9 7 9 29 13 9 7 5 10 18 9 27 13 20 20 5 7 8 10 8 9 5 9 18 27 29 8 5 10 13 8 10 13 10 20 8 8 5
p29
23771.0
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1
18 18 29 16 4 4 21 18 7 4 8 22 24 11 5 14 21 24 16 16 21 16 24 7 13 18 27 5 27 13 8 24 8 7 4 14 2 24 7 7 25 5 22 18 14 24 13 16 13 16 8 13 8 7 13 1 0 5 7 7 24 2 8 7 13 8 13 11 18 4 14 22 18 21 14 29 7 8 5 7 2 13 10 9 4 10 9 18 2 13 2 2 8 9 5 4 0 27 7 4 4 13 18 10 4 14 0 9 7 13 22 2 9 25 9 24 16 9 7 5 27 8 9 7 5 14 1 24 6 25 10 2 9 7 9 8 2 16 8 11 8 2 18 21 4 8 13 6 11 5
p30
20848.0
1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0
21 18 21 13 9 4 13 18 21 9 20 27 22 21 5 10 0 18 7 4 8 8 9 25 9 18 18 6 8 5 4 2 18 10 4 20 20 18 2 5 13 27 20 7 21 24 7 9 7 4 22 2 8 7 9 21 20 3 13 5 22 16 8 25 9 8 2 20 9 5 20 20 9 6 14 10 7 6 5 7 4 2 22 10 21 3 21 27 9 8 0 2 18 7 4 10 20 22 16 21 20 2 22 25 18 14 20 6 9 9 22 16 6 5 5 10 13 8 7 5 22 8 18 5 9 24 20 27 16 25 22 13 8 7 13 10 27 18 9 9 20 2 22 21 4 18 18 6 21 5
p31
26131.0
1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1
10 13 29 2 16 10 16 8 9 13 4 21 9 7 25 8 2 9 25 16 21 28 8 8 4 1 7 6 28 25 8 13 10 7 1 21 13 9 2 2 0 2 18 14 14 28 14 29 5 7 24 13 8 7 9 20 0 5 2 0 22 16 8 7 9 0 25 10 7 1 4 22 24 21 14 22 27 8 7 7 8 13 10 25 7 14 10 29 21 25 8 13 10 10 14 1 0 10 2 21 25 5 28 21 21 21 13 8 25 7 4 0 29 25 7 8 16 8 5 5 27 0 16 25 25 24 16 5 13 5 10 2 16 25 7 10 2 27 25 16 2 27 22 21 14 22 0 16 25 5
p32
29252.0
0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1
10 27 7 3 2 24 21 16 7 7 10 13 10 9 21 2 27 10 18 4 24 18 6 4 13 29 13 18 13 5 4 2 18 10 5 2 8 21 4 5 2 2 8 10 7 10 13 8 27 13 4 13 8 9 9 7 27 3 21 25 24 16 8 7 9 2 2 10 9 4 3 27 3 6 3 10 7 16 25 7 2 21 8 10 4 25 13 13 4 16 6 2 10 7 4 10 27 16 18 5 2 2 10 21 24 24 27 16 25 13 24 16 8 25 5 2 8 8 25 13 24 7 6 24 9 7 18 3 5 2 24 16 16 7 13 21 8 24 5 2 21 13 18 9 16 10 3 6 7 7
p33
18826.0
1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0
8 8 24 8 5 24 21 8 21 4 4 22 24 6 16 22 8 24 10 16 6 21 8 10 8 22 13 8 5 16 0 24 10 9 9 24 16 9 21 9 8 13 8 10 21 24 0 8 5 7 10 16 8 7 9 24 8 24 13 9 22 13 8 7 13 2 13 9 7 4 16 22 13 21 13 24 7 8 7 9 4 21 10 9 4 24 8 5 24 9 4 13 8 10 9 10 13 24 2 4 4 4 22 7 4 22 13 8 5 9 24 8 8 7 7 22 16 8 9 5 24 0 16 7 9 24 16 5 7 16 10 13 16 7 7 21 0 6 9 7 8 2 9 7 21 21 16 24 16 9
p34
16808.0
0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0
10 1 13 2 5 8 2 9 10 9 8 8 9 7 5 10 27 18 7 5 8 27 18 9 21 10 1 9 13 9 8 13 10 7 1 8 27 13 9 5 2 13 10 18 4 22 27 9 7 13 24 13 8 7 13 22 27 27 13 5 10 16 8 7 13 8 2 22 10 4 21 22 10 21 1 22 13 8 7 7 2 13 10 10 9 21 10 27 7 8 8 13 8 10 4 21 27 8 10 13 4 4 10 7 13 21 27 8 16 5 10 8 9 5 7 10 27 8 7 1 7 27 9 8 5 18 8 5 7 5 22 13 8 7 7 22 13 27 21 5 4 13 10 9 16 21 13 27 5 7
p35
19619.0
0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0
14 16 13 5 9 8 13 8 21 4 10 11 8 10 11 10 16 24 21 5 11 8 24 7 8 10 13 16 10 7 8 13 11 21 4 8 13 21 24 5 4 24 11 21 1 7 13 16 1 13 24 13 8 7 13 18 10 18 13 11 24 13 8 7 13 4 16 11 7 14 21 13 24 18 8 24 7 16 5 13 4 13 10 7 4 10 16 18 4 16 4 24 10 7 4 14 16 8 4 16 8 24 18 10 16 10 8 9 7 13 24 13 9 7 7 10 16 9 7 5 7 16 8 5 9 18 16 8 13 8 24 16 8 7 7 21 16 16 7 7 11 24 10 18 14 8 13 16 5 11
p36
23006.0
0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0
22 10 13 16 5 8 16 9 10 5 10 13 10 5 5 6 16 16 8 5 24 13 24 7 13 22 3 5 5 5 4 2 10 7 4 6 13 24 5 5 4 13 16 7 3 24 13 6 5 9 10 13 16 7 9 8 3 4 5 4 22 13 8 9 13 4 16 22 7 4 16 22 8 7 5 22 7 6 7 9 4 16 16 10 4 3 13 8 6 13 2 13 8 7 9 6 8 6 9 7 2 4 10 10 22 8 13 8 8 5 22 13 6 5 7 10 13 8 7 9 24 8 6 5 13 24 8 3 5 7 22 13 8 9 7 22 16 16 3 5 4 24 10 7 4 10 13 16 5 13
p37
17082.0
0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1
10 13 24 16 16 8 13 16 7 4 20 13 24 7 7 4 16 8 7 7 10 13 9 7 9 29 7 29 13 8 4 13 11 10 4 29 20 29 11 16 13 13 11 9 4 10 7 29 7 7 24 13 8 7 13 4 20 4 13 16 10 16 8 7 13 8 16 20 9 4 11 16 10 4 24 29 16 16 9 7 4 13 10 7 4 20 13 29 16 20 4 13 8 9 4 10 13 16 9 13 4 13 10 9 4 29 20 8 7 11 29 8 8 7 7 24 8 9 7 13 7 8 8 7 7 29 20 16 7 11 10 13 16 7 7 10 8 24 16 11 4 13 10 9 4 7 16 16 8 9
p38
15441.0
0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0
10 16 8 13 10 2 13 8 10 9 8 13 8 21 1 21 8 8 21 7 8 16 8 16 13 7 8 8 16 9 2 13 8 7 1 1 8 8 16 16 8 2 9 7 21 10 16 16 1 7 10 2 8 7 13 21 10 8 7 2 10 16 8 7 13 2 16 10 7 1 8 16 16 10 1 10 7 16 7 7 8 2 10 21 1 16 13 18 2 2 2 2 10 10 1 10 2 16 7 16 2 13 10 7 1 10 8 8 7 13 10 7 8 21 13 10 16 9 9 13 10 16 8 8 7 10 8 16 8 2 10 13 16 7 7 10 16 9 7 16 2 13 10 9 21 10 13 8 8 13
p39
16812.0
0 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
21 16 9 4 7 8 13 8 7 4 4 16 8 21 9 21 16 16 21 16 21 8 8 21 16 21 8 16 7 9 2 2 8 7 21 2 2 16 21 4 2 13 8 21 21 10 13 8 7 7 10 13 8 7 13 21 21 8 7 2 10 13 8 7 9 4 2 8 10 4 16 16 8 9 16 10 7 16 9 7 4 13 8 7 4 8 13 4 9 16 2 2 8 10 4 21 13 8 10 7 4 4 2 7 4 10 8 8 8 13 10 13 16 9 7 8 16 8 9 9 7 16 8 8 13 21 21 9 13 7 10 13 16 7 13 10 13 8 21 8 4 13 10 10 21 10 16 16 7 16
p40
21441.0
0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0
4 13 4 4 8 8 13 8 7 9 4 9 18 4 8 8 16 16 16 13 21 13 18 7 13 18 16 9 13 13 4 13 18 9 13 18 13 18 4 16 13 4 18 7 4 7 7 9 8 7 4 13 16 7 9 18 8 18 7 9 24 13 8 7 9 4 13 18 7 4 4 16 16 21 13 7 16 16 7 13 4 13 8 7 13 4 16 18 4 4 4 21 8 7 4 4 16 18 16 13 4 4 18 9 9 8 13 9 8 9 24 13 16 7 13 21 8 8 7 9 24 7 16 8 13 8 8 8 8 8 8 13 16 7 13 18 8 9 16 13 4 16 16 18 13 18 16 8 16 13
p41
8359.0
1 0 0 1 1 0 1 1 1 1
0 8 8 3 6 8 4 3 0 3 0 3 7 9 0 6 8 3 4 4 6 6 0 4 6 6 7 6 7 9 4 3 7 3 4 3 3 0 7 7 9 0 9 3 4 0 0 9 0 7 3 3 9 4 3 9 0 7 9 3 6 8 4 4 6 6 4 3 4 3 4 3 8 7 8 0 4 7 3 9 0 4 4 6 9 8 4 6 8 7
p42
10573.0
1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0
6 14 0 13 6 8 13 6 5 6 6 13 0 13 6 0 7 6 1 0 13 13 5 5 14 5 0 8 6 7 0 6 13 5 5 12 5 1 6 13 5 13 6 0 8 7 6 5 6 5 6 5 0 6 14 6 6 13 6 13 12 12 6 13 6 7 12 5 8 5 14 6 6 1 6 13 13 0 0 8
p43
10858.0
1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0
14 12 25 25 9 0 1 21 27 25 8 28 27 27 27 25 21 21 14 25 28 0 21 14 9 27 8 0 0 14 28 8 1 25 8 14 8 0 0 21 12 0 25 21 21 14 21 25 25 0 8 21 28 27 0 28 27 27 1 1 28 25 21 8 1 25 21 12 0 25
p44
11893.0
1 0 1 1 1 0 1 1 1 0
8 4 2 7 7 2 4 7 7 8 7 2 0 2 0 7 4 8 3 7 6 0 4 4 2 4 4 0 7 6 4 8 3 3 2 3 3 3 2 7 0 2 4 0 7 6 0 2 7 7 2 0 2 7 8 2 2 6 6 0 6 7 6 8 0 2 6 7 7 0 3 0 8 7 6 0 4 4 7 4 4 3 7 6 6 4 4 2 2 3
p45
12498.0
1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1
5 9 4 4 4 0 8 19 19 0 0 0 19 15 0 13 19 5 5 13 15 13 13 15 13 19 19 17 19 19 4 19 17 4 13 15 19 0 0 5 13 0 19 5 8 4 4 14 19 4 13 0 19 4 14 17 0 14 5 14 4 19 15 19 9 4 5 15 15 4 15 13 4 13 4 19 4 19 8 19
p46
10587.0
1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0
1 19 19 5 19 5 5 19 8 0 21 19 12 0 21 8 5 9 0 21 19 28 0 12 19 0 1 5 12 19 9 12 0 19 19 19 19 0 19 0 12 19 9 19 19 21 5 0 28 19 19 19 19 5 19 8 21 5 27 0 27 28 5 19 21 5 9 0 19 12