带有度约束的最小耗费生成树的分支限界算法

来源 :计算机应用与软件 | 被引量 : 0次 | 上传用户:aya05901
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
最小耗费生成树算法已很成熟,如Dijkstras 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。
其他文献
本文讨论了多类别模式识别中快速筛选与精确分类的问题,提出了分层多级决策树模型,将整个决策过程分为模糊分类层和最佳决策树分类层。对前者构造了以类别中心为基础的加权择近原则,实现快速筛选;对后者构造了综合最佳决策树,实现精确分类。此决策树模型具有较高的筛选率和分类精度。对六类乳腺癌细胞进行识别,它对正常细胞的筛选率达70%以上,而假阴性率为0%,整个系统的重置正确识别率为100%,实际测试样本测试正确
寄存器分配可看作为一个图着色问题,图中每个结点代表了一个硬件寄存器的候选者,如果两个候选者使用寄存器发生冲突则两者之间有一条边,即它们同时在某些点活跃。本文提出了在VAX-11/VMS 机器上实现MODULA-2编译中使用的基于优先级着色的寄存器分配算法。使得图着色寄存器分配中处理Spilling 问题的时间从指数级变为线性级。
在某些特定情形下,用一组非线性代数方程表示压差-流量特性的由复杂管路组成的实际系统可用一电路网络抽象表示,并且运用基于电路网络理论的网络等效法求解体现压差-流量关系的非线性代数方程。
当前,自助服务已成为了高校图书馆服务创新的主要趋势之一。文章论述了高校图书馆自助服务的产生背景和概念内涵,以及深入探讨了服务方式的技术应用创新、服务对象的需求满足
利用有限元分析软件ANSYS对预制倒T形板进行了非线性分析,对一些问题如不同参数取值对分析结果的影响进行了讨论,给出了相应的意见和建议;然后利用最优参数组对不同型号预制倒T
图G的顶点W-划分是指G的一个顶点划分{V1,V2,…,Vs},其中G[Vi]有生成子图轮W|Vi|(1≤i≤s)结合图的顶点W--划分以及顶点度条件,得到了一类新的上可嵌入图类,推广了已有相关结果.
文章详细介绍了用ObjectARX进行AutoCAD二次开发在通信管线设计中的应用。详细描述了系统的整体设计流程以及每个功能模块的设计过程。开创了通信管线设计的新设计模式,有效的
校企合作协同培养学生已成为一种新型的教育模式得到社会认可.但这种模式在研究生教育阶段的应用还有待深入研究,文章在分析校企合作协同培养研究生机制的理论基础上,结合广
本文所叙述的追加法,很好地解决了软件开发中软件的汉化和修改时常遇到的追加段存放位置和追加段的调试问题。通过多次实践证明,这是一种简单而行之有效的软件开发方法。
对把图象变换为四叉树以及把四叉树还原为图象的标准方法作了改进。改进法是以图象中的均匀性区域为基础,通过定义几阶非终结点来扩展均匀性定义的范围,从而减少四叉树的结点数目。结果证明,用该方法得到的四叉树,其结点数目比标准法的要少4~13%。