算法分析：货郎担问题求解分析

【虎.无名】看到一个帖子 【迷题：走遍全国各省会的最短路线问题 】http://www.iteye.com/topic/214846  想起以前上MSE时候做的一个《算法》的课程设计。数据如下：

 

城市 北京 上海 天津 石家庄 太原 呼和浩特 沈阳 长春 哈尔滨 济南 南京 合肥 杭州 南昌 福州 台北 郑州 武汉 长沙 广州 海口 南宁 西安 银川 兰州 西宁 乌鲁木齐 成都 贵阳 昆明 拉萨
北京 0 1078 119 263 398 401 634 866 1061 367 905 902 1135 1255 1568 1729 626 1052 1343 1893 2286 2050 909 879 1178 1321 2399 1511 1732 2085 2558
上海 1078 0 963 989 1096 1381 1189 1451 1679 735 269 399 160 601 606 686 824 685 881 1210 1666 1599 1218 1597 1717 1908 3265 1655 1522 1956 2909
天津 119 963 0 262 426 504 605 860 1068 271 798 806 1025 1169 1465 1620 582 981 1277 1819 2223 2001 913 947 1228 1381 2502 1518 1702 2071 2604
石家庄 263 989 262 0 171 394 867 1117 1318 266 769 730 1010 1049 1403 1590 376 823 1104 1662 2042 1794 654 720 977 1138 2336 1258 1469 1823 2347
太原 398 1096 426 171 0 341 1025 1264 1457 412 854 790 1095 1065 1452 1655 359 816 1074 1637 1991 1720 516 555 807 968 2192 1114 1368 1700 2179
呼和浩特 401 1381 504 394 341 0 987 1171 1325 650 1161 1114 1403 1405 1783 1978 700 1157 1411 1973 2315 2029 770 535 870 981 1999 1320 1649 1942 2237
沈阳 634 1189 605 867 1025 987 0 281 512 790 1155 1227 1314 1607 1785 1870 1158 1484 1782 2280 2714 2535 1518 1504 1812 1950 2909 2123 2278 2662 3192
长春 866 1451 860 1117 1264 1171 281 0 232 1065 1432 1507 1582 1887 2053 2124 1428 1765 2063 2561 2995 2815 1770 1703 2026 2151 2998 2375 2551 2929 3402
哈尔滨 1061 1679 1068 1318 1457 1325 512 232 0 1287 1664 1738 1813 2118 2282 2349 1645 1993 2291 2792 3225 3041 1970 1860 2193 2306 3057 2572 2768 3139 3561
济南 367 735 271 266 412 650 790 1065 1287 0 540 537 775 899 1201 1367 374 720 1019 1553 1964 1757 780 964 1185 1359 2599 1370 1488 1878 2528
南京 905 269 798 769 854 1161 1155 1432 1664 540 0 141 242 467 668 827 560 456 704 1136 1581 1459 949 1335 1448 1640 3004 1404 1320 1750 2653
合肥 902 399 806 730 790 1114 1227 1507 1738 537 141 0 328 380 674 866 463 319 584 1054 1490 1344 824 1237 1328 1520 2902 1264 1185 1614 2514
杭州 1135 160 1025 1010 1095 1403 1314 1582 1813 775 242 328 0 447 472 596 787 566 733 1051 1506 1441 1147 1564 1653 1845 3229 1543 1378 1812 2799
南昌 1255 601 1169 1049 1065 1405 1607 1887 2118 899 467 380 447 0 441 687 706 270 291 674 1115 1004 908 1404 1401 1589 3020 1166 938 1370 2414
福州 1568 606 1465 1403 1452 1783 1785 2053 2282 1201 668 674 472 441 0 252 1103 705 666 697 1137 1171 1348 1836 1842 2030 3461 1573 1256 1666 2800
台北 1729 686 1620 1590 1655 1978 1870 2124 2349 1367 827 866 596 687 252 0 1317 945 916 869 1276 1366 1589 2067 2087 2276 3704 1824 1493 1892 3046
郑州 626 824 582 376 359 700 1158 1428 1645 374 560 463 787 706 1103 1317 0 459 730 1291 1666 1424 437 777 906 1094 2444 1003 1123 1505 2194
武汉 1052 685 981 823 816 1157 1484 1765 1993 720 456 319 566 270 705 945 459 0 299 842 1243 1054 644 1134 1144 1334 2758 976 867 1295 2233
长沙 1343 881 1277 1104 1074 1411 1782 2063 2291 1019 704 584 733 291 666 916 730 299 0 563 946 762 778 1298 1229 1408 2848 908 647 1080 2141
广州 1893 1210 1819 1662 1637 1973 2280 2561 2792 1553 1136 1054 1051 674 697 869 1291 842 563 0 455 505 1306 1825 1698 1858 3278 1235 761 1087 2324
海口 2286 1666 2223 2042 1991 2315 2714 2995 3225 1964 1581 1490 1506 1115 1137 1276 1666 1243 946 455 0 373 1587 2082 1889 2021 3378 1339 816 959 2220
南宁 2050 1599 2001 1794 1720 2029 2535 2815 3041 1757 1459 1344 1441 1004 1171 1366 1424 1054 762 505 373 0 1274 1748 1533 1657 3005 971 449 619 1883
西安 909 1218 913 654 516 770 1518 1770 1970 780 949 824 1147 908 1348 1589 437 644 778 1306 1587 1274 0 521 507 699 2114 604 880 1187 1758
银川 879 1597 947 720 555 535 1504 1703 1860 964 1335 1237 1564 1404 1836 2067 777 1134 1298 1825 2082 1748 521 0 346 448 1668 885 1318 1526 1701
兰州 1178 1717 1228 977 807 870 1812 2026 2193 1185 1448 1328 1653 1401 1842 2087 906 1144 1229 1698 1889 1533 507 346 0 192 1622 596 1087 1226 1380
西宁 1321 1908 1381 1138 968 981 1950 2151 2306 1359 1640 1520 1845 1589 2030 2276 1094 1334 1408 1858 2021 1657 699 448 192 0 1440 691 1207 1288 1255
乌鲁木齐 2399 3265 2502 2336 2192 1999 2909 2998 3057 2599 3004 2902 3229 3020 3461 3704 2444 2758 2848 3278 3378 3005 2114 1668 1622 1440 0 2053 2570 2494 1592
成都 1511 1655 1518 1258 1114 1320 2123 2375 2572 1370 1404 1264 1543 1166 1573 1824 1003 976 908 1235 1339 971 604 885 596 691 2053 0 523 641 1257
贵阳 1732 1522 1702 1469 1368 1649 2278 2551 2768 1488 1320 1185 1378 938 1256 1493 1123 867 647 761 816 449 880 1318 1087 1207 2570 523 0 434 1574
昆明 2085 1956 2071 1823 1700 1942 2662 2929 3139 1878 1750 1614 1812 1370 1666 1892 1505 1295 1080 1087 959 619 1187 1526 1226 1288 2494 641 434 0 1266
拉萨 2558 2909 2604 2347 2179 2237 3192 3402 3561 2528 2653 2514 2799 2414 2800 3046 2194 2233 2141 2324 2220 1883 1758 1701 1380 1255 1592 1257 1574 1266 0

 

