下载 >  开发技术 >  Delphi > 旅行商问题的分支限界法
4

旅行商问题的分支限界法

Delphi程序。算法中的分支限界法解旅行商问题,只能尽快解出一个最优解。
2009-06-10 上传大小:187KB
分享
收藏 (3) 举报

评论 共15条

u014660531 还可以吧,就是没有源代码,不知用什么算法实现的
2015-09-07
回复
baidu_15169983 谢谢 很有参考价值
2014-10-25
回复
sandybob 很好 很经典,对于编程的人很有帮助
2014-06-19
回复
lijianming1234567890 资源没有源代码,没法分析!
2013-12-17
回复
kj8686745 怎么说呢,如果有源程序,那就更好了。。。
2013-12-04
回复
sqhust 说实话这问题挺难的,有多种解法
2013-11-11
回复
fjp824 看不到代码,下和没下一样啊
2013-06-22
回复
lkt_lantian 还可以吧,有点帮助
2013-03-27
回复
lifeilonglovejcy 没有源代码啊
2013-03-05
回复
j591908439 就是没源代码
2012-12-20
回复
动态规划法,回溯法,分支限界法求解TSP旅行商问题

本报告仅供参考,不足之处请指正,版权由博主所有,未经同意禁止应用于非法用途,请下载者自觉。

立即下载
旅行商问题 C语言解法

C语言解决旅行商问题(货郎担问题),包括程序文件、源代码、程序测试图。

立即下载
分支限界法旅行商问题

网上很多分支限界法求旅行商问题很复杂而且正确的没几个,这是我下决心花两天时间完成的,很辛苦的

立即下载
分支限界法 装载问题

#include <queue> #include <iostream> #include <algorithm> #include<fstream> using namespace std; ifstream infile; ofstream outfile; class Node { friend int func(int*, int, int, int*); public: int ID; double weight;//物品的重量 }; bool comp1(Node a, Node b) //定义比较规则 { return a.weight > b.weight; } class Load; class bbnode; class Current { friend Load; friend struct Comp2; private: int upweight;//重量上界 int weight;//结点相应的重量 int level;//活结点在子集树中所处的层次 bbnode* ptr;//指向活结点在子集树中相应结点的指针 }; struct Comp2 { bool operator () (Current *x, Current *y) { return x->upweight<y->upweight; } }; class Load { friend int func(int*, int, int, int*); public: int Max0(); private: priority_queue<Current*, vector<Current*>, Comp2>H;//利用优先队列(最大堆)储存 int limit(int i); void AddLiveNode(int up, int cw, bool ch, int level); bbnode *P;//指向扩展结点的指针 int c;//背包的容量 int n;//物品的数目 int *w;//重量数组 int cw;//当前装载量 int *bestx;//最优解方案数组 }; class bbnode { friend Load; friend int func( int*, int, int, int*); bbnode* parent; bool lchild; }; //结点中有双亲指针以及左儿子标志 int Load::limit(int i) //计算结点所相应重量的上界 { int left,a; left= c - cw;//剩余容量 a = cw; //b是重量上界,初始值为已经得到的重量 while (i <= n && w[i] <= left) { left -= w[i]; a += w[i]; i++; } return a; } void Load::AddLiveNode(int up, int cw, bool ch, int level) //将一个新的活结点插入到子集树和优先队列中 { bbnode *b = new bbnode; b->parent = P; b->lchild = ch; Current* N = new Current; N->upweight = up; N->weight = cw; N->level = level; N->ptr = b; H.push(N); } int Load::Max0() { int i = 1; P = 0; cw = 0; int bestw = 0; int up = limit(1); while (i != n + 1) { int wt = cw + w[i]; //检查当前扩展结点的左儿子结点 if (wt <= c)//左儿子结点是可行结点 { if (wt > bestw) bestw =wt; AddLiveNode(up,wt, true, i + 1); } up = limit(i + 1); //检查当前扩展结点的右儿子结点 if (up >= bestw)//如果右儿子可行 { AddLiveNode(up,cw, false, i + 1); } Current* N = H.top(); //取队头元素 H.pop(); P = N->ptr; cw = N->weight; up = N->upweight; i = N->level; } bestx = new int[n + 1]; for (int j = n; j > 0; --j) { bestx[j] = P->lchild; P = P->parent; } return cw; } int func(int *w, int c, int n, int *bestx) //调用Max0函数对子集树的优先队列式进行分支限界搜索 { int W = 0; //初始化装载的总质量为0 Node* Q = new Node[n]; for (int i = 0; i < n; ++i) { Q[i].ID = i + 1; Q[i].weight = w[i+1]; W += w[i+1]; } if (W <= c)//如果足够装,全部装入 return W; sort(Q, Q + n, comp1); //首先,将各物品按照重量从大到小进行排序; Load K; K.w = new int[n + 1]; for (int j = 0; j < n; j++) K.w[j + 1] = w[Q[j].ID]; K.cw = 0; K.c = c; K.n = n; int bestp = K.Max0(); for (int k = 0; k < n; k++) { bestx[Q[k].ID] = K.bestx[k + 1]; } delete []Q; delete []K.w; delete []K.bestx; return bestp; } int main() { int*w,*Final; int c,n,i,best; infile.open("input.txt",ios::in); if(!infile) { cerr<<"open error"<<endl; exit(1); } infile>>c; infile>>n; w=new int[n+1]; for(i=1;i<=n;i++) infile>>w[i]; infile.close(); Final = new int[n+1]; best = func( w, c, n, Final); outfile.open("output.txt",ios::out); if(!outfile) { cerr<<"open error"<<endl; exit(1); } outfile << best << endl; for (int i = 1; i <= n; ++i) { outfile<<Final[i]<<" "; } outfile.close(); return 0; }

