| 一种对特殊多维0-1背包问题的约束简化方法 |
| |
| 引用本文： | 迟东璇.一种对特殊多维0-1背包问题的约束简化方法[J].渤海大学学报(自然科学版),2001(2). |
| |
| 作者姓名： | 迟东璇 |
| |
| 作者单位： | 锦州师范学院数学系!辽宁锦州121000 |
| |
| 基金项目： | 辽宁省教育厅科学基金资助 ( 980 81110 79) |
| |
| 摘 要： | 针对一类组合优化问题—多维 0 - 1背包问题 ( MKP) ,这是一个 NP-难问题 ,提出一种能减少求解难度的方法—约束化简方法。定义了 MKP的紧约束的概念。提出了一种代替多约束组的计算方法。对于经过替换后所得到的新问题 ,证明了与其原问题解精度上的等价性。
|
| 关 键 词： | NP-难问题 化简约束 紧约束 解精度等价性 |
A predigest method for the restrict of special multi-dimension 0-1 knapsack problem |
| |
| CHI Dong,xuan.A predigest method for the restrict of special multi-dimension 0-1 knapsack problem[J].Journal of Bohai University:Natural Science Edition,2001(2). |
| |
| Authors: | CHI Dong xuan |
| |
| Abstract: | The authors we lodged a method of reducing the solving difficulty the creative method of nonequivalence single restrict, aim at a kind of combination and optimize problem multi dimension 0 1 knapsack problem(also called the NP hard problem). We defined the tightness restrictive conception of this problem, and lodged a calculation method of replacing a restrict group with a single restrict condition. We proved the equivalence property of solution precision between original problem and new problem that be replaced. |
| |
| Keywords: | NP hard problem convert simple restrict tightness restrict solution precision equivalence |
| 本文献已被 CNKI 等数据库收录！ |
