模糊最小生成树.doc

1. 概述 在通信网络系统的架设过程中，为了使网络架设的费用最低化，通常是根据需要架设通信网络的城市之间的距离和每公里的费用，采用经典的最小生成树算法求出城市网络图的最小生成树，据此进行架设即可。但是在实际情况中，考虑到地理环境的影响，不同的城市之间每公里的费用是模糊的、不确定的，因此无法采用确定的数值来表示，而要采用模糊集合理论中的模糊数来表示，此时所构造的最小生成树亦称为模糊最小生成树。本文基于以下一个实例，探讨了根据模糊集合理论的相关方法来构造模糊最小生成树的过程。 实例：某省的七个城市需要加高通信网络系统，为连接这七个城市，每两个城市之间的距离如表1所示。考虑地理环境的影响，综合考虑各城市之间的距离和每公里修建网络的费用，各城市之间修建网络每公里的费用可用与10000元之间的比较来估计（表2）。试问如何架设通信网络，使总费用最小？ 表1 各城市之间的距离（单位：公里） 表2 各城市之间架设网络每公里的费用与10000元之间的比较 2．相关准备知识调研 2.1 模糊集合相关理论 在科学研究中，存在着许多定义不很严格或者说具有模糊性的概念，客观事物的差异在中间过渡中也存在着不分明性，为处理分析这些模糊概念的数据，便产生了模糊集合论。 这里所谓的模糊性，主要是指客观事物的差异在中间过渡中的不分明性，如某一生态条件对某种害虫、某种作物的存活或适应性可以评价为有利、比较有利、不那么有利、 不利灾害性霜冻气候对农业产量的影响程度为较重、 严重、 很严重，等等。这些通常是本来就属于模糊的概念，为处理分析这些模糊概念的数据，便产生了模糊集合论。根据集合论的要求，一个对象对应于一个集合，要么属于，要么不属于，二者必居其一，且仅居其一。这样的集合论本身并无法处理具体的模糊概念。为处理这些模糊概念而进行的种种努力，催生了模糊理论，主要包括模糊集合理论、模糊逻辑、模糊推理和模糊控制等方面的内容。 早在20世纪20年代，著名的哲学家和数学家B.Russell就写出了有关”含糊性”的论文。他认为所有的自然语言均是模糊的，比如红的和老的等概念没有明确的内涵和外延，因而是不明确的和模糊的。可是，在特定的环境中，人们用这些概念来描述某个具体对象时却又能心领神会，很少引起误解和歧义美国加州大学的L.A.Zadeh教授在1965年发表了著名的论文。文中首次提出表达事物模糊性的重要概念隶属函数，从而突破了19世纪末笛卡尔的经典集合理论，模糊理论的基础。1966年，P.N.Marinos发表模糊逻辑的研究报告，1974年，L.A.Zadeh发表模糊推理的研究报告，从此，模糊理论成了一个热门的课题模糊数学的基础大致朝着两个方向发展，一个方向是形式化系统，即同普通数学的公理化一样，用逻辑语言和形式公理来描述模糊数学。年，美国宾夕法尼亚统计大学的Weidner通过分析对比模糊集与布尔值论域的相似性，利用一阶逻辑提出了模糊集论的形式公理化体系。另一个方向是范畴论描述，范畴最早是拓扑学中的概念。所谓范畴，是指一个由个体与个体之间关系所成的一种数学体系，例如群、代数等都可以看成是范畴。用范畴论研究模糊数学的目的是希望把模糊集论定义成某种特定的范畴。较早把用范畴论来研究模糊集论的是加利福尼亚大学计算机科学系的教授Goguen.Goguen把模糊集论的一些特点描述成范畴论公理，从而得出模糊集论的范畴。在Goguen提出的范畴中，模糊集不再是一定要用区间0,1]来描述隶属度，而可以用任意的格来描述。这就是后来被称为L型模糊集论的一种广义的模糊集论。 实践证明，模糊数学在农业中主要用于病虫测报、种植区划、品种选育等方面，在图像识别、天气预报、地质地震、交通运输、医疗诊断、信息控制、人工智能等诸多领域的应用也已初见成效。从该学科的发展趋势来看，它具有极其强大的生命力和渗透力。在侧重于应用的模糊数学分析中，经常应用到聚类分析、模式识别和综合评判等方法。A，要么xA，二者必居其一。 这一特征可用一个函数表示为： A(x)即为集合A的特征函数。将特征函数推广到模糊集，从在普通集合中只取0和1这两个值，推广到模糊集中为[0,1]区间。 定义1：设U为论域，若A为U上取值[0,1]的一个函数，则称A为模糊集。 如给5个同学的性格稳重程度打分，按百分制给分，再除以100，这样给定了一个从域到[0,1]闭区间的映射。 ：85分，即A()=0.85 ：75分，即A()=0.75 ：98分，即A()=0.98 ：30分，即A()=0.30 ：60分，即A()=0.60 这样确定出一个模糊子集A=(0.85,0.75,0.98,0.30,0.60). 定义2：设U为论域，U上的一个模糊集合A由U上的一个实值函数：U-[0,1]表示。对于， (u)称为u对于A的隶属度，而称为A的隶属函数。 对我们来