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

作     者：贾俊华 

作者单位：东南大学 

学位级别：硕士

导师姓名：关秀翠

授予年度：2017年

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

主      题：l∞模 极大加和支撑树 组合优化逆问题 时间复杂性 

摘      要：本文研究的是l模下调整最大权重w的极大加和支撑树逆问题.极大加和支撑树问题是在一个边赋权无向连通图G(V,E,c,w)中,找一棵最优的支撑树T*,使得目标函数maxw(e)+∑ c(e)最小,该问题的时间复杂度为O(m log n),其中m:= |E|,n:= |V|.它的逆问题描述为:给定网络G的一棵非最优的支撑树T,调整网络各边的权重w到(?),使得T成为新网络G(V,E,c,(?))下的最优极大加和支撑树,其中w-l≤(?)≤w+u,l≥0,u≥0.目标函数是使得maxe∈Eq(e)|w(e)-(?)(e)|最小,其中q(e)是调整1单位w(e)所需的费用.本文首先分析了该逆问题的可行解和最优解所具有的性质,其次得到了如何通过给定的可行目标函数值构造可行解这个重要结论.最后我们分别讨论了三种情况.首先在无界的单位无穷模情况下,我们根据最优值的性质设计了二分法确定最优值的下界,进一步根据最优解的性质确定了最优值,并证明了该算法的迭代次数不超过O(m),算法的时间复杂度为O(m log n).在赋权无穷模的情况下,我们先讨论了无界的情况,再推广到一般有界的情况.我们先将已知树上的边分成两类,根据每类边的不同性质设计了寻求最优解的算法.证明了算法最多调用O(m)次求解极大加和支撑树问题的算法,因此时间复杂度为O(m log n).