計(jì)算復(fù)雜性理論介紹-閱讀頁
2024-09-24 19:19本頁面
【正文】 舉例：（ P 類問題）班上是否有年齡小于 20 的同學(xué)？ 五、 NP（ Nondeterministic Polynomial）類問題 對(duì)于旅行商判定問題還沒有找到解這個(gè)問題的多項(xiàng)式算法。我們驗(yàn)證它是否是旅行路線，是否小于 B，如果回答“否”，則對(duì)于每一條這樣的路徑，驗(yàn)證它是否 ?B。 六、 NP完全類（ NP Completeness） P和 NP 的關(guān)系 ???? 反之， ???? ？如果成立 ? P = NP 如果不成立 ? P? NP 不知道 TSP 判定問題 ? NP，沒有找到多項(xiàng)式時(shí)間算法。記為： A? B 例 1： A? ：全班學(xué)生成績(jī)排序（從大到?。? B? ：求一些學(xué)生的最高成績(jī)。 2. 用 B? 求最高成績(jī) 。 4. 如果 n = 0 則結(jié)束。 ，有 139。 ??? 完全問題是 NP 中最難的 . 定理 : ????? 21, .1? 是 NP完全的 . 21 ??? 則 2? 也是 NP完全的 . 所有 NP 完全問題構(gòu)成一個(gè)集合，它們之間等價(jià)。 旅行商判定問題是一個(gè) NP 完全問題，上述集合包含了 300 多個(gè)問題。 ) TSP 判定問題是 NP 完全問題；例 2 算法（ TSP 判定問題調(diào)用 TSP 問題） TSP 問題是 NP 難題。 （時(shí)間、空間）。 簡(jiǎn)單，通俗 , 有代表性。 ＊并非人工智能的所有困難在于 NP 問題或指數(shù)爆
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1