分支限界法 最小权顶点覆盖问题
★问题描述：给定一个赋权无向图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不在最小权顶点覆盖中。
文件下载
资源详情
[{"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
-
其他资源
- socket编程实验报告
- 矩阵理论黄延祝
- Juniper SRX Junos 12.3
- STM32F103C8T6最小系统板PCB图AD项目
- 三次样条插值法，求信号包络线
- 数字摄影测量学（第二版） 压缩版 39M
- 各类报警声音wav文件
- AlexNet深度神经网络
- 图像处理DCRAW
- VASP 5.4.4
- 大学生创业计划书有关于校园自行车的原创稿
- IMM交互多模型算法
- 溶胶-凝胶法Er_2O_3薄膜的结构和光学特性
- 高分冲刺专业知识综合讲义.pdf
- java的JDBC使用Mybatis框架封装
- aix5.3安装jdk1.6
- 小说网站项目
- Iris_Running_Crane___December_2009
- haxm-windows_v6_0_6
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明