中國科學(xué)家破解“背包問題”復(fù)雜度之謎 發(fā)現(xiàn)計算速度極限
中新網(wǎng)北京5月27日電 (記者 孫自法)“背包問題”是計算機科學(xué)中經(jīng)典的NP完全問題(非確定性圖靈機多項式復(fù)雜度求解的決定問題)之一,其相關(guān)研究長期以來備受科學(xué)家關(guān)注。
記者5月27日從中國科學(xué)院金屬研究所獲悉,該所張志東研究員最近在計算機科學(xué)基礎(chǔ)理論領(lǐng)域取得一項突破性進展,首次精確確定了“背包問題”的計算復(fù)雜度下限,通俗而言就是發(fā)現(xiàn)計算速度極限。
中國科學(xué)家破解“背包問題”復(fù)雜度之謎的這項基礎(chǔ)研究成果論文,近日在美國數(shù)學(xué)科學(xué)研究所出版社(AIMS)《數(shù)學(xué)》期刊發(fā)表。

張志東研究員科普解讀說,“背包問題”假設(shè)你有一個容量有限的背包,面前擺著N件價值不同、重量各異的物品,如何選擇物品組合才能使總價值最大化?這個看似簡單的選擇問題,實則暗藏計算玄機:當(dāng)物品數(shù)量超過一定規(guī)模后,即使使用最先進計算機也需要耗費天文數(shù)字時間求解,而“計算復(fù)雜度下限”就是解決問題所需的最少時間。
在現(xiàn)實生活中,包括在物流運輸領(lǐng)域如何優(yōu)化集裝箱裝載方案、在金融投資領(lǐng)域如何構(gòu)建收益最大化的投資組合、材料科學(xué)領(lǐng)域如何尋找最優(yōu)原子排列方式等,都涉及“背包問題”。
中國科學(xué)院金屬研究所介紹,在10余年三維伊辛模型研究工作的基礎(chǔ)上,張志東研究員此次建立起“背包問題”與自旋玻璃三維伊辛模型的聯(lián)系,根據(jù)兩個問題的關(guān)系確定“背包難題”的計算復(fù)雜度的下限。
他通過把每個物品的選擇(取或不取)對應(yīng)為微觀粒子的兩種自旋狀態(tài),將價值最大化問題轉(zhuǎn)化為尋找系統(tǒng)最低能量狀態(tài),發(fā)現(xiàn)“絕對極小核心模型”,揭示計算復(fù)雜度的本源來自三維晶格中自旋排列的特殊拓?fù)浣Y(jié)構(gòu)。
進一步通過構(gòu)建計算復(fù)雜度相圖,張志東首次描繪出NP完全問題與NP中間問題(在NP類中既不是P類問題也不是NP完全問題的問題)的分界線,從而確定復(fù)雜度下限,證明最優(yōu)算法的時間復(fù)雜度至少為(1+ε)^N(ε為趨近0的正數(shù)),顯著優(yōu)于現(xiàn)有1.3^N的算法。
業(yè)內(nèi)專家稱,“背包問題”可以被映射為許多其他的科學(xué)問題,中國科學(xué)家此次破解“背包問題”復(fù)雜度之謎的研究結(jié)論可以直接推廣應(yīng)用,將助力解決計算機、物理、化學(xué)、生物、數(shù)學(xué)以及材料科學(xué)領(lǐng)域一系列相關(guān)基礎(chǔ)科學(xué)問題。(完)

社會新聞精選:
- 2025年07月15日 10:17:40
- 2025年07月15日 07:48:37
- 2025年07月14日 18:13:41
- 2025年07月14日 15:56:24
- 2025年07月14日 14:38:15