第七章np問(wèn)題選講-文庫(kù)吧資料
2024-11-01 14:53本頁(yè)面
【正文】 范式）：如果一個(gè) 布爾公式 是一些子句的 合取 （與） ，而且子句是一個(gè)文字或多個(gè)文字的 析取 （或） ， 則該公式是 CNF。第七章 NP問(wèn)題選講 鄒權(quán)（博士） 計(jì)算機(jī)科學(xué)系 概念 規(guī)約 最大獨(dú)立集問(wèn)題 提要 概念 ?判定問(wèn)題 ? P是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法 求解的 判定問(wèn)題 的集合。 ? NP問(wèn)題是所有可用多項(xiàng)式時(shí)間算法 驗(yàn)證 其猜測(cè)準(zhǔn)確性的 判定問(wèn)題 的集合。 –如果 CNF中每個(gè)子句都有且只有 3個(gè)不同的文字，則該公式稱為 3CNF。x 1 ? 172。x1 ? 172。x 4) 規(guī)約 ?最大團(tuán)問(wèn)題 –對(duì)于無(wú)向圖 G，一個(gè)團(tuán)即圖 G的一個(gè)完全子圖 –最大團(tuán)問(wèn)題即是否可以找出一個(gè)團(tuán)，使得其包含的頂點(diǎn)個(gè)數(shù)大于 k ?頂點(diǎn)覆蓋問(wèn)題 –對(duì)于無(wú)向圖 G=(V,E)，是否可以找出子集V’，使得如果邊 (u,v
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1