课程名称 计算机算法设计与分析（The Desigh and Analysis of computer Algorithms ）
姓 名 周培德 英文名字 Zhou Peide 性别 男
学 历 大学 专业 数学、计算机
现就职单位 北京理工大学计算机系 出生年月 1941.3
主干课程主讲教师
教育背景（大学起） 1960.8-1965.7武汉大学数学系 
工作经历 1965.7—至今　北京工业学院即现在的北京理工大学
1982-2001年主讲《算法设计与分析》
1989-2001年主讲《算法理论》另外，还主讲《组合数学》《可计算性理论》《高等数学》等课程，出版两部研究生教材，一部学术专著，在核心期刊发表学术论文56篇。
软件项目和工程实践经验 1972－1976年从事计算机编程及台式机的设计工作。1982－1983从事函数逼近编程工作。
获奖励与荣誉证书 《计算机算法设计与分析》荣获第三届部级优秀教材一等奖。
个人评价 本人善于搞科研，也愿意教学。
联系方式 010-68913991

 

算法分析：货郎担问题求解分析

一、 对图4-6所示算法的修改：

1，从开始到终止都采用31*31的二维数组保存耗费矩阵，但增加了两个BitSet分别记录有效行、列的序号；这样，删除行、列，只需要对BitSet做一下设置就可以了，而不需要遍历行列来把每个元素设置为MAX。

2，先用贪心法，可以提前排除部分叶子节点，从而减少循环次数。当N>25时，采用蔡胜的方法，一直选择右分支选择出一条路径，效果更好。具体办法是：先从右节点分支到最下层，快速求出第一个Z0值，只需要循环N-1次，就可求得，效果在N>25时比贪心法耗，而且代码简单，只需要一、两行的修改。代码如下：
相关代码：
 if (Z0==MAX)
    nodeX = nodeY;  //先从右分支获取第一次最小耗费Z0；
   else nodeX = S2_min(S2); //获取拥有最小耗费的叶子节点；
