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

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

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	Эссен

LMatrix

Теги (ключевые слова): Европа, задача коммивояжера, TSP, город | Комментарии (2)

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

#70

Илья (гость) пишет:

13:44 27 ноября 2014 года

Я подозреваю, что применялся какой либо приближенный алгоритм решения комбинаторной задачи (например, метод ветвей и границ или метод группового учета аргумента). Доказать оптимальность - переборная задача.
Куда интереснее, каким алгоритмом решения пользовались при составлении маршрута.

#41

Рустем (гость) пишет:

20:08 2 ноября 2013 года

Цитата с первой странички (и не только с нее): "... классы P и NP можно описать так: P - это вычислительные задачи, которые легко решить; NP - задачи, для которых легко проверить, верно ли предполагаемое решение.".
Тот факт, что предоставленный здесь маршрут замкнут и проходит через 57 городов, вполне очевиден. При некоторой внимательности десятки таких ломаных легко провести даже для сотни вершин графа, просто не отрывая карандаша от карты. Подобные ломаные А теперь, пожалуйста, докажите, что это - искомое решение данного индивидуального случая задачи "Коммивояжер", т.е. объявленный маршрут имеет наименьшую длину среди прочих (57!-1) подобных "ожерелий" с 57 бусинами. Успехов :)