概述與組合優(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－完備問題 ? 有成千上萬個(gè) NP－完備問題，如：整數(shù)線性規(guī)劃、團(tuán)、貨郎擔(dān)問題、適定性問題、點(diǎn)覆蓋、獨(dú)立集、哈密頓圈問題、 0－ 1背包問題。事實(shí)上要證明一個(gè)問題是 NP－完備的轉(zhuǎn)化為要證明： 1） 該問題是 NP的 2） 有一個(gè)已知的 NP－完備問題可以多項(xiàng)式時(shí)間轉(zhuǎn)化為該問題。 ? NP－困難問題 P NP NPC NPH ? 一個(gè)問題的最優(yōu)算法求得該問題每個(gè)實(shí)例的最優(yōu)解，啟發(fā)式算法是對應(yīng)最優(yōu)算法提出的。定義為：一個(gè)基于直觀和經(jīng)驗(yàn)的短發(fā)，在可接受的花費(fèi)下給出待解決組合最優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，改可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。 ? 在某些情況下，特別是實(shí)際問題中，最優(yōu)算法的計(jì)算時(shí)間使人無法忍受或因問題的難度事情計(jì)算時(shí)間隨實(shí)例規(guī)模的增加以指數(shù)速度增加。如 TSP枚舉算法。 ? 背包問題的貪婪算法 ? Step1 對物品以 從大到小排列，不妨把排列記成{1
語文相關(guān)推薦
鄂ICP備17016276號-1