计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2005年
3期
46-48
,共3页
NP完全%Packing问题%可计算性%图灵机%拓扑
NP完全%Packing問題%可計算性%圖靈機%拓撲
NP완전%Packing문제%가계산성%도령궤%탁복
本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形Packing问题进行了有益的探讨.这对设计Packing问题的求解算法具有借鉴意义.
本文討論瞭離散模型與連續問題的關繫以及圖靈機的計算能力,在此基礎上擴充瞭問題及NP完全問題的定義,根據解空間的拓撲結構特點將NP完全的Packing問題分為三類,併對多邊形Packing問題進行瞭有益的探討.這對設計Packing問題的求解算法具有藉鑒意義.
본문토론료리산모형여련속문제적관계이급도령궤적계산능력,재차기출상확충료문제급NP완전문제적정의,근거해공간적탁복결구특점장NP완전적Packing문제분위삼류,병대다변형Packing문제진행료유익적탐토.저대설계Packing문제적구해산법구유차감의의.
