第二章產(chǎn)生式系統(tǒng)的搜索策略3(編輯修改稿)
2024-10-10 14:56 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 算復(fù)雜度 對(duì)問(wèn)題的規(guī)模 n，確定循環(huán)次數(shù)。 對(duì)不確定的循環(huán)次數(shù) ?估計(jì)最壞 情況 下 的計(jì)算量（如 while 循環(huán)） 三、決策（判定）問(wèn)題 判定問(wèn)題就是回答“是”或“否”的問(wèn)題。 和旅行商問(wèn)題相關(guān)的判定問(wèn)題： 一個(gè)有窮的“城市”集合 C={ 1C ， 2C ,? , mC }. 對(duì)于任意一對(duì)城市 iC 、 jC ∈ C，有“距離 ” ???),( ji CCd ，以及界限 ???? （正整數(shù)集合）。 問(wèn)：是否有 C 的一個(gè)旅行路線，全長(zhǎng)不超過(guò) B。 只考慮判定問(wèn)題的原因是它在計(jì)算理論中有一個(gè)對(duì)應(yīng)物“語(yǔ)言” 四、 P 類(lèi)問(wèn)題 多項(xiàng)式時(shí)間算法，設(shè)某算法 C 的時(shí)間復(fù)雜度是 )(nf ，其中 n 是問(wèn)題規(guī)模，有))(()( npOnf ? ， )(np 是多項(xiàng)式函數(shù)，則稱(chēng) C 算法是多項(xiàng)式時(shí)間算法。 即：時(shí)間復(fù)雜度 函數(shù)是 ))(( npO 的算法 指數(shù)時(shí)間算法：時(shí)間復(fù)雜性函數(shù)不能表示成 ))(( npO 的算法（包括： nnlog ：非多項(xiàng)式函數(shù) ，不是指數(shù)函數(shù)） P 類(lèi)問(wèn)題＝ {有多項(xiàng)式時(shí)間算法解決的判定問(wèn)題 }。 舉例：（ P 類(lèi)問(wèn)題）班上是否有年齡小于 20 的同學(xué)？ 五、 NP（ Nondeterministic Polynomial）類(lèi)問(wèn)題 對(duì)于旅行商判定問(wèn)題還沒(méi)有找到解這個(gè)問(wèn)題的多項(xiàng)式算法。但如果回答“是”，我們?nèi)绻麘岩删驼?qǐng)他給一條這樣的旅行路線經(jīng)證實(shí)。我們驗(yàn)證它是否是旅行路線，是否小于 B， 如果回答“否”，則對(duì)于每一條這樣的路徑，
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1