Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Задача коммивояжера (Европа)

9 апреля 2013 года в 11:21   Просмотров: 5206

TSP Европа (57 крупнейших городов)

 

Оптимальный маршрут по Европе

 

Описание

 

Матрица

    Амстердам Афины Барселона Белград Берлин Бирмингем Бремен Брюссель Будапешт Бухарест Валенсия Варшава Вена Вроцлав Гамбург Ганновер Генуя Гетеборг Глазго Дортмунд Дрезден Дублин Дюссельдорф Загреб Кельн Копенгаген Краков Лейпциг Лидс Лодзь Лондон Мадрид Малага Марсель Милан Мюнхен Неаполь Нюрнберг Осло Палермо Париж Познань Прага Рим Роттердам Сарагоса Севилья София Стамбул Стокгольм Тирана Турин Франкфурт Хельсинки Шеффилд Штутгарт Эссен  
0
Амстердам
0
2818
1536
1721
656
736
355
211
1401
2261
1875
1198
1148
964
465
374
1207
1096
1196
239
733
1131
227
1326
263
788
1218
632
536
1088
330
1769
2295
1237
1077
826
1852
658
1267
2554
502
895
877
1656
74
1577
2232
2110
2676
1436
2208
1236
441
1916
816
619
207
Амстердам
1
Афины
0
0
3091
1109
2350
3397
2622
2782
1481
1183
3431
2352
1721
2080
2646
2509
2246
3091
3857
2603
2151
3792
2610
1497
2572
2782
1878
2257
3502
2256
3193
3688
4059
2632
2124
2038
1083
2173
3376
1385
2886
2247
1998
1276
2832
3376
4074
801
1095
3424
721
2261
2384
3419
3477
2271
2625
Афины
2
Барселона
0
0
0
1993
1871
1692
1666
1340
1928
2584
350
2410
1832
2002
1778
1644
857
2407
2152
1446
1749
2087
1390
1598
1384
2100
2255
1711
1797
2310
1488
621
998
507
981
1375
1556
1444
2579
2263
1038
2115
1721
1360
1475
312
996
2379
2945
2747
2070
876
1337
3236
1772
1259
1424
Барселона
3
Белград
0
0
0
0
1249
2300
1521
1681
380
598
2329
1249
619
983
1540
1408
1151
1988
2760
1499
1048
2695
1507
394
1521
1680
772
1155
2405
1156
2096
2588
2979
1535
1026
940
1485
1076
2278
2192
1861
1149
901
1289
1735
2279
2977
397
962
2327
746
1163
1287
2321
2380
1174
1528
Белград
4
Берлин
0
0
0
0
0
1297
406
767
874
1735
2219
569
678
344
289
287
1168
742
1756
494
191
1691
559
1077
574
434
597
191
1402
479
1092
2315
2853
1542
1039
586
1705
439
1032
2412
1053
273
349
1509
692
2157
2781
1638
2204
1082
1988
1157
548
1561
1376
633
529
Берлин
5
Бирмингем
0
0
0
0
0
0
1020
567
1925
2785
2031
1835
1675
1605
1130
1015
1559
1762
467
805
1317
401
767
1853
782
1453
1858
1218
193
1728
203
1917
2440
1438
1497
1353
2259
1185
1932
2961
654
1532
1470
2063
677
1726
2381
2689
3255
2101
2699
1439
602
1603
147
1123
770
Бирмингем
6
Бремен
0
0
0
0
0
0
0
490
1141
2001
2007
932
950
738
127
128
1218
756
1479
234
485
1414
297
1262
315
449
961
375
1125
843
816
2055
2582
1341
1088
752
1871
584
928
2578
793
636
621
1675
391
1865
2521
1910
2476
1096
2140
1206
441
1575
1094
639
256
Бремен
7
Брюссель
0
0
0
0
0
0
0
0
1356
2217
1678
1299
1107
1047
600
483
1044
1230
1026
275
794
961
203
1289
212
916
1301
701
672
1209
363
1571
2097
1045
914
785
1686
616
1396
2393
308
1002
907
1490
151
1381
2038
2070
2635
1569
2167
1037
400
2049
647
557
240
Брюссель
8
Будапешт
0
0
0
0
0
0
0
0
0
866
2265
874
243
607
1164
1033
1087
1612
2384
1176
672
2319
1184
344
1146
1305
391
780
2030
781
1720
2524
2915
1471
962
684
1420
820
1902
2127
1486
773
525
1224
1411
2214
2912
769
1334
1951
1118
1099
963
1945
2004
920
1204
Будапешт
9
Бухарест
0
0
0
0
0
0
0
0
0
0
2922
1327
1104
1468
2025
1893
1742
2473
3245
2036
1533
3180
2044
985
2006
2165
1105
1640
2890
1368
2543
3179
3570
2126
1617
1545
2074
1681
2763
1909
2346
1634
1385
1878
2271
2868
3566
350
635
2812
889
1753
1824
2355
2827
1780
2065
Бухарест
10
Валенсия
0
0
0
0
0
0
0
0
0
0
0
2751
2169
2341
2117
1983
1196
2746
2491
1785
2088
2426
1730
1937
1723
2439
2595
2050
2136
2650
1827
355
621
847
1320
1714
1895
1783
2919
2602
1377
2454
2060
1699
1814
318
654
2719
3284
3086
2410
1215
1676
3565
2111
1598
1763
Валенсия
1
Варшава
0
0
0
0
0
0
0
0
0
0
0
0
684
365
854
826
1707
1308
2295
1032
707
2230
1098
1051
1113
1000
358
729
1940
133
1631
2854
3392
2080
1577
1125
1999
981
1597
2706
1591
313
757
1802
1234
2700
3323
1640
2205
1651
1989
1699
1090
1052
1915
1176
1071
Варшава
2
Вена
0
0
0
0
0
0
0
0
0
0
0
0
0
418
971
839
990
1418
2135
927
478
2070
935
376
896
1111
467
586
1780
592
1471
2427
2818
1374
865
435
1324
503
1708
2031
1236
584
331
1127
1162
2118
2816
1009
1574
1758
1254
1002
714
1756
1755
671
955
Вена
3
Вроцлав
0
0
0
0
0
0
0
0
0
0
0
0
0
0
628
625
1300
1084
2064
776
268
1999
841
780
831
776
271
373
1710
220
1400
2567
2969
1675
1173
724
1824
573
1369
2549
1288
168
328
1646
1000
2287
2985
1491
2057
1421
1841
1291
721
1425
1684
768
809
Вроцлав
4
Гамбург
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
151
1241
638
1590
344
476
1525
407
1286
425
330
882
399
1235
759
920
2165
2692
1451
1111
776
1894
607
814
2601
903
552
645
1698
501
1975
2632
1934
2499
977
2164
1230
492
1457
1204
655
366
Гамбург
5
Ганновер
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1098
781
1475
212
372
1410
278
1137
293
473
847
262
1120
729
811
2034
2560
1348
968
633
1751
464
963
2458
771
522
508
1555
410
1844
2500
1797
2362
1120
2027
1086
349
1600
1095
512
247
Ганновер
6
Генуя
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1868
2019
1006
1047
1954
994
753
956
1560
1441
1009
1664
1609
1355
1453
1844
400
136
624
711
742
2051
1418
913
1402
1019
515
1171
1144
1842
1534
2100
2208
1208
168
794
2687
1639
635
1025
Генуя
7
Гетеборг
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2221
975
932
2156
1038
1781
1056
315
1338
894
1867
1215
1552
2797
3324
2082
1743
1290
2408
1239
293
3115
1535
1008
1090
2212
1132
2607
3263
2379
2944
471
2659
1861
1124
950
1836
1287
997
Гетеборг
8
Глазго
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1265
1776
370
1227
2313
1242
1912
2318
1678
354
2187
404
2377
2900
1898
1957
1813
2719
1645
2391
3421
1114
1992
1930
2523
1137
2185
2840
3149
3715
2560
3158
1899
888
1889
406
985
1230
Глазго
9
Дортмунд
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
522
1200
70
1110
95
668
1029
418
910
937
601
1835
2362
1120
880
606
1652
438
1147
2359
573
730
659
1455
253
1645
2301
1891
2457
1315
1988
998
221
1795
885
418
37
Дортмунд
20
Дрезден
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1712
580
845
570
622
522
112
1422
486
1113
2285
2727
1415
912
463
1582
312
1220
2289
1026
361
150
1385
769
2026
2725
1439
2004
1270
1788
1030
460
1706
1397
507
548
Дрезден
1
Дублин
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1162
2248
1177
1847
2253
1613
333
2122
586
2312
2835
1833
1892
1748
2654
1580
2326
3356
1049
1927
1865
2458
1072
2120
2775
3084
3650
2495
3093
1828
1364
2975
597
1521
1166
Дублин
2
Дюссельдорф
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1117
40
733
1094
483
872
1003
563
1763
2290
1063
866
613
1638
444
1212
2345
501
796
735
1442
224
1573
2229
1898
2463
1380
1995
984
228
1860
847
404
35
Дюссельдорф
3
Загреб
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1074
1466
828
917
1958
953
1649
2193
2585
1141
632
546
1090
681
2064
1797
1389
946
693
894
1340
1884
2582
785
1350
2113
899
769
892
2118
1933
780
1134
Загреб
4
Кельн
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
747
1085
497
887
1017
578
1751
2278
1057
828
575
1600
406
1226
2307
489
810
696
1404
257
1561
2217
1860
2425
1394
1957
946
189
1874
862
366
71
Кельн
5
Копенгаген
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1029
585
1558
906
1243
2488
3015
1774
1434
981
2100
930
608
2807
1226
699
781
1903
824
2298
2954
2070
2635
658
2350
1553
815
1137
1527
978
689
Копенгаген
6
Краков
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
626
1963
263
1654
2799
3241
1831
1322
919
1780
827
1625
2487
1540
443
538
1584
1253
2541
3239
1166
1731
1675
1515
1459
975
1348
1938
1021
1063
Краков
7
Лейпциг
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1324
635
1014
2216
2697
1386
883
430
1549
283
1183
2256
957
427
256
1353
667
2001
2700
1545
2110
1231
1799
1001
392
1711
1298
477
450
Лейпциг
8
Лидс
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1833
313
2022
2545
1544
1602
1458
2364
1290
2037
3066
760
1637
1575
2168
782
1831
2486
2795
3360
2206
2804
1544
680
1681
58
778
895
Лидс
9
Лодзь
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1521
2746
3284
1973
1467
1015
1903
791
1490
2610
1484
203
546
1707
1124
2505
3203
1544
2110
1541
1893
1509
980
1177
1805
985
961
Лодзь
30
Лондон
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1713
2236
1234
1293
1149
2055
981
1722
2757
450
1328
1266
1859
473
1521
2177
2485
3051
1891
2494
1235
765
2371
269
919
566
Лондон
1
Мадрид
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
530
1103
1577
1971
2152
2039
2968
2859
1271
2552
2315
1956
1708
314
528
2976
3541
3136
2666
1472
1852
3616
1997
1855
1804
Мадрид
2
Малага
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1493
1949
2342
2523
2411
3491
3231
1794
3082
2688
2327
2232
838
205
3347
3912
3659
3038
1843
2304
4141
2520
2226
2329
Малага
3
Марсель
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
522
1010
1098
1119
2252
1805
775
1790
1396
902
1176
794
1492
1922
2487
2422
1612
372
1012
2901
1518
934
1099
Марсель
4
Милан
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
494
775
612
1920
1483
850
1271
888
579
1040
1267
1965
1416
1981
2077
1150
146
663
2557
1577
504
895
Милан
5
Мюнхен
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1117
169
1577
1824
829
822
386
921
840
1658
2356
1330
1896
1627
1427
614
392
2106
1433
232
633
Мюнхен
6
Неаполь
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1288
2696
724
1613
1941
1505
227
1816
1844
2542
1053
1550
2746
527
868
1511
3070
2339
1271
1752
Неаполь
7
Нюрнберг
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1420
1996
759
678
303
1092
672
1730
2428
1467
2032
1482
1564
734
224
1962
1265
211
465
Нюрнберг
8
Осло
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3414
1705
1293
1375
2511
1303
2777
3433
2664
3229
523
2944
2042
1305
985
2006
1468
1168
Осло
9
Палермо
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2314
2643
2207
930
2518
2546
3244
1561
1855
3448
937
1570
2213
3772
3041
1973
2454
Палермо
40
Париж
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1285
1035
1414
442
1079
1735
2174
2740
1869
1998
776
573
2349
734
624
537
Париж
1
Познань
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
434
1748
931
2397
3021
1538
2104
1348
1888
1396
787
1356
1612
873
768
Познань
2
Прага
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1305
913
2002
2700
1291
1856
1427
1640
1006
509
1752
1550
483
692
Прага
3
Рим
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1620
1648
2346
1678
1749
2550
726
672
1315
2874
2143
1075
1556
Рим
4
Роттердам
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1517
2173
2124
2690
1469
2222
1168
454
1949
757
605
221
Роттердам
5
Сарагоса
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
845
2671
3237
2944
2362
1168
1629
3424
1805
1551
1612
Сарагоса
6
Севилья
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3364
3929
3599
3055
1860
2323
4079
2461
2246
2267
Севилья
7
София
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
565
2717
539
1553
1676
2711
2769
1563
1918
София
8
Стамбул
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3282
1021
2118
2242
3276
3335
2129
2483
Стамбул
9
Стокгольм
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2998
2200
1463
481
2175
1626
1337
Стокгольм
50
Тирана
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1261
1774
3062
2778
1600
2015
Тирана
1
Турин
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
785
2679
1519
626
1017
Турин
2
Франкфурт
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1943
1049
205
250
Франкфурт
3
Хельсинки
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2655
2106
1817
Хельсинки
4
Шеффилд
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
749
850
Шеффилд
5
Штутгарт
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
426
Штутгарт
6
Эссен
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Эссен

2 комментариев

#70
Илья (гость) пишет:
13:44 27 ноября 2014 года
Я подозреваю, что применялся какой либо приближенный алгоритм решения комбинаторной задачи (например, метод ветвей и границ или метод группового учета аргумента). Доказать оптимальность - переборная задача.
Куда интереснее, каким алгоритмом решения пользовались при составлении маршрута.
#41
Рустем (гость) пишет:
20:08 2 ноября 2013 года
Цитата с первой странички (и не только с нее): "... классы P и NP можно описать так: P - это вычислительные задачи, которые легко решить; NP - задачи, для которых легко проверить, верно ли предполагаемое решение.".
Тот факт, что предоставленный здесь маршрут замкнут и проходит через 57 городов, вполне очевиден. При некоторой внимательности десятки таких ломаных легко провести даже для сотни вершин графа, просто не отрывая карандаша от карты. Подобные ломаные А теперь, пожалуйста, докажите, что это - искомое решение данного индивидуального случая задачи "Коммивояжер", т.е. объявленный маршрут имеет наименьшую длину среди прочих (57!-1) подобных "ожерелий" с 57 бусинами. Успехов :)

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта