計(jì)算復(fù)雜性理論介紹-資料下載頁(yè)
2024-09-04 19:19本頁(yè)面
【導(dǎo)讀】要比較算法A和算法B的速度，需要在同一機(jī)器上，同種條件下，同一輸入數(shù)據(jù)運(yùn)行兩個(gè)程序，并比較其時(shí)間。而考慮問(wèn)題規(guī)模，在一般情況下和最壞情況下需要多少次運(yùn)算。例n的二叉樹(shù)，要訪問(wèn)所有結(jié)點(diǎn)。計(jì)算復(fù)雜性理論是問(wèn)題難易程度的理論。對(duì)問(wèn)題的規(guī)模n，確定循環(huán)次數(shù)。，)(np是多項(xiàng)式函數(shù)，則稱C算法是多項(xiàng)式。舉例：班上是否有年齡小于20的同學(xué)？對(duì)于旅行商判定問(wèn)題還沒(méi)有找到解這個(gè)問(wèn)題的多項(xiàng)式算法。如果回答“是”，我們?nèi)绻麘岩删驼?qǐng)他給一條這樣的旅行路線經(jīng)證實(shí)。抓住了多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證性。感覺(jué)上，NP中元素更多，傾向P?完全問(wèn)題是NP中最難的.所有NP完全問(wèn)題構(gòu)成一個(gè)集合，它們之間等價(jià)。決了，其它問(wèn)題也就解決了。題）TSP問(wèn)題是NP難題。，或大部分情況。簡(jiǎn)單，通俗,有代表性。＊并非人工智能的所有困難在于NP問(wèn)題或指數(shù)爆炸。沒(méi)什么差別，但是在應(yīng)用上會(huì)有所不同
【正文】 ?1l ? 存在二類簡(jiǎn)化： a: ?????????? ABAB , b: BBAB ????????? , 至少和 A? 一樣難 . B? 解決了 A?? 也解決了 NP 完全 判定問(wèn)題 ????1 ；對(duì)所有其它判定問(wèn)題 ????39。 ，有 139。 ??? ，則 1? 是 NP完全的。 ??? 完全問(wèn)題是 NP 中最難的 . 定理 : ????? 21, .1? 是 NP完全的 . 21 ??? 則 2? 也是 NP完全的 . 所有 NP 完全問(wèn)題構(gòu)成一個(gè)集合，它們之間等價(jià)。即一個(gè)問(wèn)題解決了，其它問(wèn)題也就解決了。 旅行商判定問(wèn)題是一個(gè) NP 完全問(wèn)題，上述集合包含了 300 多個(gè)問(wèn)題。 七、 NP難題 21 ??? , ????1 完全問(wèn)題 . 2? 是 NP 難的 (不管 ????2 是否滿足。 ) TSP 判定問(wèn)題是 NP 完全問(wèn)題；例 2 算法（ TSP 判定問(wèn)題調(diào)用 TSP 問(wèn)題） TSP 問(wèn)題是 NP 難題。 八、總結(jié) 。 （時(shí)間、空間）。 52 nn ? （ n 取一定值），一般 2n? ~3n ，或大 部分情況（線性規(guī)劃中單純形方法）。 簡(jiǎn)單，通俗 , 有代表性。 （不僅僅用于比較算法，主要用于研究問(wèn)題本身）。 ＊并非人工智能的所有困難在于 NP 問(wèn)題或指數(shù)爆炸。 ＊理論上 nnf ?)( 與 nnf 10)( ? 沒(méi)什么差別，但是在應(yīng)用上會(huì)有所不同 參考書(shū)： “ NP 問(wèn)題與優(yōu)化問(wèn)題”
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1