求解Covering问题的拟物方法——NP难度问题的一个处理途径  

A QUASIPHYSICAL METHOD FOR SOLVING THE COVERING PROBLEM——AN APPROACH TO TACKLING NP HARD PROBLEM

作　　者：黄文奇[1] 

机构地区：[1]华中理工大学

出　　处：《计算机学报》1989年第8期610-616,共7页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：本文提出的算法模拟了由万有引力和屏蔽现象所引起的力学过程.这种拟物的方案可为许多NP难度的问题得出有价值的近似算法.该算法对拟物类型的选择与现代递归论中的有穷损害优先方法的精神是一致的.An approximate algorithm is proposed for solving the well-known NP hardproblem-the covering problem based on the quasiphisical concept. The phenomenon dueto universal gravitation and screen was simulated. It is pointed out that valuable approximate algorithms can be obtained for large numbers of NP hard problems by following the quasi-physical procedure. Behind the quasiphysics procedure are strategies in priority method in modern recursion theory.

关 键 词：Covering问题 NP难度 拟物方法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]