文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 旅行售货员问题
侵权投诉

旅行售货员问题

对售货员问题的算法进行了详细的解说

旅行售货员问题

【问题描述】某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。

路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。

旅行售货员问题的解空间可以组织成一棵排列树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。

回溯法求解:

【算法描述】

int bestc; //当前最优值

int x[num+1]; //当前解

int bestx[num+1];

int cc; //当前费用

int tsp(int m)

{ for(int i=0;i<=m;i++) x[i]=i; bestc=max_value; cc=0; //搜索x[2:n]的全排列 backtrack(2,m); return bestc;

}

void backtrack(int i,int n)

{ if(i==n) { if((a[x[n-1]][x[n]])<max_value&&a[x[n]][1]<max_value&&(bestc==max_value||cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc))

{

} else { for(int j=i;j<=n;j++) //是否可进入x[j]子树? if(a[x[i-1]][x[i]]<max_value&&(bestc==max_value||cc+a[x[i-1]][x[j]]<bestc)) { //搜索子树 swap(x,i,j); } for(int j=1;j<=n;j++) bestx[j]=x[j]; bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];

第1页

你可能喜欢

  • 分支限界法
  • 算法报告
  • 回溯算法
  • 遗传算法解决TSP问题
  • 网络编程基础
  • 旅行商问题算法
  • 贪心算法
  • 动态规划

热门文档

相关文档

  • 动态规划:旅行售货员问题

    本次课程设计运用动态规划解决旅行售货员问题,动态规划的基本思想是: 把求解的问题分成许多若干阶段或许多子问题,然后按顺序求解各子问题。前一 子问题的解, 为后...

  • 旅行售货员问题初探索

    旅行售货员问题初探索数本 062 班 赵佳佳 06990231@zjnu.net 摘要 旅行售货员问题(Travelling Salesman Problem,以下简称 TSP)是图论中一个 著名的问题,这个问题有...

  • 旅行售货员问题

    旅行售货员问题 传统的旅行售货员问题可以概述如下:设有 n 个城市, 以 V1 ,V2 ,?Vn 表示之,用 dij 表示城市 Vi 到城市 Vj 之间的 距离,一个推销员从某...

  • 旅行售货员问题

    旅行售货员问题要在图 G 中找出费用最小的 周游路线。设有 p 个城市,假设每两个城市之间都有直通通道,两个城市之间 的路程已知,一个售货员要到每个城市推销...

  • 旅行售货员问题

    旅行售货员问题_理学_高等教育_教育专区。关于算法的课程设计问题的重 一 问题的重述 售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选 ...

  • 建模 旅行售货员问题

    建模 旅行售货员问题_数学_自然科学_专业资料。旅行售货员(TSP),Hamilton 回路的 lingo 程序 方法一 model: sets: city / 1..6/: u;! 定义 6 个城市; ...

  • 旅行售货员问题

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 旅行售货员问题 隐藏>> 旅行售货员问题 一...

  • 旅行售货员问题的图论近似算法

    Computer Engineering and Applications 计算机工程与应用 2009 ,45 (32 ) 51 旅行售货员问题的图论近似算法许金星, 吴素萍 XU Jin-xing, WU Su-ping 宁夏大学 ...

  • 欧式旅行售货员问题

    1.问题描述 欧式旅行售货员问题是对给定的平面上 n 个点确定一条连接这 n 个点的长度最短的哈密 顿回路。 由于欧氏距离满足三角不等式, 所以欧式旅行售货员...

  • (原创精品)旅行售货员问题(回溯法)

    (原创精品)旅行售货员问题(回溯法)_工学_高等教育_教育专区。(原创精品)旅行售货员问题(回溯法)今日推荐 157份文档 2015国家公务员考试备战攻略...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email