#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE (1)
#define FALSE (0)
#define MAX_CITIES (31)
#define INFINITY (99999)
#define I INFINITY
//typedef int bool;
/* 定义边结构 */
typedef struct _EDGE {
int head;
int tail;
} EDGE;
/* 定义路径结构 */
typedef struct _PATH {
EDGE edge[MAX_CITIES];
int edgesNumber;
} PATH;
/* 定义花费矩阵结构 */
typedef struct _MATRIX {
int distance[MAX_CITIES][MAX_CITIES];
int citiesNumber;
} MATRIX;
/* 定义树结点 */
typedef struct _NODE {
int bound; /* 相应于本结点的花费下界 */
MATRIX matrix; /* 当前花费矩阵 */
PATH path; /* 已经选定的边 */
struct _NODE* left; /* 左枝 */
struct _NODE* right; /* 右枝 */
} NODE;
int Simplify(MATRIX*);
EDGE SelectBestEdge(MATRIX);
MATRIX LeftNode(MATRIX, EDGE);
MATRIX RightNode(MATRIX, EDGE, PATH);
PATH AddEdge(EDGE, PATH);
PATH BABA(NODE);
PATH MendPath(PATH, MATRIX);
int MatrixSize(MATRIX, PATH);
void ShowMatrix(MATRIX);
void ShowPath(PATH, MATRIX);
int main()
{
PATH path;
NODE root = {
0, /* 花费下界 */
{I ,1087.894857 ,104.9674967 ,1588.631896 ,1304.751199 ,1085.291248 ,803.9650871 ,544.0153205 ,279.2938629 ,492.2942803 ,360.3293112 ,646.3021577 ,1048.494427 ,1474.965871 ,1134.987357 ,1686.188514 ,3246.24837 ,898.3632278 ,871.825509 ,1128.007424 ,1322.381241 ,1240.304925 ,1045.258361 ,1700.457506 ,1833.797448 ,1534.363244 ,1863.225045 ,2274.9929 ,2101.53971 ,2239.842484 ,3024.866656,
1087.894857 ,I ,998.9351726 ,1676.72178 ,1690.721318 ,1443.567738 ,1172.133837 ,1508.447435 ,1092.671515 ,1222.81651 ,753.118842 ,950.7310302 ,1457.055483 ,2053.449616 ,1858.179667 ,2282.904956 ,4028.328569 ,458.7888669 ,325.2545604 ,173.667367 ,981.4970125 ,709.7827606 ,791.7897895 ,1918.540145 ,1737.788993 ,612.6480277 ,1274.632933 ,1748.781161 ,1747.297778 ,2209.177643 ,3362.284153,
104.9674967 ,998.9351726 ,I ,1620.468362 ,1253.488526 ,1024.864227 ,732.3895492 ,645.0215569 ,336.3787529 ,558.3351075 ,301.5391438 ,656.6336732 ,1099.706195 ,1552.336949 ,1221.432389 ,1767.239171 ,3344.999766 ,842.7612869 ,801.1099744 ,1048.958896 ,1303.93878 ,1200.537584 ,1021.871367 ,1746.989857 ,1852.147065 ,1468.063581 ,1834.285997 ,2257.498663 ,2098.889413 ,2269.842047 ,3092.516934,
1588.631896 ,1676.72178 ,1620.468362 ,I ,2876.136796 ,2634.31036 ,2323.659578 ,1368.721003 ,1312.159349 ,1131.634713 ,1424.61832 ,976.2365352 ,592.0643301 ,809.7761585 ,987.4168494 ,953.9304109 ,2639.665739 ,1231.837091 ,1387.259718 ,1533.65211 ,754.7781456 ,1027.845628 ,884.9481917 ,279.0111516 ,330.3842941 ,1475.618048 ,1029.091503 ,1120.692888 ,788.7210033 ,647.9367701 ,1692.144796,
1304.751199 ,1690.721318 ,1253.488526 ,2876.136796 ,I ,253.8545106 ,563.170337 ,1750.073921 ,1583.087481 ,1797.804542 ,1454.6207 ,1893.684507 ,2355.548493 ,2760.432296 ,2394.158748 ,2958.105206 ,4347.452937 ,1861.568549 ,1734.906331 ,1843.06132 ,2444.126468 ,2253.169296 ,2161.503215 ,3009.365601 ,3089.091134 ,2304.479105 ,2900.905183 ,3369.182354 ,3276.226258 ,3527.818112 ,4336.816656,
1085.291248 ,1443.567738 ,1024.864227 ,2634.31036 ,253.8545106 ,I ,312.1630625 ,1561.373641 ,1359.195771 ,1577.883989 ,1208.873108 ,1652.150404 ,2127.186735 ,2555.527045 ,2198.310636 ,2759.483208 ,4205.846348 ,1606.787808 ,1480.408561 ,1592.876951 ,2189.605456 ,1997.848511 ,1908.086917 ,2775.645819 ,2839.968753 ,2055.69388 ,2644.745666 ,3111.836567 ,3020.270724 ,3281.604167 ,4120.868809,
803.9650871 ,1172.133837 ,732.3895492 ,2323.659578 ,563.170337 ,312.1630625 ,I ,1312.294072 ,1068.932658 ,1290.551672 ,897.7465122 ,1343.156977 ,1828.733881 ,2280.04617 ,1934.550148 ,2490.131842 ,3995.532325 ,1299.924174 ,1178.905522 ,1310.939562 ,1877.266864 ,1691.466723 ,1595.442841 ,2471.135422 ,2524.959938 ,1776.710952 ,2339.714552 ,2802.701847 ,2705.533995 ,2967.191268 ,3831.034426,
544.0153205 ,1508.447435 ,645.0215569 ,1368.721003 ,1750.073921 ,1561.373641 ,1312.294072 ,I ,415.1452242 ,343.7673515 ,765.339425 ,702.1859684 ,776.0961225 ,1017.722525 ,644.0049958 ,1205.543424 ,2702.742924 ,1183.212254 ,1223.970409 ,1498.466089 ,1386.793049 ,1416.671606 ,1165.541933 ,1395.276909 ,1670.643433 ,1821.537939 ,1944.622055 ,2280.343707 ,2035.78613 ,1998.780336 ,2585.866128,
279.2938629 ,1092.671515 ,336.3787529 ,1312.159349 ,1583.087481 ,1359.195771 ,1068.932658 ,415.1452242 ,I ,222.733955 ,353.1352649 ,405.0229195 ,769.233761 ,1219.955374 ,902.9836077 ,1438.110213 ,3056.116877 ,792.4718122 ,815.7806551 ,1089.069925 ,1110.966725 ,1077.314498 ,850.5433823 ,1420.206472 ,1565.979955 ,1438.735311 ,1665.789881 ,2052.793753 ,1856.749531 ,1962.663379 ,2754.170995,
492.2942803 ,1222.81651 ,558.3351075 ,1131.634713 ,1797.804542 ,1577.883989 ,1290.551672 ,343.7673515 ,222.733955 ,I ,533.3812018 ,358.6838837 ,564.0313201 ,997.8229538 ,691.2315601 ,1217.378399 ,2857.659701 ,858.2205986 ,918.5037004 ,1190.656551 ,1048.761712 ,1073.005179 ,821.7248351 ,1216.563697 ,1406.465648 ,1486.043994 ,1607.953373 ,1960.3259 ,1735.008985 ,1779.350945 ,2531.846832,
360.3293112 ,753.118842 ,301.5391438 ,1424.61832 ,1454.6207 ,1208.873108 ,897.7465122 ,765.339425 ,353.1352649 ,533.3812018 ,I ,450.628925 ,972.5198687 ,1502.516323 ,1222.132483 ,1728.809711 ,3392.76173 ,541.804445 ,512.6447804 ,774.2982864 ,1021.675756 ,901.2810211 ,736.7845893 ,1587.504995 ,1623.01355 ,1173.894869 ,1539.904444 ,1971.716177 ,1831.6198 ,2061.403503 ,2985.758267,
646.3021577 ,950.7310302 ,656.6336732 ,976.2365352 ,1893.684507 ,1652.150404 ,1343.156977 ,702.1859684 ,405.0229195 ,358.6838837 ,450.628925 ,I ,543.7126794 ,1117.427471 ,907.1912779 ,1347.575995 ,3070.982474 ,532.780693 ,627.5959771 ,885.011373 ,709.7413852 ,714.1641567 ,465.3110722 ,1137.057205 ,1193.602957 ,1135.767258 ,1267.780977 ,1647.419571 ,1455.740821 ,1617.423141 ,2546.556084,
1048.494427 ,1457.055483 ,1099.706195 ,592.0643301 ,2355.548493 ,2127.186735 ,1828.733881 ,776.0961225 ,769.233761 ,564.0313201 ,972.5198687 ,543.7126794 ,I ,598.7496068 ,521.3583114 ,826.0800676 ,2577.475302 ,1004.9041 ,1132.725238 ,1360.155114 ,835.9122064 ,1005.92527 ,758.4266453 ,651.9548372 ,899.8128766 ,1488.957169 ,1334.831959 ,1582.955526 ,1299.106776 ,1226.198659 ,2010.94568,
1474.965871 ,2053.449616 ,1552.336949 ,809.7761585 ,2760.432296 ,2555.527045 ,2280.04617 ,1017.722525 ,1219.955374 ,997.8229538 ,1502.516323 ,1117.427471 ,598.7496068 ,I ,382.5459186 ,230.1165805 ,1977.649631 ,1603.587519 ,1727.963058 ,1959.825374 ,1377.237589 ,1584.873869 ,1348.605614 ,630.1292334 ,1124.642929 ,2071.116789 ,1798.946526 ,1931.85522 ,1595.677221 ,1232.188198 ,1563.670795,
1134.987357 ,1858.179667 ,1221.432389 ,987.4168494 ,2394.158748 ,2198.310636 ,1934.550148 ,644.0049958 ,902.9836077 ,691.2315601 ,1222.132483 ,907.1912779 ,521.3583114 ,382.5459186 ,I ,561.4212972 ,2172.447428 ,1434.465527 ,1535.558845 ,1791.491205 ,1356.35063 ,1507.604276 ,1249.518151 ,899.5213969 ,1317.772406 ,1983.911834 ,1853.856458 ,2071.338945 ,1762.549338 ,1526.121866 ,1942.09276,
1686.188514 ,2282.904956 ,1767.239171 ,953.9304109 ,2958.105206 ,2759.483208 ,2490.131842 ,1205.543424 ,1438.110213 ,1217.378399 ,1728.809711 ,1347.575995 ,826.0800676 ,230.1165805 ,561.4212972 ,I ,1755.938047 ,1831.733247 ,1957.468091 ,2187.354605 ,1581.153032 ,1800.01176 ,1569.290424 ,726.0870712 ,1245.130739 ,2286.017392 ,1973.27721 ,2065.823937 ,1719.564617 ,1269.723105 ,1389.092772,
3246.24837 ,4028.328569 ,3344.999766 ,2639.665739 ,4347.452937 ,4205.846348 ,3995.532325 ,2702.742924 ,3056.116877 ,2857.659701 ,3392.76173 ,3070.982474 ,2577.475302 ,1977.649631 ,2172.447428 ,1755.938047 ,I ,3584.035617 ,3700.323379 ,3945.370652 ,3338.640621 ,3567.356765 ,3334.011692 ,2364.624626 ,2861.092102 ,4058.668905 ,3680.464333 ,3665.813976 ,3308.054202 ,2659.027751 ,1620.202762,
898.3632278 ,458.7888669 ,842.7612869 ,1231.837091 ,1861.568549 ,1606.787808 ,1299.924174 ,1183.212254 ,792.4718122 ,858.
BNB.rar_bnb_动态规划_规划
版权申诉
11 浏览量
2022-09-24
02:08:17
上传
评论
收藏 8KB RAR 举报
![avatar](https://profile-avatar.csdnimg.cn/5df8bff20ad645abb899a1a8333a748d_weixin_42651281.jpg!1)
小波思基
- 粉丝: 74
- 资源: 1万+