具体数据（方法四）：
贪心法＋31：选择基地为城市v0时，耗费为19614
贪心法＋31：选择基地为城市v3时，耗费为18773
贪心法＋31：选择基地为城市v5时，耗费为18620
贪心法＋31：选择基地为城市v6时，耗费为18209
贪心法＋31：选择基地为城市v7时，耗费为18074
贪心法＋31：选择基地为城市v8时，耗费为17902
贪心法＋31：循环：#0次，耗时40(ms)
贪心法＋31：内存：Total：43778048，Free：43479088，Used：298168(B)
贪心法＋31：路线：8 - 7 - 6 - 2 - 0 - 3 - 4 - 5 - 23 - 24 - 25 - 27 - 28 - 29 - 21 - 20 - 19 - 18 - 13 - 17 - 11 - 10 - 12 - 1 - 14 - 15 - 16 - 9 - 22 - 30 - 26 - 8...最小费用:17902
直接右分支求解
分支限界31：更新最小花费Z0:16169, #30
分析：采用蔡胜的办法，直接右分支到最底层，由此产生的最小耗费Z0，在城市数目N>25的情况下，一般情况下比贪心法更低，对于减少叶子结点的效果更好。

城市数目 贪心法 贪心法改进 先行后列，直接右分支 先列后行，直接右分支
31 19614 17902 16169 16121
30 17863 16666 15672 15000
29 17259 16062 14697 14712
28 16975 15987 16552 16375
27 16379 14985 14592 14628
26 11984 11958 11833 11968
25 11600 11600 11638 11674
24 11268 11268 11515 11530
23 10340 10321 10642 10589
22 9718 9699 11935 11604
21 9311 9292 9263 9111

3，由于框图9中，没有定义叶子节点的存储结构和插入、查找对应的算法，所以可以采取多几种方式，目前尝试了以下几种方法：
方法一：每次遍历整个树，检索所有叶子节点，比较叶子的权值，找出最小；
方法二：使用Vector保存每次产生的叶子节点，每次搜索Vector找出最小。(复杂度为n；如每次都对Vector排序，复杂度n logn，反而得不偿失)
方法三：使用有序链表LinkedList保存叶子节点，动态维护保持有序，获取最小叶子，复杂度为1，插入链表复杂度为n；（使用java语言编写，对TSP31求解，需要1782342 ms，将近30分钟，根据其他同学的结果用C语言编写大概是12分钟）
具体数据（方法三）：
分支限界31：循环：82364次；直接右分支费用下限 Z0=16169
分支限界31：时间：1042431555008 - 1042433337350 耗时1782342 ms
方法四：由于分支过程中，存在大量节点的权值是相同的（在）这样极大影响插入排序效率，故根据权值进行分类，将大大降低获取最小叶子问题的规模。具体办法是：使用TreeMap（一种实现了排序映射表接口的红-黑树），其关键字是耗费下限，关键字对应的值是一个LinkedList，用来保存所有w相同的节点。查找过程，先根据耗费w查找对应的LinkedList，然后取出LinkedList的第一个节点；插入过程也类似，直接插入对应LinkedList的首节点就可以了。两者的复杂度都是常数。
具体数据：
TSP－20中 4777个节点，只有278个不同的权值，平均有17个节点的权值是相同的
TSP－31中78107个节点，只有766个不同的权值，平均有101个节点的权值是相同的
优先原则：
1> 最小权值的节点优；
2> 相同权值节点，右分支优先；
3> 相同权值节点，新分支的节点优先；
叶子的动态维护过程（方法三、方法四）：
1> 初始化，S2.add(TOP);
2> 分支时：S2.add(X.left), S2.add(X.right), S2.remove(X);
3> 更新最小耗费Z0时：清楚S2中所有耗费>Z0的节点；
定义接口
public interface ch4_tsp_leafs {  //定义接口
 public String  size();   //显示大小；
 public String  toString();  //用于显示输出
 public void add(int kk, Object oo, int sn); //按从小到大排序加入，如果有相同键，加入最前
 public Boolean  remove(int kk, Object oo); //删除单个对象，减少叶子节点集合的尺寸
 public object removeFirst();  //获取最小的叶子节点，如果有相同键值的，取第一个；
 public int  removeBig(int limit);  //删除所有键值大于limit的所有节点；
}
具体数据（方法四）：
先行后列31：循环：#82364次，耗时250080(ms)
先行后列31：内存：Total：43778048，Free：30300112，Used：13477136(B)
先行后列31：路线：0 - 8 - 7 - 6 - 2 - 9 - 11 - 10 - 1 - 12 - 15 - 14 - 13 - 17 - 18 - 19 - 20 - 21 - 28 - 29 - 27 - 30 - 26 - 25 - 24 - 23 - 22 - 16 - 3 - 4 - 5 - 0...最小费用:15404
先列后行31：循环：#81915次，耗时240616(ms)
先列后行31：内存：Total：43778048，Free：30403432，Used：13373816(B)
先列后行31：路线：0 - 5 - 4 - 3 - 16 - 22 - 23 - 24 - 25 - 26 - 30 - 27 - 29 - 28 - 21 - 20 - 19 - 18 - 17 - 13 - 14 - 15 - 12 - 1 - 10 - 11 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:15404

