/ 分支限界法最小权顶点覆盖问题
分支限界法最小权顶点覆盖问题
分支限界法最小权顶点覆盖问题
★问题描述：给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。
如果U∈V,且对任意(u,v)∈E有u∈U或v∈U,就称U为图G的一个顶点条覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。
★算法设计：对于结定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖。
★数据输入：由文件input.txt给出输入数据。
第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,.....,n.第2行有n个正整数表示n个顶点的权.接上去的m行中,每行有2个正整数u,v,表示图G的一条边(u,v)。
★结果输出：将计算出的最小权顶点覆盖的顶点权之和以及最优输出到文件output.txt.文件第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi,1≤i≤n,xi=0表示顶点i不在最小权顶点覆盖中。
本软件ID:3213303
★问题描述：给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。
如果U∈V,且对任意(u,v)∈E有u∈U或v∈U,就称U为图G的一个顶点条覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。
★算法设计：对于结定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖。
★数据输入：由文件input.txt给出输入数据。
第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,.....,n.第2行有n个正整数表示n个顶点的权.接上去的m行中,每行有2个正整数u,v,表示图G的一条边(u,v)。
★结果输出：将计算出的最小权顶点覆盖的顶点权之和以及最优输出到文件output.txt.文件第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi,1≤i≤n,xi=0表示顶点i不在最小权顶点覆盖中。
本软件ID:3213303
文件下载
资源详情
[{"title":"（11个子文件363KB）分支限界法最小权顶点覆盖问题","children":[{"title":"五、分支限界法","children":[{"title":"6-2.opt <span style='color:#111;'>47.50KB</span>","children":null,"spread":false},{"title":"6-2.ncb <span style='color:#111;'>41.00KB</span>","children":null,"spread":false},{"title":"Debug","children":[{"title":"vc60.pdb <span style='color:#111;'>116.00KB</span>","children":null,"spread":false},{"title":"6-2.exe <span style='color:#111;'>536.06KB</span>","children":null,"spread":false},{"title":"6-2.obj <span style='color:#111;'>251.27KB</span>","children":null,"spread":false},{"title":"6-2.pdb <span style='color:#111;'>1.05MB</span>","children":null,"spread":false}],"spread":true},{"title":"MinHeap.h <span style='color:#111;'>1.58KB</span>","children":null,"spread":false},{"title":"6-2.dsp <span style='color:#111;'>3.29KB</span>","children":null,"spread":false},{"title":"6-2.cpp <span style='color:#111;'>3.63KB</span>","children":null,"spread":false},{"title":"6-2.dsw <span style='color:#111;'>514B</span>","children":null,"spread":false},{"title":"6-2.plg <span style='color:#111;'>733B</span>","children":null,"spread":false}],"spread":true}],"spread":true}]
评论信息
-
-
-
yehuiliusu:应付学校的昨夜完全够了不过程序还有点小问题运行出来的结果不是最优的2015-09-09 -
leedehua_:同可用，不过和其他人的差不多2015-08-21
-
macchiatoo:还可以,但是结果跟书上的答案有出入啊2014-06-04
-
linyangfan94:很好，好好研究研究2014-05-30
-
soareyou:还不错，及时的资料2013-10-23
其他资源
- osm2pgsql最新windows版
- LSM和RLS算法实现系统辨识和逆辨识
- 运输imimable-js：Immutable.js的运输序列化-源码
- 物流管理系统论文+项目+中期报告等
- TMS8.5.1ForXe10.3
- pcm音频测试文件
- javaweb使用监听器实现按时周期性实施责任demo
- RTSPPUSHtcpudph264easydarwin
- 【Spring项目源码】天气预告系统.zip
- vue-2.5.17js源码,库文件,例子等
- 软件成果测试进程详解与案例阐发（第二版）pdf-残缺书签目录-软件测试文档类资源
- 平衡小车之家以及自己的有关于平衡小车的资料
- 基于空心光纤技术产生高能量周期量级脉冲压缩
- ASK调制解调的完善程序
- 模拟泊松过程R语言
- 温室大棚控制系统设计
- FileZillaServerbeta0.9.43
- 基于android的校园助手代码
- 先生信息管理（mfc）word文档
- 计算机组成原理（白中英第五版）完好版课件，从第一章到第八章
免责申明
【好快吧下载】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【好快吧下载】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【好快吧下载】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，8686821#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，8686821#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明