l1模下调整最大权值的极大加和支撑树逆问题

作     者：龚亚娟 

作者单位：东南大学 

学位级别：硕士

导师姓名：关秀翠

授予年度：2018年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：l1模 极大加和支撑树 基本割 组合优化逆问题 

摘      要：本文研究的是一类在l1模下调整最大权值w的极大加和支撑树逆问题。极大加和支撑树问题是在一个边赋权无向连通图G=(V,E,c,w)中,找一棵最优的支撑树T*,使得目标函数max w(e)+∑c(e)最小,该问题的时间复杂度为0(mlogn),其中m:=|E|,n:=|V|。它的逆问题描述为:给定网络G的一棵非最优的支撑树T0,调整网络各边的权重w到w,使得T0成为新网络G=(V,E,c,w)的最优极大加和支撑树,其中w-l≤w+u,l≥0,u≥ 0。目标函数是使得调整边权的总费用在l1模下尽可能地小,即min ∑q(e)|w(e)-w(e)|,其中q(e)是调整1单位w(e)所需的费用。这篇文章首先建立l1模下极大加和支撑树逆问题的数学模型,并引入符号对模型进行了简化,然后分析该逆问题的可行解和最优解所具有的性质,给出了树边最大权值的上下界。接着考虑了无界单位l1模下的逆问题,针对三种调整权值的方式进行具体分析,设计了基于基本割和关键边求树外边权值总上调量的子算法,最终给出了无界单位l1模下求解极大加和支撑树逆问题的启发式算法。本文还设计了求解该问题的基于树外边全排列顺序的算法,并通过数值实验将两种算法的运行结果及运行效率进行了对比,说明了该算法的有效性。