ImageVerifierCode 换一换
格式:DOCX , 页数:11 ,大小:17.28KB ,
资源ID:14022901      下载积分:3 金币
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.bingdoc.com/d-14022901.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录   QQ登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(用分支限界算法解决旅行商问题.docx)为本站会员(b****1)主动上传,冰点文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知冰点文库(发送邮件至service@bingdoc.com或直接QQ联系客服),我们立即给予删除!

用分支限界算法解决旅行商问题.docx

1、用分支限界算法解决旅行商问题/求解旅行商问题的分枝限界算法#include #include #include #define TRUE (1)#define FALSE (0)#define MAX_CITIES (10)#define INFINITY(999)#define I INFINITYtypedef int bool;/* 定义边结构 */typedef struct _EDGE int head; int tail; EDGE;/* 定义路径结构 */typedef struct _PATH EDGE edgeMAX_CITIES; intedgesNumber; PATH;

2、/* 定义花费矩阵结构 */typedef struct _MATRIX int distanceMAX_CITIESMAX_CITIES; int citiesNumber; MATRIX;/* 定义树结点 */typedef struct _NODE int bound; /* 相应于本结点的花费下界 */ MATRIX matrix; /* 当前花费矩阵 */ PATH path; /* 已经选定的边 */ struct _NODE* left; /* 左枝 */ struct _NODE* right; /* 右枝 */ NODE;int Simplify(MATRIX*);EDGE

3、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);main() PATH path; NODE root = 0, /* 花费下界 */ I, 1, 2, 7, 5, /

