計算復雜性理論介紹-wenkub.com
2024-08-31 19:19 本頁面
【正文】 ＊并非人工智能的所有困難在于 NP 問題或指數(shù)爆炸。 （時間、空間）。 旅行商判定問題是一個 NP 完全問題，上述集合包含了 300 多個問題。 ，有 139。 2. 用 B? 求最高成績 。 六、 NP完全類（ NP Completeness） P和 NP 的關(guān)系 ???? 反之， ???? ？如果成立 ? P = NP 如果不成立 ? P? NP 不知道 TSP 判定問題 ? NP，沒有找到多項式時間算法。 舉例：（ P 類問題）班上是否有年齡小于 20 的同學？ 五、 NP（ Nondeterministic Polynomial）類問題 對于旅行商判定問題還沒有找到解這個問題的多項式算法。 和旅行商問題相 關(guān)的判定問題： 一個有窮的“城市”集合 C={1C ， 2C ,… , mC }. 對于任意一對城市 iC 、 jC ∈ C，有“距離” ???),( ji CCd ，以及界限 ???? （正整數(shù)集合）。 指數(shù)時間算法不是好算法。 jn。 一般來說，兩個算法的速度比較應獨立于機器。而考慮問題規(guī)模，在一般情況下和最壞情況下需要多少次運算。 j++) k=i+j。 計算復雜性理論是問題難易程度的理論。 問：是否有 C 的一個旅行路線，全長不超過 B。但如果回答“是”，我們?nèi)绻麘岩删驼埶o一條這樣的旅行路線經(jīng)證實。 所以有“ P = NP
公司管理相關(guān)推薦
鄂ICP備17016276號-1