背包算法计算速度极限被发现，物流金融都能用上

背包算法计算速度极限被发现，物流金融都能用上

中国新闻网于5月27日在北京发布消息，记者是孙自法，“背包问题”属于计算机科学里经典的NP完全问题，意思是非确定性图灵机多项式复杂度求解的决定问题，它是其中之一，其相关研究在长时间以来一直备受科学家的关注。

5月27日，有记者从中国科学院金属研究所了解到，该所的研究员张志东最近在计算机科学基础理论领域，取得了一项突破性的进展，他首次精确地确定了“背包问题”的计算复杂度下限，通俗来讲，也就是发现了计算速度的极限。

有关破解“背包问题”复杂度之谜其为中国科学家所取得且属于基础研究成果表现的那篇论文，在近日实现了于美国数学科学研究所出版社(AIMS)《数学》期刊的发表。

该研究的自旋玻璃三维伊辛模型最小核模型的示意图，红色自旋朝着随机方向分布，蓝色自旋存在阻错，由中国科学院金属研究所提供图片。

张志东研究员进行科普解读，提到一个情况，那就是“背包问题”，此问题假设你面临这样一种状况，有一个容量存在限制的背包，在你面前摆放着N件物品，这些物品价值各不相同，其重量也各不相同，要思考的是如何去选择物品组合才能够让总价值实现最大化，这看上去是一个比较简单的选择问题，然而实际上其中隐藏着计算方面的玄机，当物品数量超过一定规模之后，就算是使用最先进的计算机，也需要耗费如同天文数字一般多的时间去求解，而这里所说的“计算复杂度下限”指的是解决这个问题所需要的最少时间。

于现实生活里，涵盖于物流运输范畴怎样去优化集装箱装载方案，于金融投资范畴怎样去构建收益达至最大化的投资组合，于材料科学范畴怎样去寻觅最优原子排列方式等，均牵涉“背包问题”。

中国科学院金属研究所予以讲述，在历经10余年对于三维伊辛模型的研究工作的基础之上，张志东研究员于此次构建起“背包问题”同自旋玻璃三维伊辛模型之间的联系，依据两个问题所具备的关系来明确“背包难题”在计算复杂度方面的下限。

每一个物品的选择，存在取或者不取的情况，他把这对应为微观粒子的两种自旋状态，进而将价值最大化的问题做出转化，转化为找到系统最低能量状态的问题，之后他发现了“绝对极小核心模型”，通过这个发现揭示出计算复杂度的本源，其本源来自三维晶格中自旋排列所具备的特殊拓扑结构。

通过进一步构建计算复杂度相图示的方式，张志东首次描绘出NP完全问题与NP中间问题（这类问题在NP类里，既不属于P类问题，也不属于NP完全问题）之间的分界线，借着这个操作确定了复杂度下限，证明最优算法的时间复杂度起码为(1 + ε)的N次方（其中ε是趋近于0的正数），且该结果显著优于现有的1.3的N次方的算法。

此消息由业内专家宣称，“背包问题”能够被映射成诸多别的科学问题，中国科学家此次破解“背包问题”复杂度之谜所获研究结论能够直接进行推广运用，但会助力解决计算机、物理、化学、生物、数学，并且还有材料科学领域一系列与之相关的基础科学问题。