概述與組合優(yōu)化概念續(xù)(編輯修改稿)
2025-05-26 12:02 本頁面
【文章內(nèi)容簡介】 的問題，比如簡單的數(shù)組排序問題是 P類問題，但是 P屬于 NP，所以也是 NP問題 . ? 現(xiàn)在還不知道是否有 P=NP或者 PNP，但是后來人們發(fā)現(xiàn)還有一系列的特殊 NP問題，這類問題的特殊性質(zhì)使得很多人相信 PNP，只不過現(xiàn)在還無法證明。這類特殊的 NP問題就是 NP完全問題 ? NP－ Complete（ NP完備類） ? 常見的 NP－完備問題 ? 有成千上萬個 NP－完備問題，如：整數(shù)線性規(guī)劃、團、貨郎擔問題、適定性問題、點覆蓋、獨立集、哈密頓圈問題、 0－ 1背包問題。事實上要證明一個問題是 NP－完備的轉(zhuǎn)化為要證明： 1） 該問題是 NP的 2） 有一個已知的 NP－完備問題可以多項式時間轉(zhuǎn)化為該問題。 ? NP－困難問題 P NP NPC NPH ? 一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解，啟發(fā)式算法是對應最優(yōu)算法提出的。定義為：一個基于直觀和經(jīng)驗的短發(fā)，在可接受的花費下給出待解決組合最優(yōu)化問題每一個實例的一個可行解，改可行解與最優(yōu)解的偏離程度不一定事先可以預計。 ? 在某些情況下，特別是實際問題中，最優(yōu)算法的計算時間使人無法忍受或因問題的難度事情計算時間隨實例規(guī)模的增加以指數(shù)速度增加。如 TSP枚舉算法。 ? 背包問題的貪婪算法 ? Step1 對物品以 從大到小排列，不妨把排列記成{1
語文相關推薦
鄂ICP備17016276號-1