二、 按先行归约后列归约；先列归约后行归约顺序，执行图4-6所示算法，比较结果是否相同，用31＊31矩阵。（20分）
经过分析，两者均可求得最优解，线路正好相反。两者循环次数稍有不同，但平均性能一样，具体数据如下：
先行后列31：循环：#82364次，耗时250080(ms)
先行后列31：内存：Total：43778048，Free：30300112，Used：13477136(B)
先行后列31：路线：0 - 8 - 7 - 6 - 2 - 9 - 11 - 10 - 1 - 12 - 15 - 14 - 13 - 17 - 18 - 19 - 20 - 21 - 28 - 29 - 27 - 30 - 26 - 25 - 24 - 23 - 22 - 16 - 3 - 4 - 5 - 0...最小费用:15404
先列后行31：循环：#81915次，耗时240616(ms)
先列后行31：内存：Total：43778048，Free：30403432，Used：13373816(B)
先列后行31：路线：0 - 5 - 4 - 3 - 16 - 22 - 23 - 24 - 25 - 26 - 30 - 27 - 29 - 28 - 21 - 20 - 19 - 18 - 17 - 13 - 14 - 15 - 12 - 1 - 10 - 11 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:15404

三、 用贪心法先选择Z0的值，再执行图4-6所示算法，是否能减少运行时间。用31＊31矩阵。（22分）
对于25节点以下，有一定效果，但是对于31节点，作用不大，不如一直右分支求得第一条路径。（详细情况见上面部分：一、2的分析）

四、 对搜索过程增加约束条件（比如，寻找不含边（i , j）的路径），再执行图4-6所示算法，是否能缩短求解时间。用31＊31矩阵。（20分）

如果去掉的边（i，j）恰好时本次规约的时候选择的用于分支的边，那么可能会对产生影响

五、 第四章P70，例13，动态规划求解，用31＊31矩阵。（20分）
由于需要保存中间计算结果用于最后回溯路径，需要的消耗巨大的内存资源。求解17城市的时候，需要51M内存，求解21城市的时候需要999M内存，无法继续了 ：（
具体数据：
动态规划16：循环：#245761次，耗时12675(ms)
动态规划16：内存：Total：87818240，Free：63718504，Used：24098600(B)
动态规划16：路线：0 - 2 - 8 - 7 - 6 - 1 - 12 - 15 - 14 - 13 - 11 - 10 - 9 - 3 - 4 - 5 - 0...最小费用:6578
动态规划16：费用: 北京-119-天津-1068-哈尔滨-232-长春-281-沈阳-1189-上海-160-杭州-596-台北-252-福州-441-南昌-380-合肥-141-南京-540-济南-266-石家庄-171-太原-341-呼和浩特-401-北京 = 总费用：6578
动态规划17：循环：#524289次，耗时30029(ms)
动态规划17：内存：Total：97124352，Free：45218648，Used：51904568(B)
动态规划17：路线：0 - 5 - 4 - 3 - 16 - 11 - 13 - 14 - 15 - 12 - 1 - 10 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:6840
动态规划17：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-463-合肥-380-南昌-441-福州-252-台北-596-杭州-160-上海-269-南京-540-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：6840

