求解几何拓扑网络设计问题的一种新方法.PDF

内江师范学院学报 第20卷第6期 0F TEAcHERSCOLLEGE No．6V01．20 ·88· JOURNALNEUIANG 求解几何拓扑网络设计问题的一种新方法 陈杰东 (广东轻工职业技术学院经济系．广东 广州 510300) 摘 要：由于几何拓扑网络设计中许多问题都可以归结为极小极大问题，而熵函数法正是求解极小极大 问题的一个强有力的数学工具，所以本文试图运用熵函数法求解一些几何拓扑网络设计问题．理论分析和试 验结果均表明了熵函数法求解这些同题的有效性． 关键词：熵函数；几何拓扑网络设计问题}极小极大问题 中图分类号：018文献标识码：A 文章编号：1671—1785(2005)06—0088一03 引言 几何拓扑网络设计同题在许多领域，特别是在网络设计、计算机图形学、模式识别、地理数据库、计算机辅助设计、机 器人学等领域中得到了广泛的应用Ⅲ．这些问题都是一些组合最优化问题，而且往往可以归结为极小极大问题，比如最 G(0))等等．求解这些问题的方法有 大间隙问题(MAxG)、最小覆盖问题(MJⅣc)、有障碍物的最大间隙问题(MAx 很多．较传统的是数学规划方法，但新发展起来的计算几何方法往往有更好的效果…．数学规划方法，如单纯形法，可以 适用于许多问题，而计算几何算法则是“特殊问题特殊解决”，一个算法总是针对特定的问题而设计的，所以各有各的优 点和缺点．本文采用数学规划方法中的熵函数法01来解决这一大类问题，在我们的方法中设计了一些参数，这些参数可 以根据特定问题的情况和人们的经验进行设定，所以也起到了“特殊问题特殊解决”的效果．尽管熵函数法并不一定能 求得问题的最优解，但理论上它求得的近似解可以跟最优解任意逼近，可以通过设定参数来满足工程上的任意蛤定的精 度要求，而且，重要的是．从实验结果可以看出它的时间复杂度是线性的． 下一节介绍熵函数法；第三节以最小覆盖问题为范例．介绍了熵函数法在几何拓扑网络设计中的应用；第四节给出 了试验结果和一些参数控制注意问题；第五节进行了方法应用推广；最后在第五节中进行了小结． 2 熵函数法 考虑如下的极小极大问题： (尸)mmmax，h) J∈∥1≤f≤“ 这里^妇)是P中连续可微的函数，卅≥2是正整数．P是一类比较典型的非光滑优化间题，是许多实际问题的数学模 展起来的熵函数法(或称凝聚函数法)是一种较新颖而实用的方法．它借用信息论中shann。n熵的概念，推导出一旗光精 Fo)的近似解．以下给出极大熵函数的导出． 记Fo)；max{^“))，A={^∈肜t^≥o．i=1，…m，∑^；1)．易知： 】《。‘“ 。一l F扛)一max{≥：^^扛)} 1∈“j ，＆)的极大熵函数是按信息论中的最大埔原理得到的，它定义如下： n^} 蹦∞。搿‘善堋曲一古善u 其中一÷∑¨n^表示带参数户的shannon信息熵．经简单的计算可得： 收稿日期：2005一05—12 作者简介：陈杰东(1980一)，男，广东佛山人，广东轻工职业技术学院助教。 万方数据 2005年12月 陈杰东：求解几何拓扑两络设计问题的一种新方法 ·89· ， F，(z)=÷ln{∑F一“}， r -一l 且F，o)道有下列性质： z∈彤 oF，(z)一胁)警，v 可见，F，缸)一致逼近F缸)．熵函数法主要是依据F，缸)的这个性质进行计算的． 因此．所谓熵函数法，就是对给定极小极大阀题尸，不直接求其最优解，而通过求出问题P的熵函数的最优值．以 此作为问题的近似解的方法 3 熵函数港在几何拓扑