第二章產(chǎn)生式系統(tǒng)的搜索策略3-資料下載頁
2025-08-26 14:56本頁面
【導(dǎo)讀】兩個程序，并比較其時間。一般來說，兩個算法的速度比較應(yīng)獨立于機器。而考慮問題規(guī)模，在一般情況下和最壞。情況下需要多少次運算。例為n的二叉樹，要訪問所有結(jié)點。例計算復(fù)雜度為!計算復(fù)雜性理論是問題難易程度的理論。對問題的規(guī)模n，確定循環(huán)次數(shù)。,mC}.對于任意一對城市iC、jC∈C，有“距。舉例：班上是否有年齡小于20的同學(xué)？對于旅行商判定問題還沒有找到解這個問題的多項式算法。果回答“否”，則對于每一條這樣的路徑，驗證它是否?抓住了多項式時間內(nèi)可驗證性。感覺上，NP中元素更多，傾向P?完全問題是NP中最難的.所有NP完全問題構(gòu)成一個集合，它們之間等價。旅行商判定問題是一個NP完全問題，上述集合包含了300多個問題。，或大部分情況。簡單，通俗,有代表性。＊并非人工智能的所有困難在于NP問題或指數(shù)爆炸。沒什么差別，但是在應(yīng)用上會有所不同
【正文】 b: BBAB ????????? , 至少和 A? 一樣難 . B? 解決了 A?? 也解決了 NP 完全 判定問題 ????1 ；對所有其它判定問題 ????39。 ，有 139。 ??? ，則 1? 是 NP 完全的。 ??? 完全問題是 NP 中 最難的 . 定理 : ????? 21, . 1? 是 NP 完全的 . 21 ??? 則 2? 也是 NP 完全的 . 所有 NP 完全問題 構(gòu)成一個集合，它們之間等價。 即一個問題解決了，其它問題也 就解決了。 旅行商判定問題是一個 NP 完全問題， 上述集合包含 了 300 多個問題。 七、 NP難題 21 ??? , ????1 完全問題 . 2? 是 NP 難的 (不 管 ????2 是否 滿足 。 ) TSP 判定 問題 是 NP 完全 問題 ；例 2算法（ TSP 判定 問題 調(diào)用 TSP 問題 ） TSP 問題 是 NP 難題 。 八、總結(jié) 。 盡 可能 不寫 計算 復(fù)雜度 為 指數(shù) 的 程序（時間、空間） 。 52 nn? （ n 取一定值），一般 2n? ~ 3n ，或大部分情況（線性規(guī)劃中單純形方法） 。 簡單，通 俗 , 有 代表性 。 智能的定義（不僅僅 用于比較算法，主要 用于 研究問題本身） 。 ＊并非人工智能的所有困難在于 NP 問題或指數(shù)爆炸 。 ＊ 理 論上 nnf ?)( 與 nnf 10)( ? 沒 什么差別 ， 但 是 在 應(yīng)用上會有所不同 參考書： “ NP 問 題與優(yōu)化問題 ”
公司管理相關(guān)推薦
鄂ICP備17016276號-1