作　　者： ; ; ; ;

机构地区： 华南农业大学信息学院

出　　处： 《计算机应用与软件》 2005年第2期90-92,共3页

摘　　要： 首先分析了基于Hopfield神经网络的TSP问题求解方法 ,提出从研究能量函数、状态空间分布和可行解的关系来研究以Hopfield为代表的优化神经网络的计算复杂性的思想 ;并给出从状态空间到线性表的映射方法 ,引入状态—程序复杂性。分析结果表明 ,绝对状态 -程序复杂性更为充分地反映能量函数的求解过程 ;相对状态 -程序复杂性提供了一种在多项式时间内对NP问题算法的有效性进行衡量的尺度。 Following the example solving TSP using neural network which is first presented in the paper,a new concept is introduced to study the complexity of the optimization neural network by study the relation among energy function,state space distribution and feasible solutions.The Method mapping the state space into a linear table is provided,as well as the introduction of 'state-programming complexity'.The results indicate that absolute state-programming complexity is able to reflect the solving of the energy function fully and the relative state-programming complexity provided a new way to evaluate complexity of NP problem within polynomial time.

关 键 词： 计算复杂性 神经网络 算法复杂性 计算机

领　　域： [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术]