Created
May 5, 2016 19:38
-
-
Save pveierland/214fd7bc3debf3da784474c94a8146be to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
CITY | 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 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||
2 | 3 | 0 | |||||||||||||||||||||||||||||||||||||||||||||||
3 | 2 | 14 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||
4 | 8 | 13 | 3 | 0 | |||||||||||||||||||||||||||||||||||||||||||||
5 | 21 | 10 | 4 | 38 | 0 | ||||||||||||||||||||||||||||||||||||||||||||
6 | 2 | 4 | 23 | 67 | 5 | 0 | |||||||||||||||||||||||||||||||||||||||||||
7 | 10 | 35 | 5 | 48 | 12 | 51 | 0 | ||||||||||||||||||||||||||||||||||||||||||
8 | 5 | 24 | 14 | 2 | 38 | 21 | 10 | 0 | |||||||||||||||||||||||||||||||||||||||||
9 | 98 | 2 | 5 | 21 | 45 | 56 | 75 | 19 | 0 | ||||||||||||||||||||||||||||||||||||||||
10 | 5 | 16 | 11 | 36 | 86 | 1 | 45 | 75 | 10 | 0 | |||||||||||||||||||||||||||||||||||||||
11 | 2 | 31 | 24 | 6 | 21 | 41 | 10 | 5 | 34 | 56 | 0 | ||||||||||||||||||||||||||||||||||||||
12 | 25 | 11 | 1 | 67 | 82 | 10 | 31 | 34 | 10 | 51 | 69 | 0 | |||||||||||||||||||||||||||||||||||||
13 | 19 | 5 | 43 | 12 | 34 | 10 | 66 | 56 | 45 | 6 | 78 | 13 | 0 | ||||||||||||||||||||||||||||||||||||
14 | 21 | 72 | 4 | 5 | 39 | 2 | 16 | 20 | 21 | 45 | 11 | 34 | 21 | 0 | |||||||||||||||||||||||||||||||||||
15 | 2 | 17 | 25 | 12 | 26 | 5 | 17 | 21 | 21 | 11 | 14 | 32 | 16 | 91 | 0 | ||||||||||||||||||||||||||||||||||
16 | 14 | 21 | 4 | 25 | 92 | 72 | 10 | 14 | 33 | 55 | 11 | 54 | 12 | 52 | 34 | 0 | |||||||||||||||||||||||||||||||||
17 | 38 | 24 | 99 | 11 | 31 | 78 | 62 | 43 | 33 | 25 | 10 | 77 | 82 | 11 | 15 | 55 | 0 | ||||||||||||||||||||||||||||||||
18 | 26 | 2 | 16 | 24 | 11 | 25 | 19 | 2 | 81 | 78 | 41 | 56 | 45 | 52 | 61 | 33 | 21 | 0 | |||||||||||||||||||||||||||||||
19 | 33 | 94 | 13 | 62 | 31 | 26 | 10 | 10 | 86 | 25 | 57 | 32 | 91 | 23 | 67 | 72 | 72 | 15 | 0 | ||||||||||||||||||||||||||||||
20 | 36 | 1 | 2 | 61 | 45 | 24 | 21 | 6 | 19 | 12 | 45 | 34 | 63 | 10 | 12 | 72 | 82 | 11 | 55 | 0 | |||||||||||||||||||||||||||||
21 | 1 | 16 | 53 | 22 | 42 | 13 | 15 | 67 | 14 | 31 | 25 | 47 | 16 | 87 | 35 | 9 | 24 | 13 | 25 | 5 | 0 | ||||||||||||||||||||||||||||
22 | 10 | 21 | 22 | 2 | 76 | 10 | 15 | 5 | 31 | 43 | 66 | 14 | 2 | 45 | 24 | 21 | 57 | 10 | 5 | 71 | 4 | 0 | |||||||||||||||||||||||||||
23 | 9 | 91 | 2 | 34 | 5 | 63 | 12 | 61 | 5 | 45 | 6 | 5 | 91 | 12 | 61 | 2 | 6 | 35 | 11 | 21 | 24 | 82 | 0 | ||||||||||||||||||||||||||
24 | 10 | 31 | 81 | 34 | 56 | 23 | 33 | 62 | 24 | 5 | 73 | 10 | 15 | 2 | 52 | 11 | 45 | 40 | 11 | 13 | 27 | 24 | 52 | 0 | |||||||||||||||||||||||||
25 | 2 | 32 | 23 | 52 | 45 | 84 | 21 | 35 | 45 | 21 | 35 | 1 | 25 | 26 | 98 | 76 | 13 | 67 | 5 | 11 | 81 | 14 | 25 | 62 | 0 | ||||||||||||||||||||||||
26 | 19 | 21 | 23 | 56 | 2 | 27 | 78 | 34 | 5 | 10 | 82 | 32 | 67 | 43 | 25 | 98 | 5 | 23 | 12 | 92 | 34 | 4 | 14 | 25 | 42 | 0 | |||||||||||||||||||||||
27 | 11 | 35 | 33 | 21 | 81 | 21 | 91 | 73 | 92 | 10 | 23 | 26 | 25 | 64 | 5 | 24 | 31 | 15 | 91 | 16 | 78 | 15 | 1 | 35 | 98 | 11 | 0 | ||||||||||||||||||||||
28 | 12 | 51 | 91 | 2 | 44 | 67 | 25 | 5 | 21 | 41 | 32 | 11 | 51 | 34 | 61 | 72 | 19 | 35 | 29 | 5 | 15 | 93 | 63 | 31 | 10 | 78 | 38 | 0 | |||||||||||||||||||||
29 | 35 | 10 | 56 | 5 | 2 | 21 | 1 | 35 | 15 | 15 | 2 | 48 | 65 | 55 | 32 | 76 | 21 | 97 | 10 | 34 | 34 | 62 | 21 | 67 | 1 | 52 | 86 | 21 | 0 | ||||||||||||||||||||
30 | 31 | 15 | 32 | 56 | 31 | 21 | 13 | 25 | 34 | 2 | 10 | 31 | 95 | 65 | 79 | 10 | 76 | 56 | 10 | 13 | 71 | 5 | 87 | 84 | 35 | 19 | 10 | 21 | 52 | 0 | |||||||||||||||||||
31 | 56 | 51 | 6 | 45 | 11 | 55 | 25 | 78 | 25 | 34 | 34 | 34 | 52 | 56 | 21 | 2 | 5 | 56 | 45 | 43 | 45 | 5 | 2 | 10 | 10 | 34 | 13 | 56 | 51 | 34 | 0 | ||||||||||||||||||
32 | 21 | 12 | 21 | 27 | 57 | 24 | 10 | 82 | 32 | 34 | 43 | 25 | 98 | 5 | 26 | 24 | 13 | 10 | 23 | 23 | 24 | 14 | 21 | 10 | 21 | 51 | 5 | 56 | 45 | 2 | 81 | 0 | |||||||||||||||||
33 | 41 | 10 | 5 | 10 | 1 | 32 | 26 | 11 | 48 | 31 | 35 | 82 | 11 | 72 | 9 | 21 | 2 | 11 | 76 | 98 | 24 | 72 | 76 | 10 | 2 | 24 | 44 | 2 | 31 | 11 | 51 | 23 | 0 | ||||||||||||||||
34 | 11 | 16 | 2 | 91 | 15 | 25 | 67 | 25 | 51 | 65 | 95 | 52 | 45 | 24 | 21 | 35 | 21 | 15 | 93 | 62 | 5 | 5 | 14 | 72 | 43 | 61 | 55 | 71 | 54 | 91 | 34 | 47 | 38 | 0 | |||||||||||||||
35 | 75 | 5 | 72 | 34 | 56 | 91 | 21 | 14 | 14 | 21 | 63 | 16 | 2 | 91 | 15 | 25 | 67 | 25 | 51 | 11 | 13 | 25 | 10 | 26 | 31 | 72 | 81 | 29 | 10 | 10 | 45 | 23 | 76 | 93 | 0 | ||||||||||||||
36 | 41 | 51 | 34 | 21 | 11 | 13 | 25 | 10 | 26 | 2 | 27 | 14 | 42 | 24 | 53 | 81 | 82 | 2 | 26 | 43 | 64 | 34 | 55 | 65 | 56 | 19 | 31 | 87 | 2 | 21 | 76 | 14 | 10 | 55 | 26 | 0 | |||||||||||||
37 | 2 | 10 | 10 | 41 | 15 | 2 | 34 | 34 | 31 | 65 | 21 | 66 | 16 | 17 | 10 | 62 | 19 | 10 | 21 | 64 | 34 | 55 | 15 | 56 | 5 | 27 | 24 | 91 | 24 | 17 | 43 | 42 | 63 | 17 | 64 | 34 | 0 | ||||||||||||
38 | 24 | 14 | 21 | 81 | 21 | 21 | 55 | 24 | 32 | 25 | 56 | 28 | 45 | 38 | 51 | 10 | 15 | 51 | 12 | 10 | 16 | 81 | 51 | 11 | 48 | 31 | 34 | 25 | 82 | 52 | 39 | 91 | 32 | 71 | 26 | 41 | 55 | 0 | |||||||||||
39 | 13 | 45 | 61 | 51 | 21 | 45 | 26 | 67 | 49 | 45 | 31 | 11 | 57 | 1 | 15 | 56 | 11 | 15 | 21 | 21 | 11 | 35 | 10 | 21 | 42 | 43 | 31 | 56 | 5 | 48 | 13 | 5 | 44 | 55 | 81 | 31 | 24 | 34 | 0 | ||||||||||
40 | 10 | 25 | 21 | 31 | 21 | 13 | 25 | 34 | 15 | 32 | 56 | 31 | 21 | 33 | 25 | 64 | 24 | 72 | 76 | 10 | 2 | 24 | 21 | 35 | 25 | 81 | 62 | 10 | 51 | 24 | 61 | 72 | 19 | 27 | 31 | 43 | 34 | 64 | 31 | 0 | |||||||||
41 | 71 | 56 | 32 | 6 | 21 | 24 | 2 | 32 | 34 | 10 | 45 | 91 | 54 | 67 | 84 | 76 | 10 | 12 | 24 | 21 | 35 | 25 | 81 | 62 | 10 | 56 | 64 | 21 | 11 | 45 | 34 | 26 | 67 | 67 | 24 | 10 | 21 | 17 | 52 | 91 | 0 | ||||||||
42 | 48 | 16 | 67 | 12 | 5 | 42 | 25 | 31 | 24 | 62 | 61 | 19 | 75 | 44 | 34 | 56 | 20 | 21 | 14 | 14 | 36 | 10 | 86 | 67 | 41 | 51 | 6 | 45 | 11 | 55 | 25 | 78 | 25 | 12 | 31 | 43 | 45 | 16 | 21 | 6 | 72 | 0 | |||||||
43 | 10 | 66 | 6 | 17 | 40 | 62 | 19 | 90 | 21 | 15 | 15 | 24 | 5 | 13 | 21 | 53 | 22 | 12 | 81 | 23 | 76 | 33 | 91 | 56 | 32 | 26 | 21 | 51 | 22 | 35 | 31 | 67 | 84 | 10 | 10 | 10 | 72 | 26 | 65 | 56 | 35 | 76 | 0 | ||||||
44 | 21 | 39 | 26 | 72 | 31 | 41 | 31 | 45 | 42 | 76 | 5 | 56 | 45 | 32 | 81 | 44 | 21 | 31 | 11 | 57 | 10 | 31 | 11 | 57 | 41 | 15 | 56 | 51 | 71 | 21 | 21 | 29 | 21 | 75 | 40 | 31 | 32 | 82 | 54 | 18 | 38 | 28 | 72 | 0 | |||||
45 | 11 | 24 | 62 | 61 | 22 | 32 | 34 | 34 | 52 | 56 | 21 | 72 | 96 | 56 | 45 | 27 | 51 | 91 | 34 | 21 | 55 | 25 | 24 | 61 | 31 | 67 | 52 | 91 | 29 | 10 | 56 | 45 | 23 | 76 | 93 | 51 | 34 | 34 | 87 | 56 | 98 | 87 | 46 | 47 | 0 | ||||
46 | 5 | 14 | 87 | 71 | 24 | 21 | 43 | 94 | 25 | 64 | 97 | 16 | 13 | 32 | 53 | 22 | 2 | 81 | 23 | 23 | 33 | 91 | 56 | 32 | 56 | 21 | 24 | 16 | 72 | 34 | 81 | 21 | 61 | 21 | 32 | 67 | 46 | 26 | 62 | 45 | 31 | 78 | 34 | 23 | 76 | 0 | |||
47 | 12 | 38 | 45 | 86 | 21 | 82 | 34 | 39 | 26 | 92 | 31 | 31 | 65 | 45 | 42 | 76 | 45 | 56 | 45 | 82 | 81 | 44 | 42 | 31 | 61 | 57 | 51 | 26 | 24 | 13 | 77 | 23 | 23 | 24 | 54 | 21 | 10 | 81 | 21 | 55 | 24 | 32 | 25 | 73 | 13 | 76 | 0 | ||
48 | 14 | 13 | 10 | 34 | 23 | 24 | 21 | 16 | 31 | 51 | 15 | 72 | 17 | 21 | 24 | 72 | 94 | 91 | 16 | 21 | 91 | 31 | 62 | 21 | 35 | 51 | 51 | 26 | 51 | 31 | 10 | 51 | 34 | 45 | 76 | 43 | 39 | 41 | 61 | 34 | 25 | 31 | 21 | 89 | 71 | 24 | 10 | 0 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
CITY | 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 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||
2 | 4727 | 0 | |||||||||||||||||||||||||||||||||||||||||||||||
3 | 1205 | 3588 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||
4 | 6363 | 2012 | 5163 | 0 | |||||||||||||||||||||||||||||||||||||||||||||
5 | 3657 | 1842 | 2458 | 2799 | 0 | ||||||||||||||||||||||||||||||||||||||||||||
6 | 3130 | 6977 | 3678 | 8064 | 5330 | 0 | |||||||||||||||||||||||||||||||||||||||||||
7 | 2414 | 6501 | 3071 | 7727 | 4946 | 743 | 0 | ||||||||||||||||||||||||||||||||||||||||||
8 | 563 | 5187 | 1742 | 6878 | 4200 | 3209 | 2468 | 0 | |||||||||||||||||||||||||||||||||||||||||
9 | 463 | 5028 | 1444 | 6581 | 3824 | 2670 | 1952 | 718 | 0 | ||||||||||||||||||||||||||||||||||||||||
10 | 5654 | 2327 | 4462 | 1402 | 2012 | 6929 | 6673 | 6203 | 5789 | 0 | |||||||||||||||||||||||||||||||||||||||
11 | 1713 | 4148 | 1184 | 5366 | 2573 | 2831 | 2380 | 2241 | 1602 | 4392 | 0 | ||||||||||||||||||||||||||||||||||||||
12 | 1604 | 4723 | 1520 | 5946 | 3157 | 2266 | 1795 | 2051 | 1343 | 4947 | 586 | 0 | |||||||||||||||||||||||||||||||||||||
13 | 2368 | 3635 | 1498 | 4679 | 1924 | 3407 | 3051 | 2920 | 2330 | 3648 | 766 | 1299 | 0 | ||||||||||||||||||||||||||||||||||||
14 | 2201 | 3125 | 1103 | 4378 | 1580 | 3854 | 3405 | 2762 | 2291 | 3501 | 1029 | 1612 | 646 | 0 | |||||||||||||||||||||||||||||||||||
15 | 1290 | 4907 | 1501 | 6225 | 3427 | 2178 | 1604 | 1687 | 970 | 5274 | 883 | 406 | 1642 | 1853 | 0 | ||||||||||||||||||||||||||||||||||
16 | 1004 | 3930 | 951 | 5709 | 3179 | 4076 | 3382 | 1304 | 1451 | 5183 | 2040 | 2208 | 2446 | 2026 | 2029 | 0 | |||||||||||||||||||||||||||||||||
17 | 3833 | 7463 | 4298 | 8417 | 5749 | 727 | 1469 | 3932 | 3376 | 7216 | 3353 | 2824 | 3840 | 4349 | 2803 | 4759 | 0 | ||||||||||||||||||||||||||||||||
18 | 2258 | 6338 | 2903 | 7578 | 4793 | 881 | 168 | 2331 | 1796 | 6535 | 2224 | 1639 | 2905 | 3247 | 1438 | 3220 | 1601 | 0 | |||||||||||||||||||||||||||||||
19 | 3419 | 7243 | 3967 | 8296 | 5577 | 293 | 1020 | 3487 | 2959 | 7140 | 3100 | 2542 | 3655 | 4119 | 2466 | 4368 | 477 | 1165 | 0 | ||||||||||||||||||||||||||||||
20 | 2267 | 5105 | 2169 | 6135 | 3409 | 1930 | 1681 | 2669 | 1951 | 5022 | 1049 | 694 | 1488 | 1997 | 986 | 2900 | 2359 | 1563 | 2170 | 0 | |||||||||||||||||||||||||||||
21 | 2957 | 4043 | 2209 | 4802 | 2223 | 3310 | 3110 | 3487 | 2835 | 3621 | 1246 | 1586 | 730 | 1341 | 1987 | 3151 | 3617 | 2988 | 3520 | 1430 | 0 | ||||||||||||||||||||||||||||
22 | 720 | 4022 | 652 | 5707 | 3066 | 3672 | 2993 | 1175 | 1112 | 5077 | 1625 | 1767 | 2096 | 1753 | 1593 | 442 | 4345 | 2829 | 3965 | 2460 | 2779 | 0 | |||||||||||||||||||||||||||
23 | 1700 | 3677 | 828 | 4982 | 2185 | 3315 | 2827 | 2260 | 1725 | 4090 | 503 | 1050 | 697 | 606 | 1253 | 1765 | 3851 | 2666 | 3588 | 1547 | 1387 | 1401 | 0 | ||||||||||||||||||||||||||
24 | 5279 | 2863 | 4136 | 2322 | 1860 | 6199 | 6009 | 5840 | 5346 | 922 | 3841 | 4357 | 3076 | 3078 | 4716 | 4960 | 6433 | 5882 | 6393 | 4333 | 2905 | 4781 | 3621 | 0 | |||||||||||||||||||||||||
25 | 2578 | 3106 | 1518 | 4178 | 1401 | 3932 | 3552 | 3141 | 2628 | 3207 | 1196 | 1770 | 533 | 419 | 2072 | 2444 | 4372 | 3401 | 4183 | 2019 | 1062 | 2166 | 903 | 2718 | 0 | ||||||||||||||||||||||||
26 | 6076 | 1850 | 4873 | 320 | 2491 | 7745 | 7412 | 6596 | 6285 | 1131 | 5054 | 5633 | 4363 | 4070 | 5915 | 5443 | 8098 | 7263 | 7977 | 5817 | 4482 | 5427 | 4675 | 2042 | 3864 | 0 | |||||||||||||||||||||||
27 | 3465 | 7173 | 3954 | 8186 | 5486 | 365 | 1104 | 3563 | 3007 | 7014 | 3042 | 2498 | 3567 | 4052 | 2454 | 4396 | 370 | 1233 | 202 | 2079 | 3398 | 3984 | 3537 | 6254 | 4097 | 7866 | 0 | ||||||||||||||||||||||
28 | 2654 | 6630 | 3254 | 7800 | 5035 | 482 | 267 | 2728 | 2193 | 6714 | 2488 | 1907 | 3122 | 3517 | 1764 | 3610 | 1206 | 399 | 767 | 1694 | 3119 | 3212 | 2954 | 6024 | 3635 | 7483 | 839 | 0 | |||||||||||||||||||||
29 | 3625 | 1204 | 2446 | 2778 | 894 | 5774 | 5300 | 4120 | 3889 | 2437 | 2945 | 3520 | 2453 | 1923 | 3710 | 2932 | 6267 | 5138 | 6041 | 3910 | 2922 | 2946 | 2475 | 2569 | 1932 | 2515 | 5973 | 5427 | 0 | ||||||||||||||||||||
30 | 3115 | 6814 | 3581 | 7859 | 5141 | 261 | 821 | 3240 | 2661 | 6707 | 2676 | 2128 | 3219 | 3690 | 2082 | 4034 | 726 | 923 | 438 | 1733 | 3087 | 3620 | 3169 | 5966 | 3748 | 7539 | 374 | 558 | 5612 | 0 | |||||||||||||||||||
31 | 1574 | 6001 | 2441 | 7408 | 4611 | 1659 | 916 | 1559 | 1122 | 6477 | 2087 | 1558 | 2842 | 3032 | 1204 | 2572 | 2384 | 794 | 1932 | 1813 | 3115 | 2224 | 2427 | 5913 | 3274 | 7101 | 2019 | 1181 | 4824 | 1716 | 0 | ||||||||||||||||||
32 | 3951 | 3447 | 2960 | 3763 | 1669 | 4513 | 4348 | 4507 | 3920 | 2476 | 2331 | 2778 | 1592 | 1866 | 3164 | 3891 | 4754 | 4227 | 4706 | 2668 | 1240 | 3603 | 2254 | 1687 | 1448 | 3449 | 4569 | 4349 | 2550 | 4280 | 4330 | 0 | |||||||||||||||||
33 | 1748 | 5253 | 1966 | 6461 | 3677 | 1746 | 1270 | 2082 | 1372 | 5432 | 1114 | 531 | 1791 | 2142 | 497 | 2525 | 2335 | 1117 | 2027 | 654 | 1953 | 2089 | 1578 | 4807 | 2284 | 6146 | 1996 | 1377 | 4050 | 1624 | 1180 | 3184 | 0 | ||||||||||||||||
34 | 2142 | 2656 | 950 | 4223 | 1590 | 4431 | 3890 | 2658 | 2391 | 3599 | 1650 | 2171 | 1480 | 838 | 2287 | 1590 | 4991 | 3724 | 4711 | 2694 | 2175 | 1496 | 1148 | 3384 | 1164 | 3938 | 4669 | 4044 | 1498 | 4298 | 3346 | 2510 | 2685 | 0 | |||||||||||||||
35 | 6755 | 3123 | 5564 | 1427 | 3113 | 7910 | 7698 | 7304 | 6883 | 1102 | 5459 | 6003 | 4706 | 4593 | 6342 | 6278 | 8148 | 7565 | 8107 | 6029 | 4607 | 6178 | 5177 | 1716 | 4286 | 1375 | 7970 | 7723 | 3476 | 7679 | 7545 | 3402 | 6475 | 4697 | 0 | ||||||||||||||
36 | 2383 | 6274 | 2916 | 7451 | 4682 | 769 | 332 | 2512 | 1927 | 6376 | 2132 | 1552 | 2772 | 3161 | 1419 | 3313 | 1452 | 286 | 1061 | 1366 | 2796 | 2906 | 2598 | 5699 | 3283 | 7134 | 1085 | 356 | 5071 | 735 | 1023 | 4031 | 1022 | 3693 | 7393 | 0 | |||||||||||||
37 | 3306 | 7183 | 3878 | 8263 | 5533 | 207 | 900 | 3364 | 2845 | 7121 | 3037 | 2472 | 3610 | 4060 | 2379 | 4261 | 609 | 1049 | 132 | 2130 | 3501 | 3861 | 3521 | 6384 | 4136 | 7944 | 305 | 653 | 5980 | 420 | 1808 | 4698 | 1952 | 4636 | 8097 | 965 | 0 | ||||||||||||
38 | 1029 | 5622 | 2035 | 7131 | 4352 | 2225 | 1484 | 985 | 611 | 6284 | 1958 | 1538 | 2721 | 2788 | 1134 | 2033 | 2949 | 1348 | 2503 | 1991 | 3119 | 1719 | 2194 | 5787 | 3086 | 6831 | 2581 | 1744 | 4470 | 2263 | 578 | 4281 | 1341 | 2975 | 7370 | 1542 | 2380 | 0 | |||||||||||
39 | 3530 | 3085 | 2482 | 3669 | 1252 | 4435 | 4185 | 4091 | 3543 | 2497 | 1997 | 2506 | 1232 | 1380 | 2867 | 3398 | 4752 | 4051 | 4652 | 2525 | 1136 | 3132 | 1833 | 1852 | 967 | 3349 | 4532 | 4218 | 2096 | 4216 | 4062 | 533 | 2963 | 1981 | 3515 | 3883 | 4629 | 3952 | 0 | ||||||||||
40 | 825 | 4564 | 1027 | 6011 | 3227 | 2681 | 2049 | 1319 | 676 | 5160 | 931 | 791 | 1656 | 1663 | 554 | 1476 | 3331 | 1881 | 2972 | 1474 | 2173 | 1040 | 1074 | 4687 | 1973 | 5709 | 2976 | 2241 | 3388 | 2606 | 1438 | 3245 | 1050 | 1909 | 6249 | 1913 | 2877 | 1127 | 2873 | 0 | |||||||||
41 | 2188 | 2756 | 1395 | 4638 | 2426 | 5053 | 4415 | 2544 | 2590 | 4318 | 2513 | 2912 | 2550 | 1932 | 2885 | 1241 | 5687 | 4248 | 5344 | 3542 | 3268 | 1479 | 2054 | 4285 | 2285 | 4397 | 5339 | 4614 | 1911 | 4967 | 3693 | 3612 | 3358 | 1124 | 5379 | 4286 | 5250 | 3197 | 3080 | 2374 | 0 | ||||||||
42 | 4820 | 1591 | 3617 | 1681 | 1169 | 6384 | 6051 | 5358 | 4993 | 937 | 3701 | 4277 | 3001 | 2736 | 4569 | 4287 | 6746 | 5903 | 6617 | 4455 | 3136 | 4211 | 3340 | 1272 | 2507 | 1363 | 6509 | 6121 | 1501 | 6179 | 5763 | 2187 | 4787 | 2718 | 2001 | 5772 | 6583 | 5518 | 2012 | 4392 | 3386 | 0 | |||||||
43 | 3489 | 7027 | 3891 | 7987 | 5313 | 550 | 1219 | 3632 | 3039 | 6795 | 2923 | 2403 | 3403 | 3915 | 2405 | 4390 | 437 | 1322 | 486 | 1923 | 3189 | 3969 | 3423 | 6022 | 3935 | 7667 | 287 | 955 | 5831 | 400 | 2115 | 4339 | 1926 | 4565 | 7738 | 1121 | 570 | 2658 | 4324 | 2943 | 5284 | 6314 | 0 | ||||||
44 | 1946 | 6186 | 2686 | 7502 | 4706 | 1224 | 482 | 1987 | 1486 | 6507 | 2137 | 1564 | 2860 | 3138 | 1289 | 2928 | 1948 | 355 | 1501 | 1641 | 3029 | 2553 | 2541 | 5892 | 3331 | 7190 | 1581 | 743 | 4994 | 1277 | 440 | 4265 | 1086 | 3548 | 7556 | 600 | 1380 | 1002 | 4046 | 1659 | 3997 | 5837 | 1676 | 0 | |||||
45 | 6835 | 3472 | 5661 | 1877 | 3241 | 7805 | 7635 | 7391 | 6934 | 1268 | 5459 | 5983 | 4697 | 4647 | 6338 | 6419 | 8005 | 7508 | 7989 | 5957 | 4527 | 6290 | 5213 | 1629 | 4312 | 1798 | 7844 | 7644 | 3704 | 7567 | 7537 | 3296 | 6436 | 4830 | 461 | 7322 | 7986 | 7395 | 3478 | 6285 | 5585 | 2205 | 7603 | 7521 | 0 | ||||
46 | 1542 | 5461 | 2023 | 6758 | 3962 | 1670 | 1054 | 1785 | 1112 | 5773 | 1394 | 827 | 2126 | 2395 | 555 | 2428 | 2334 | 887 | 1962 | 1071 | 2355 | 2012 | 1801 | 5178 | 2589 | 6446 | 1974 | 1231 | 4264 | 1609 | 763 | 3576 | 422 | 2839 | 6829 | 902 | 1866 | 951 | 3328 | 1012 | 3386 | 5095 | 1964 | 744 | 6805 | 0 | |||
47 | 2379 | 4390 | 1867 | 5360 | 2651 | 2704 | 2432 | 2879 | 2196 | 4249 | 711 | 892 | 756 | 1351 | 1297 | 2749 | 3098 | 2302 | 2939 | 777 | 711 | 2336 | 1077 | 3581 | 1284 | 5041 | 2838 | 2465 | 3209 | 2501 | 2404 | 1941 | 1244 | 2140 | 5267 | 2128 | 2904 | 2429 | 1755 | 1563 | 3125 | 3680 | 2662 | 2325 | 5208 | 1644 | 0 | ||
48 | 3744 | 2088 | 2560 | 2844 | 304 | 5230 | 4884 | 4296 | 3876 | 1914 | 2534 | 3109 | 1836 | 1592 | 3406 | 3337 | 5618 | 4736 | 5469 | 3302 | 2042 | 3189 | 2190 | 1639 | 1340 | 2528 | 5369 | 4957 | 1196 | 5032 | 4603 | 1381 | 3619 | 1751 | 3013 | 4608 | 5432 | 4380 | 1000 | 3254 | 2664 | 1169 | 5184 | 4670 | 3102 | 3928 | 2532 | 0 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"http://people.math.sfu.ca/~goddyn/Courses/800/Resources/Algorithms/TSPlowerbounds.pdf" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"import numpy\n", | |
"\n", | |
"def read_matrix_file(filename):\n", | |
" with open(filename) as matrix_file:\n", | |
" num_cities = len(matrix_file.readline().split(',')) - 1\n", | |
" values = numpy.zeros((num_cities, num_cities))\n", | |
"\n", | |
" for i in range(num_cities):\n", | |
" row = list(float(value) for value in matrix_file.readline().split(',')[1:] if value.strip())\n", | |
" values[i,:len(row)] = row\n", | |
" values[:len(row),i] = row\n", | |
"\n", | |
" return values" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"from scipy.sparse import csr_matrix\n", | |
"from scipy.sparse.csgraph import minimum_spanning_tree\n", | |
"\n", | |
"def one_tree_bound(graph, vertex):\n", | |
" s = sum(numpy.sort(graph[vertex,:])[:2])\n", | |
" \n", | |
" graph_minus_vertex = graph.copy()\n", | |
" graph_minus_vertex[vertex,:] = 0\n", | |
" graph_minus_vertex[:,vertex] = 0\n", | |
" \n", | |
" r = minimum_spanning_tree(graph_minus_vertex).sum()\n", | |
" t = r + s\n", | |
" \n", | |
" return r + s" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"1-tree lower cost bound (~10% below optimal): 134.0\n", | |
"1-tree lower distance bound: (~10% below optimal): 28510.0\n" | |
] | |
} | |
], | |
"source": [ | |
"distances = read_matrix_file('distance.csv')\n", | |
"costs = read_matrix_file('cost.csv')\n", | |
"\n", | |
"print('1-tree lower cost bound (~10% below optimal): {}'.format(\n", | |
" max(one_tree_bound(costs, v) for v in range(costs.shape[0]))))\n", | |
"print('1-tree lower distance bound: (~10% below optimal): {}'.format(\n", | |
" max(one_tree_bound(distances, v) for v in range(distances.shape[0]))))" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.4.4" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment