论文部分内容阅读
反问题不仅有很重要的理论研究价值,而且有很大的实际应用价值.在求解一个组合优化问题的时候,我们通常假设问题中的参数均是确定的,而且关心的是如何求解问题的最优解.但在实际中,往往得到的仅仅是这些参数的估计值,而且知道某些给定的解是问题的最优解(或者是满足要求的解).反问题研究的是如何确定参数的值,使得某些给定的解是问题在这些参数值下的最优解(或是满足要求的解),且使总的改造费用尽可能少.
约束最小支撑树的反问题是通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用Hamming距离来衡量修改的费用,且修改费用最小.本文从三个不同模型对Hamming距离下约束最小支撑树的反问题进行了讨论.
第一个讨论总和型Hamming距离下约束最小支撑树的反问题,通过修改网络边上的权,用总和型Hamming距离来衡量修改的费用,且修改费用最小.我们把总和型Hamming距离下约束最小支撑树的反问题转化为最小权点覆盖问题,并给出了多项式算法.
第二个讨论瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改网络边上的权,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小.我们把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法.
第三个讨论Hamming距离下费用受限制的约束最小支撑树反问题,此问题是在总和型Hamming距离和瓶颈型Hamming距离下约束最小支撑树的反问题的基础上增加一个费用限制,使修改的总费用不超过给定的上界.最后给出Hamming距离下费用受限制的约束最小支撑树反问题的多项式算法.