4、* 花费矩阵 */ 1, I, 4, 4, 3, 2, 4, I, 1, 2, 7, 4, 1, I, 3, 5, 3, 2, 3, I, 5, /* 城市数目 */ 0, 0, /* 经历过的路径 */ NULL, NULL /* 左枝与右枝 */ ; /* 归约,建立根结点 */ root.bound += Simplify(&root.matrix); /* 进入搜索循环 */ path = BABA(root); ShowPath(path, root.matrix);return 0;/* 算法主搜索函数,Branch-And-Bound Algorithm Search* root

5、 是当前的根结点,已归约,数据完善*/PATH BABA(NODE root) int i; static int minDist = INFINITY; static PATH minPath; EDGE selectedEdge; NODE *left, *right; puts(Current Root:n-); ShowMatrix(root.matrix); printf(Root Bound:%dn, root.bound); /* 如果当前矩阵大小为2,说明还有两条边没有选,而这两条边必定只能有一种组合, * 才能构成整体回路,所以事实上所有路线已经确定。 */ if (Matr

6、ixSize(root.matrix, root.path) = 2) if (root.bound bound = root.bound; /* 继承父结点的下界 */ left-matrix = LeftNode(root.matrix, selectedEdge); /* 删掉分枝边 */ left-path = root.path; /* 继承父结点的路径,没有增加新边 */ left-left = NULL; left-right = NULL; right-bound = root.bound; right-matrix = RightNode(root.matrix, selec

7、tedEdge, root.path);/* 删除行列和回路边 */ right-path = AddEdge(selectedEdge, root.path); /* 加入所选边 */ right-left = NULL; right-right = NULL; /* 归约左右分枝结点 */ left-bound += Simplify(&left-matrix); right-bound += Simplify(&right-matrix); /* 链接到根 */ root.left = left; root.right = right; /* 显示到监视器 */ puts(Right B

8、ranch:n-); ShowMatrix(right-matrix); puts(Left Branch:n-); ShowMatrix(left-matrix); /* 如果右结点下界小于当前最佳答案,继续分枝搜索 */ if (right-bound bound); printf(This branch is dead.n); /* 如果右结点下界小于当前最佳答案,继续分枝搜索 */ if (left-bound bound); printf(This branch is dead.n); printf(The best answer now is %dn, minDist); retu

9、rn (minPath);/* 修补路径 */PATH MendPath(PATH path, MATRIX c) int row, col; EDGE edge; int n = c.citiesNumber; for (row = 0; row n; row+) edge.head = row; for (col = 0; col citiesNumber; h = 0; /* 行归约 */ for (row = 0; row n; row+) /* 找出本行最小的元素 */ min_dist = INFINITY; for (col = 0; col distancerowcol dis

10、tancerowcol; /* 如果本行元素都是无穷,说明本行已经被删除 */ if (min_dist = INFINITY) continue; /* 本行每元素减去最小元素 */ for (col = 0; col distancerowcol != INFINITY) c-distancerowcol -= min_dist; /* 计算归约常数 */ h += min_dist; /* 列归约 */ for (col = 0; col n; col+) /* 找出本列最小的元素 */ min_dist = INFINITY; for (row = 0; row distancerow

11、col distancerowcol; /* 如果本列元素都是无穷,说明本列已经被删除 */ if (min_dist = INFINITY) continue; /* 本列元素减去最小元素 */ for (row = 0; row distancerowcol != INFINITY) c-distancerowcol -= min_dist; /* 计算归约常数 */ h += min_dist; return (h);/* 搜索所有花费为零的边中最合适的,使左枝下界更大 */EDGE SelectBestEdge(MATRIX c) int row, col; int n = c.cit

12、iesNumber; int maxD; EDGE best, edge; /* 所用函数声明 */ int D(MATRIX, EDGE); maxD = 0; for (row = 0; row n; row+) for (col = 0; col n; col+) edge.head = row; edge.tail = col; if (!c.distancerowcol & maxD D(c, edge) maxD = D(c, edge); best = edge; return (best);/* 计算如果选 edge 作为分枝边,左枝(不含 edge)下界的增量 */int D

13、(MATRIX c, EDGE edge) int row, col, dRow, dCol; int n = c.citiesNumber; dRow = INFINITY; for (col = 0; col n; col+) if (dRow c.distanceedge.headcol & col != edge.tail) dRow = c.distanceedge.headcol; dCol = INFINITY; for (row = 0; row n; row+) if (dCol c.distancerowedge.tail & row != edge.head) dCol

14、= c.distancerowedge.tail; return (dRow + dCol);/* 删掉所选分枝边 */MATRIX LeftNode(MATRIX c, EDGE edge) c.distanceedge.headedge.tail = INFINITY; return c;/* 删除行列和回路边后的矩阵 */MATRIX RightNode(MATRIX c, EDGE edge, PATH path) int row, col; int n = c.citiesNumber; EDGE loopEdge; /* 声明所需要的求回路边函数 */ EDGE LoopEdge(

15、PATH, EDGE); for (col = 0; col n; col+) c.distanceedge.headcol = INFINITY; for (row = 0; row n; row+) c.distancerowedge.tail = INFINITY; loopEdge = LoopEdge(path, edge); c.distanceloopEdge.headloopEdge.tail = INFINITY; return (c);/* 计算回路边的函数* 除了加入的新边, 当前结点路线集合中还可能包含一些已经选定的边, 这些边构成一条或* 几条路径, 为了不构成回路,

16、 必须使其中包含新边的路径头尾不能相连,本函数返回这个* 头尾相连的边,以便把这个回路边的长度设成无穷。*/EDGE LoopEdge(PATH path, EDGE edge) int i, j; EDGE loopEdge; /* 最小的回路边 */ loopEdge.head = edge.tail; loopEdge.tail = edge.head; /* 寻找回路边的头端点,即包含新边的路径的尾端点 */ for (i = 0; i path.edgesNumber; i+) for (j = 0; j path.edgesNumber; j+) if (loopEdge.head = path.edgej.head) /* 扩大回路边 */ loopEdge.head = path.edgej.tail; break; /* 寻找回路边的尾端点,即包含新边的路径的头端点 */ for (i = 0; i path.edgesNumber; i+) for (j = 0; j path.edgesNumber; j+) if (loopEdge.tail = path.edgej.tail) /* 扩大回路边 */ loopEdge.tail = path.edgej.head;

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2