信息服務(wù)的構(gòu)造與驗(yàn)證研究報(bào)告

蘇開樂

摘 要：可滿足性問題（SAT），最大可滿足性問題（MAX-SAT）與最大團(tuán)問題（MC）都是典型的基本的NP-難解問題。該報(bào)告概述了這些難解問題的實(shí)驗(yàn)算法方面的國際研究現(xiàn)狀和國內(nèi)研究進(jìn)展，并對(duì)國內(nèi)外研究進(jìn)展進(jìn)行了比較，最后討論和展望了難解問題求解的發(fā)展趨勢(shì)。

關(guān)鍵詞：可滿足性 最大可滿足性 最大團(tuán)問題

Abstract：AT， MAX-SAT， and Maxclique are typical fundamental NP-hard problems. This paper summarizes both the state of the art and domestic progress of experimental algorithm research for these problems. The comparison between the domestic and international research endeavor in recent years ispresented. Finally， the trends of research on solving hard problems are discussed.

Key Words：SAT MAX-SAT Maxclique

閱讀全文鏈接（需實(shí)名注冊(cè)）：http：//www.nstrs.cn/xiangxiBG.aspx？id=51733&flag=1