【带核三元分划问题的计算复杂性及其启发式算法】.pdf
目录 摘要.引言,三.计算复杂性证明 四,带核三元分划间题的启发式算法 及其精确界估计.五后记 六.参考文献 6Z
二、引言 对数集={a,a2a.}(不妨设a为递减)和 定义在E的子集上的函数f,称P=(S,S2S)是E 的一个分划,若:US,=B,SrS=C对任意的i,j,i≠j.定义P的费用:F(P)=∑f(S!,一般的分划间题:求B上的分划P.使:F(P)=minF(P),(对所有的分划P)当固定k时,上述同被称为k-分划:如再要求 每个子集-S:-=m为固定.则间题被称作k-shape 分划:这些间题F.K.Hw8ng在[1]中及4]中给出所谓有序分 划条件下的一些算法和理论,三元分划问题的判定描述为:实例:一个含有n个元素的有穷集E,给定正实数界 限B以及a∈E的
g∈S:S≤3,i=1,m,使得对任意i:1