求解运筹学最小支撑树模型的一种新算法

摘要：

为了简化对运筹学中最小支撑树模型编写简单计算机程序来实现求解,设计了一种新的简便算法----“节点列表判定法”.该算法是用节点来表述网络图的边,并从节点列表中找到了构成圈的特征结构,以此作为判定条件来确定网络图是否有圈存在.在最小支撑树模型的求解过程中,选择网络图中权数最小的边为支撑树的边.每选择一条边就判定一次,若判定有圈存在则放弃最后选择的边,反复选择边并判断,直到所有已选择的边都不构成圈且总边数等于点数-1,那么新确定的支撑树就是一个最小支撑树.这种新的算法已经Excel-BVA编制求解程序验证了其正确性、实用性和快捷性.

关键词：最小支撑树、节点列表判定法、Excel-VBA运筹学

所属期刊栏目：13

分类号：O224(运筹学)

在线出版日期：2013-03-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：263-268,275