立即下载
分支限界法解决旅行商问题

这是一个np完全问题,时间复杂度会随着n的增大而爆炸增长。目前,还没有完全解决

立即下载
旅行商问题,TSP问题,C#源码

c#进行了可视化编程,采用对话框的形式,能够随机生成测试数据和生成数据规模,对测试结果进行图示,显示函数曲线,并能够保存测试数据!!

立即下载
算法设计中关于优先队列式分支限界法解装载问题的代码

分支限界法中的优先队列式分支限界法解装载问题

立即下载
旅行商问题(TSP)三种解决算法 基于C++的编程

旅行商问题是一个经典的问题,此代码用三种方法(枚举法,回溯法,贪心法),并可以对这三种方法进行比较

立即下载
分支限界法求解旅行商问题

旅行商问题,即TSP问题(Travelling Salesman Problem)是指对给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行距离最短。

立即下载
厦门大学算法课件

厦门大学优秀课件,关于01背包问题的分支限界法改进,还有装载问题,旅行商问题的分支限界算法

立即下载
分支限界法分支限界法分支限界法

分支限界法分支限界法分支限界法分支限界法分支限界法分支限界法分支限界法

立即下载
八数码问题 队列式分支限界法

随机给定一个3×3的矩阵,其元素为8个不同的数码,起始状态为S0,目标状态为Sg,要求用两种或以上的方法设计优先队列式分支限界法,寻找从初始状态变换到目标状态的最优解,说明不同的优先选择策略变换到最终状态用了多少步,并对获得的结果做出比较分析。最终状态均如Sg表示。

立即下载
n皇后问题(队列分支限界法

N皇后问题解法,采用队列分支限界算法。c++编程。

立即下载
分支限界法解决N皇后问题

使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。

立即下载
回溯法解决旅行商问题

采用回溯法解决旅行商问题,获得最短路径回路。

立即下载
遗传算法解决5种多旅行商问题MTSP(matlab实现)

遗传算法解决5种多旅行商问题(mtsp)的matlab程序 分别为以下5中情况: 1.从不同起点出发回到起点(固定旅行商数量) 2.从不同起点出发回到起点(旅行商数量根据计算可变) 3.从同一起点出发回到起点 4.从同一起点出发不会到起点 5.从同一起点出发回到同一终点(与起点不同)

立即下载
旅行商问题(java语言描述)

旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题旅行商问题

立即下载
matlab解决旅行商问题

用MATLAB语言编写tsp问题程序并仿真求解遍历34座城市最短路径。 1模拟退火首先从某个初始候选解开始,当温度大于0时执行循环。 2.在循环中通过随机扰动产生一个新的解,然后求得新解和原解之间的能量差,如果差小于0,则采用新解作为当前解。 3.如果差大于0,则采用一个当前温度与能量差成比例的概率来选择是否接受新解。温度越低,接受的概率越小,差值越大,同样接受概率越小。是否接受的概率用此公式计算:p=exp(-ΔE/T)。这里ΔE为新解与原解的差,T为当前的温度。由于温度随迭代次数逐渐降低,因此获得一个较差的解的概率较小。

立即下载
旅行商问题的Matlab程序

多旅行商问题的Matlab程序,数学建模竞赛时可能会用到

立即下载
分支限界法求01背包c语言

分支限界法求01背包问题的解.rar c语言 已调通

立即下载
关闭
img

spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
点击完成任务获取下载码
输入下载码
为了良好体验,不建议使用迅雷下载
img

旅行商问题的分支限界法

会员到期时间: 剩余下载个数: 剩余C币: 剩余积分:0
为了良好体验,不建议使用迅雷下载
VIP下载
您今日下载次数已达上限(为了良好下载体验及使用,每位用户24小时之内最多可下载20个资源)

积分不足!

资源所需积分/C币 当前拥有积分
您可以选择
开通VIP
4000万
程序员的必选
600万
绿色安全资源
现在开通
立省522元
或者
购买C币兑换积分 C币抽奖
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
为了良好体验,不建议使用迅雷下载
确认下载
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
为了良好体验,不建议使用迅雷下载
VIP和C币套餐优惠
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
您的积分不足,将扣除 10 C币
为了良好体验,不建议使用迅雷下载
确认下载
下载
您还未下载过该资源
无法举报自己的资源

兑换成功

你当前的下载分为234开始下载资源
你还不是VIP会员
开通VIP会员权限,免积分下载
立即开通

你下载资源过于频繁,请输入验证码

您因违反CSDN下载频道规则而被锁定帐户,如有疑问,请联络:webmaster@csdn.net!

举报

若举报审核通过,可返还被扣除的积分

  • 举报人:
  • 被举报人:
  • *类型:
    • *投诉人姓名:
    • *投诉人联系方式:
    • *版权证明:
  • *详细原因: