简介:本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小。把瓶颈型Hatnming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法。
简介:约束传播算法是求解约束满足问题的一种重要方法.调度问题是一种特殊的约束满足问题.本文介绍了调度问题中的Edge-Finding和Energy-Reasoning两种分离约束传播算法,并对它们进行了比较,文中最后给出了一种结合Energy-Reasoning的Edge-Finding改进算法.
简介:为解决一次性n人囚徒困境中局中人如何走出困境的问题,引进了背叛惩罚函数及其严厉度和参与人的背叛愿意度等概念,并用数学论证法证明了如下结果:(1)参与人的背叛愿意度都不超过1。(2)背叛愿意度越大,这个参与人越愿意背叛;(3)背叛愿意度为0零时,这个参与人是否背叛其赢得一样;(4)当背叛愿意度取负数时,其绝对值越大,参与人的合作积极性越大。得到博弈结果的判定法:(1)计算各参与人的背叛愿意度。(2)若至少有一个参与人愿意背叛,则全体参与人都背叛。(3)若全体参与人都愿意合作,则合作成功。例子表明,本结果在理论上可有效地解决中局中人如何走出困境和在给定惩罚机制下博弈结果的预测问题。