六、 TSP问题结果输出（N=17、19、21、25、31）
使用机器 SunOS E250 5.9 Generic_112233-01 sun4u sparc SUNW,Ultra-250
----------------------------------------------
贪心法＋17：选择基地为城市v0时，耗费为7661
贪心法＋17：选择基地为城市v4时，耗费为7642
贪心法＋17：循环：#0次，耗时42(ms)
贪心法＋17：内存：Total：87818240，Free：87660192，Used：156920(B)
贪心法＋17：路线：4 - 3 - 2 - 0 - 9 - 16 - 11 - 10 - 12 - 1 - 13 - 14 - 15 - 6 - 7 - 8 - 5 - 4...最小费用:7642
最优结果17：路线：0 > 5 > 4 > 3 > 16 > 11 > 13 > 14 > 15 > 12 > 1 > 10 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:6840
贪心法＋17：费用: 太原-171-石家庄-262-天津-119-北京-367-济南-374-郑州-463-合肥-141-南京-242-杭州-160-上海-601-南昌-441-福州-252-台北-1870-沈阳-281-长春-232-哈尔滨-1325-呼和浩特-341-太原 = 总费用：7642
----------------------------------------------
动态规划17：循环：#524289次，耗时30029(ms)
动态规划17：内存：Total：97124352，Free：45218648，Used：51904568(B)
动态规划17：路线：0 - 5 - 4 - 3 - 16 - 11 - 13 - 14 - 15 - 12 - 1 - 10 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:6840
最优结果17：路线：0 > 5 > 4 > 3 > 16 > 11 > 13 > 14 > 15 > 12 > 1 > 10 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:6840
动态规划17：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-463-合肥-380-南昌-441-福州-252-台北-596-杭州-160-上海-269-南京-540-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：6840
----------------------------------------------
分支限界17：初始最小花费Z0:999999, #0
分支限界17：更新最小花费Z0:7068, #16
分支限界17：更新最小花费Z0:6840, #4005
先行后列17：循环：#4005次，耗时17533(ms)
先行后列17：内存：Total：97124352，Free：47139824，Used：49983392(B)
先行后列17：路线：0 - 8 - 7 - 6 - 2 - 9 - 10 - 1 - 12 - 15 - 14 - 13 - 11 - 16 - 3 - 4 - 5 - 0...最小费用:6840
最优结果17：路线：0 > 5 > 4 > 3 > 16 > 11 > 13 > 14 > 15 > 12 > 1 > 10 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:6840
先行后列17：费用: 北京-1061-哈尔滨-232-长春-281-沈阳-605-天津-271-济南-540-南京-269-上海-160-杭州-596-台北-252-福州-441-南昌-380-合肥-463-郑州-376-石家庄-171-太原-341-呼和浩特-401-北京 = 总费用：6840
----------------------------------------------
分支限界17：初始最小花费Z0:999999, #0
分支限界17：更新最小花费Z0:7068, #16
分支限界17：更新最小花费Z0:6840, #3972
先列后行17：循环：#3972次，耗时14646(ms)
先列后行17：内存：Total：97124352，Free：47076640，Used：50046576(B)
先列后行17：路线：0 - 5 - 4 - 3 - 16 - 11 - 13 - 14 - 15 - 12 - 1 - 10 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:6840
最优结果17：路线：0 > 5 > 4 > 3 > 16 > 11 > 13 > 14 > 15 > 12 > 1 > 10 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:6840
先列后行17：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-463-合肥-380-南昌-441-福州-252-台北-596-杭州-160-上海-269-南京-540-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：6840
----------------------------------------------
贪心法＋19：选择基地为城市v0时，耗费为8366
贪心法＋19：选择基地为城市v4时，耗费为8347
贪心法＋19：循环：#0次，耗时43(ms)
贪心法＋19：内存：Total：87818240，Free：87659224，Used：157888(B)
贪心法＋19：路线：4 - 3 - 2 - 0 - 9 - 16 - 17 - 13 - 18 - 11 - 10 - 12 - 1 - 14 - 15 - 6 - 7 - 8 - 5 - 4...最小费用:8347
最优结果19：路线：0 > 5 > 4 > 3 > 16 > 17 > 18 > 13 > 14 > 15 > 12 > 1 > 10 > 11 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:7184
贪心法＋19：费用: 太原-171-石家庄-262-天津-119-北京-367-济南-374-郑州-459-武汉-270-南昌-291-长沙-584-合肥-141-南京-242-杭州-160-上海-606-福州-252-台北-1870-沈阳-281-长春-232-哈尔滨-1325-呼和浩特-341-太原 = 总费用：8347
----------------------------------------------
动态规划19：TSP18=116MB,TSP19=333MB,消耗内存太大,该算法无法求解
分支限界19：初始最小花费Z0:999999, #0
分支限界19：更新最小花费Z0:7411, #18
分支限界19：更新最小花费Z0:7184, #2804
先行后列19：循环：#2804次，耗时5829(ms)
先行后列19：内存：Total：87818240，Free：87222976，Used：594128(B)
先行后列19：路线：0 - 8 - 7 - 6 - 2 - 9 - 11 - 10 - 1 - 12 - 15 - 14 - 13 - 18 - 17 - 16 - 3 - 4 - 5 - 0...最小费用:7184
最优结果19：路线：0 > 5 > 4 > 3 > 16 > 17 > 18 > 13 > 14 > 15 > 12 > 1 > 10 > 11 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:7184
先行后列19：费用: 北京-1061-哈尔滨-232-长春-281-沈阳-605-天津-271-济南-537-合肥-141-南京-269-上海-160-杭州-596-台北-252-福州-441-南昌-291-长沙-299-武汉-459-郑州-376-石家庄-171-太原-341-呼和浩特-401-北京 = 总费用：7184
----------------------------------------------
分支限界19：初始最小花费Z0:999999, #0
分支限界19：更新最小花费Z0:7358, #18
分支限界19：更新最小花费Z0:7184, #2793
先列后行19：循环：#2793次，耗时5986(ms)
先列后行19：内存：Total：87818240，Free：87229944，Used：587160(B)
先列后行19：路线：0 - 5 - 4 - 3 - 16 - 17 - 18 - 13 - 14 - 15 - 12 - 1 - 10 - 11 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:7184
最优结果19：路线：0 > 5 > 4 > 3 > 16 > 17 > 18 > 13 > 14 > 15 > 12 > 1 > 10 > 11 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:7184
先列后行19：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-459-武汉-299-长沙-291-南昌-441-福州-252-台北-596-杭州-160-上海-269-南京-141-合肥-537-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：7184
----------------------------------------------
贪心法＋21：选择基地为城市v0时，耗费为9311
贪心法＋21：选择基地为城市v5时，耗费为9292
贪心法＋21：循环：#0次，耗时31(ms)
贪心法＋21：内存：Total：87818240，Free：87657128，Used：159984(B)
贪心法＋21：路线：5 - 4 - 3 - 2 - 0 - 9 - 16 - 17 - 13 - 18 - 19 - 20 - 14 - 15 - 12 - 1 - 10 - 11 - 6 - 7 - 8 - 5...最小费用:9292
最优结果21：路线：0 > 5 > 4 > 3 > 16 > 17 > 13 > 18 > 20 > 19 > 14 > 15 > 12 > 1 > 10 > 11 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:8812
贪心法＋21：费用: 呼和浩特-341-太原-171-石家庄-262-天津-119-北京-367-济南-374-郑州-459-武汉-270-南昌-291-长沙-563-广州-455-海口-1137-福州-252-台北-596-杭州-160-上海-269-南京-141-合肥-1227-沈阳-281-长春-232-哈尔滨-1325-呼和浩特 = 总费用：9292
----------------------------------------------
动态规划21：TSP18=116MB,TSP19=333MB,消耗内存太大,该算法无法求解
分支限界21：初始最小花费Z0:999999, #0
分支限界21：更新最小花费Z0:9263, #20
分支限界21：更新最小花费Z0:8812, #11214
先行后列21：循环：#11214次，耗时27668(ms)
先行后列21：内存：Total：87818240，Free：86133528，Used：1683576(B)
先行后列21：路线：0 - 8 - 7 - 6 - 2 - 9 - 11 - 10 - 1 - 12 - 15 - 14 - 19 - 20 - 18 - 13 - 17 - 16 - 3 - 4 - 5 - 0...最小费用:8812
最优结果21：路线：0 > 5 > 4 > 3 > 16 > 17 > 13 > 18 > 20 > 19 > 14 > 15 > 12 > 1 > 10 > 11 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:8812
先行后列21：费用: 北京-1061-哈尔滨-232-长春-281-沈阳-605-天津-271-济南-537-合肥-141-南京-269-上海-160-杭州-596-台北-252-福州-697-广州-455-海口-946-长沙-291-南昌-270-武汉-459-郑州-376-石家庄-171-太原-341-呼和浩特-401-北京 = 总费用：8812
----------------------------------------------
分支限界21：初始最小花费Z0:999999, #0
分支限界21：更新最小花费Z0:9111, #20
分支限界21：更新最小花费Z0:8812, #11164
先列后行21：循环：#11164次，耗时26069(ms)
先列后行21：内存：Total：87818240，Free：85903912，Used：1913192(B)
先列后行21：路线：0 - 5 - 4 - 3 - 16 - 17 - 13 - 18 - 20 - 19 - 14 - 15 - 12 - 1 - 10 - 11 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:8812
最优结果21：路线：0 > 5 > 4 > 3 > 16 > 17 > 13 > 18 > 20 > 19 > 14 > 15 > 12 > 1 > 10 > 11 > 9 > 2 > 6 > 7 > 8 > 0...最小费用:8812
先列后行21：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-459-武汉-270-南昌-291-长沙-946-海口-455-广州-697-福州-252-台北-596-杭州-160-上海-269-南京-141-合肥-537-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：8812
----------------------------------------------
贪心法＋25：选择基地为城市v0时，耗费为11600
贪心法＋25：循环：#0次，耗时32(ms)
贪心法＋25：内存：Total：87818240，Free：87655904，Used：161208(B)
贪心法＋25：路线：0 - 2 - 3 - 4 - 5 - 23 - 24 - 22 - 16 - 9 - 11 - 10 - 12 - 1 - 13 - 17 - 18 - 19 - 20 - 21 - 14 - 15 - 6 - 7 - 8 - 0...最小费用:11600
最优结果25：
贪心法＋25：费用: 北京-119-天津-262-石家庄-171-太原-341-呼和浩特-535-银川-346-兰州-507-西安-437-郑州-374-济南-537-合肥-141-南京-242-杭州-160-上海-601-南昌-270-武汉-299-长沙-563-广州-455-海口-373-南宁-1171-福州-252-台北-1870-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：11600
----------------------------------------------
动态规划25：TSP18=116MB,TSP19=333MB,消耗内存太大,该算法无法求解
分支限界25：初始最小花费Z0:999999, #0
分支限界25：更新最小花费Z0:11638, #24
分支限界25：更新最小花费Z0:10312, #301074
先行后列25：循环：#301074次，耗时1140674(ms)
先行后列25：内存：Total：89792512，Free：44655888，Used：45135480(B)
先行后列25：路线：0 - 8 - 7 - 6 - 2 - 9 - 11 - 10 - 1 - 12 - 15 - 14 - 19 - 20 - 21 - 18 - 13 - 17 - 16 - 22 - 24 - 23 - 5 - 4 - 3 - 0...最小费用:10312
最优结果25：
先行后列25：费用: 北京-1061-哈尔滨-232-长春-281-沈阳-605-天津-271-济南-537-合肥-141-南京-269-上海-160-杭州-596-台北-252-福州-697-广州-455-海口-373-南宁-762-长沙-291-南昌-270-武汉-459-郑州-437-西安-507-兰州-346-银川-535-呼和浩特-341-太原-171-石家庄-263-北京 = 总费用：10312
----------------------------------------------
分支限界25：初始最小花费Z0:999999, #0
分支限界25：更新最小花费Z0:11674, #24
分支限界25：更新最小花费Z0:10312, #291998
先列后行25：循环：#291998次，耗时1093717(ms)
先列后行25：内存：Total：87818240，Free：47917832，Used：39899264(B)
先列后行25：路线：0 - 3 - 4 - 5 - 23 - 24 - 22 - 16 - 17 - 13 - 18 - 21 - 20 - 19 - 14 - 15 - 12 - 1 - 10 - 11 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:10312
最优结果25：
先列后行25：费用: 北京-263-石家庄-171-太原-341-呼和浩特-535-银川-346-兰州-507-西安-437-郑州-459-武汉-270-南昌-291-长沙-762-南宁-373-海口-455-广州-697-福州-252-台北-596-杭州-160-上海-269-南京-141-合肥-537-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：10312
----------------------------------------------
贪心法＋31：选择基地为城市v0时，耗费为19614
贪心法＋31：选择基地为城市v3时，耗费为18773
贪心法＋31：选择基地为城市v5时，耗费为18620
贪心法＋31：选择基地为城市v6时，耗费为18209
贪心法＋31：选择基地为城市v7时，耗费为18074
贪心法＋31：选择基地为城市v8时，耗费为17902
贪心法＋31：循环：#0次，耗时31(ms)
贪心法＋31：内存：Total：87818240，Free：87652112，Used：165000(B)
贪心法＋31：路线：8 - 7 - 6 - 2 - 0 - 3 - 4 - 5 - 23 - 24 - 25 - 27 - 28 - 29 - 21 - 20 - 19 - 18 - 13 - 17 - 11 - 10 - 12 - 1 - 14 - 15 - 16 - 9 - 22 - 30 - 26 - 8...最小费用:17902
最优结果31：路线：0 > 8 > 7 > 6 > 2 > 9 > 11 > 10 > 1 > 12 > 15 > 14 > 13 > 17 > 18 > 19 > 20 > 21 > 28 > 29 > 27 > 30 > 26 > 25 > 24 > 23 > 22 > 16 > 3 > 4 > 5 > 0...最小费用:15404
贪心法＋31：费用: 哈尔滨-232-长春-281-沈阳-605-天津-119-北京-263-石家庄-171-太原-341-呼和浩特-535-银川-346-兰州-192-西宁-691-成都-523-贵阳-434-昆明-619-南宁-373-海口-455-广州-563-长沙-291-南昌-270-武汉-319-合肥-141-南京-242-杭州-160-上海-606-福州-252-台北-1317-郑州-374-济南-780-西安-1758-拉萨-1592-乌鲁木齐-3057-哈尔滨 = 总费用：17902
----------------------------------------------
动态规划31：TSP18=116MB,TSP19=333MB,消耗内存太大,该算法无法求解
分支限界31：初始最小花费Z0:999999, #0
分支限界31：更新最小花费Z0:16169, #30
分支限界31：更新最小花费Z0:15404, #82364
先行后列31：循环：#82364次，耗时352701(ms)
先行后列31：内存：Total：87818240，Free：76444576，Used：11372528(B)
先行后列31：路线：0 - 8 - 7 - 6 - 2 - 9 - 11 - 10 - 1 - 12 - 15 - 14 - 13 - 17 - 18 - 19 - 20 - 21 - 28 - 29 - 27 - 30 - 26 - 25 - 24 - 23 - 22 - 16 - 3 - 4 - 5 - 0...最小费用:15404
最优结果31：路线：0 > 8 > 7 > 6 > 2 > 9 > 11 > 10 > 1 > 12 > 15 > 14 > 13 > 17 > 18 > 19 > 20 > 21 > 28 > 29 > 27 > 30 > 26 > 25 > 24 > 23 > 22 > 16 > 3 > 4 > 5 > 0...最小费用:15404
先行后列31：费用: 北京-1061-哈尔滨-232-长春-281-沈阳-605-天津-271-济南-537-合肥-141-南京-269-上海-160-杭州-596-台北-252-福州-441-南昌-270-武汉-299-长沙-563-广州-455-海口-373-南宁-449-贵阳-434-昆明-641-成都-1257-拉萨-1592-乌鲁木齐-1440-西宁-192-兰州-346-银川-521-西安-437-郑州-376-石家庄-171-太原-341-呼和浩特-401-北京 = 总费用：15404
----------------------------------------------
分支限界31：初始最小花费Z0:999999, #0
分支限界31：更新最小花费Z0:16121, #30
分支限界31：更新最小花费Z0:15404, #81915
先列后行31：循环：#81915次，耗时348713(ms)
先列后行31：内存：Total：87818240，Free：74556648，Used：13260456(B)
先列后行31：路线：0 - 5 - 4 - 3 - 16 - 22 - 23 - 24 - 25 - 26 - 30 - 27 - 29 - 28 - 21 - 20 - 19 - 18 - 17 - 13 - 14 - 15 - 12 - 1 - 10 - 11 - 9 - 2 - 6 - 7 - 8 - 0...最小费用:15404
最优结果31：路线：0 > 8 > 7 > 6 > 2 > 9 > 11 > 10 > 1 > 12 > 15 > 14 > 13 > 17 > 18 > 19 > 20 > 21 > 28 > 29 > 27 > 30 > 26 > 25 > 24 > 23 > 22 > 16 > 3 > 4 > 5 > 0...最小费用:15404
先列后行31：费用: 北京-401-呼和浩特-341-太原-171-石家庄-376-郑州-437-西安-521-银川-346-兰州-192-西宁-1440-乌鲁木齐-1592-拉萨-1257-成都-641-昆明-434-贵阳-449-南宁-373-海口-455-广州-563-长沙-299-武汉-270-南昌-441-福州-252-台北-596-杭州-160-上海-269-南京-141-合肥-537-济南-271-天津-605-沈阳-281-长春-232-哈尔滨-1061-北京 = 总费用：15404
----------------------------------------------
-----END-----

评论

1 楼 pipal 2010-04-21  

记得学《离散数学》“图”的时候，有个叫做“迪克斯特拉算法”求最短路径的，应该可以解决这个问题吧。