| 匹配问题实例空间和解空间结构 |
| |
| 引用本文： | 马俊,高成修. 匹配问题实例空间和解空间结构[J]. 数学杂志, 2003, 23(2): 181-184 |
| |
| 作者姓名： | 马俊 高成修 |
| |
| 作者单位： | 武汉大学数学与统计学院,430072 |
| |
| 基金项目： | 国家自然科学基金资助项目 ( 7992 80 0 1，79870 0 91，A0 2 2 40 17) |
| |
| 摘 要： | 本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。
|
| 关 键 词： | 匈牙利算法 二维匹配问题 实例空间 解空间 复杂度 |
| 文章编号： | 0255-7797(2003)02-0181-04 |
STRUCTURE OF INSTANCE SPACE AND SOLUTION SPACE FOR 2-DIMENSIONAL MATCHING PROBLEM |
| |
| MA Jun GAO Cheng|xiu. STRUCTURE OF INSTANCE SPACE AND SOLUTION SPACE FOR 2-DIMENSIONAL MATCHING PROBLEM[J]. Journal of Mathematics, 2003, 23(2): 181-184 |
| |
| Authors: | MA Jun GAO Cheng|xiu |
| |
| Abstract: | There might be a close relationship between the structure of a problem's s|instance and the complexity of problem. For a combinatorial optimization problem of dimension n, the more facets there are in the s|instance spaces of a problem, the more likely that an algorithm solving the problem has to be exponential. In this paper, we expose that there exist relationships among problem's instance spaces, problem's solution spaces and hungary algorithm. The conclusion shows that the number of facets in the s|instance spaces seems to be neither necessary nor sufficient for the complexity of an algorithm. In fact, it is the key that the solution spaces are reasonably divided into a set of subspaces. |
| |
| Keywords: | hungary algorithm 2|dimensional matching problem s|instance space solution space injection complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
