论文部分内容阅读
NP难度问题是计算机科学中最难求解的一类问题的总称。在人类文明高度发达的今天,人们对于NP难度问题仍然无法给出经典数学所希求的那种完整精确,快速高效的求解办法。然而在现实生活中的各行各业中普遍存在着大量的NP难度问题,它们已成为制约技术发展的瓶颈。如何现实的求解NP难度问题是数学家和计算机科学家们在二十一世纪必须面对的重要挑战。等圆packing问题是所有NP难度问题中最天然明白的一个。它询问在平面上如何尽量紧密地放置N个半径为1的圆饼,紧密性的度量是这放好了的N个圆饼的外包装圆的半径Rn,Rn越小越好。等圆packing问题是某些实际装填布局问题的一种抽象表述,更重要的,它是我们研究如何求解NP难度问题的最天然明白的思考介质和靶子。在今天,它已成为国际上检验NP难度问题求解算法的性能的最天然的试金石。经过20余年的努力,美国大数学家R.L.Graham及其近百名的师友与学生研制出了许多不同的算法,对于每一个具体的N（N=1,2,3,…,100）,他们联合起来都得到了一个他们认可的最好结果—N个圆饼的布局图象及其相应的外包装圆的半径Rn。我们的工作结果是得到了一个唯一确定的统一算法,利用此算法对这100个N值分别进行了计算,得出了相应的布局,最后打破了Graham学派所保持的世界纪录中的8项纪录,即对于N=66,67,70,71,73,77,89,99找到了更好的布局图案,将相应的包装圆的半径Rn缩小了十万分之一至千分之一:10-5—10-3我们所用的方法是改进的拟物方法,即当拟物算法陷入局部极小值陷阱时,就天然地引进高强度的引力与斥力,迫使各个圆饼作剧烈的运动以使计算跳出局部极小值点的陷阱走向前景更好的地方。原始的拟物算法的不足之处在于计算陷入局部极小值陷阱时就无能为力了,需要调用拟人策略.然而拟人策略的制定又颇费时力,有时还难免带有一些人为的性质.在改进的拟物算法中,计算点的下降与跳坑都是拟物,所以可被称之为完全的拟物算法.