《NP難解問題的近似算法》是1998年世界圖書出版公司出版的圖書，作者是Dorit S.Hochbaum。
基本介紹
- 書名：NP難解問題的近似算法
- 作者：Dorit S.Hochbaum
- ISBN：9787506236300
- 定價：93.0
- 出版社：世界圖書出版公司
- 出版時間：1998-03-01
內容介紹,作品目錄,
內容介紹
Approximation al
作品目錄
Introduction
Do
Do
NP難解問題的近似算法
相關詞條
- NP難解問題的近似算法
《NP難解問題的近似算法》是1998年世界圖書出版公司出版的圖書,作者是Dorit S.Hochbaum。...
- NP完全問題
NP類問題:所有的非確定性多項式時間可解的判定問題構成NP類問題。非確定性算法:...差→接受或捨棄”的疊代,並逐步衰減t值,算法終止時的當前解即為所得近似最優...
- 近似算法
在計算機科學與運籌學,近似算法是指用來發現近似方法來解決最佳化問題的算法。近似算法通常與NP-hard問題相關; 由於不可能有效的多項式時間精確算來解決NP-hard問題,...
- NP-hard
接受NP完全問題(NP-Complete或NPC)和NP難題(NP-Hard或NPH)不存在有效算法這一猜想,認為這類問題的大型實例不能用精確算法求解,必須尋求這類問題的有效的近似算法...
- NPC問題
這些問題中任何一個如果存在多項式時間的算法,那么所有NP問題都是多項式時間可解...近似算法:這類算法可以快速發現離最佳解在一定差距內的次佳解。...
- NP完全性
研究NP完全問題的處理方法,這對許多實際問題的算法設計和分析很有幫助,並與NP=...因此,對於NP完全問題,最好是去尋找近似解法,或者針對該問題的某些有實用價值的...
- 組合最佳化算法
這一類組合最佳化問題歸為所謂的NP-hard問題。受人類認識能力的限制,目前人們只能...人們不得不嘗試著為這些問題設計近似算法(Approximate Algorithm)、啟發式算法(...
- 設施選址問題的近似算法
《設施選址問題的近似算法》是2013年科學出版社出版的圖書,作者是徐大川、張家偉。...... 設施選址問題的近似算法內容簡介 編輯 設施選址問題是經典的NP-難解問題之...
- 計算機和難解性
第一章粗略地介紹了計算複雜性的一些基本概念和NP完全性理論的意義。第二章至第五章介紹了NP完全性的基本理論和證明的方法。第六章集中研究NP難問題的近似算法。...
- TSP問題
接受NP完全問題(NP-Complete或NPC)和NP難題(NP-Hard或NPH)不存在有效算法這一猜想,認為這類問題的大型實例不能用精確算法求解,必須尋求這類問題的有效的近似算法...
- 布爾可滿足性問題
MAX-SAT是最大可滿足性問題,是SAT的FNP推廣。它要求最大數量的條款,任何轉讓都可以滿足。它具有有效的近似算法,但是NP難以精確解決。更糟糕的是,它是APX完全的,...
- 最大割問題
Max-Cut問題是APX-hard,意味著沒有多項式時間近似方案(PTAS),任意接近最優解,對於它,除非P = NP。因此,每個多項式時間近似算法實現嚴格小於1的近似比。...
- 集合覆蓋問題
這就是經典的集合覆蓋問題(SCP)。它是NP-hard類的最最佳化組合問題。對於NP-HARD類的問題,在P≠NP的假設下,是不存在多項式時間算法的,只能設計求解他們的近似算法...
- 算法設計與分析(第4版)
第7章介紹機率算法,對許多難解問題提供解決途徑。第8章介紹NP完全性理論和解NP難問題的近似算法。第9章介紹有關串和序列的算法。第10章通過實例介紹算法設計中...
- 裝箱問題
由於目前NP完全問題不存在有效時間內求得精確解的算法,裝箱問題的求解極為困難,因此,從70~80年代開始,陸續提出的裝箱算法都是各種近似算法,如下次適應、首次適應、...
- 分配問題
1976年S ahni和Gonzales證明了QAP不僅屬於NP-hard問題而且不存在近似度的多項式時間近似算法。QAP是很難求解的最最佳化問題,其主要原因是所謂的“組合爆炸”現象,求解...
- 算法設計與分析習題解答與學習指導
主教材的主要內容包括基礎知識、分治策略、動態規劃、貪心法、回溯與分支限界、算法分析與問題的計算複雜度、NP完全性、近似算法、隨機算法、處理難解問題的策略等。...
- 算法分析與設計技術
第三章算法設計技術,分別給出了常用的算法設計技術,如貪心算法、分而治之算法、動態規劃、回溯、分枝定界與局部搜尋技術。第四章解答NP難解問題的近似算法,給出...
- 算法基礎
12.5.5NP難問題35612.5.6非確定性算法35712.6複雜性類縱覽35912.7習題36212.8參考與深入閱讀366第13章啟發式和近似算法36913.1啟發式算法369...
- 流水車間與開放車間調度算法漸近分析
在這些問題中,絕大多數都是NP難的,即此類問題無法在多項式時間內求得最優解....可行解,把它作為最優解的近似值.通常,這樣的近似解可以通過構造啟發式算法而...
- 有效算法
數學家強烈的認為:人們不可能找出一個有效算法這一事實是NP-Complete問題的固有...因此,對這類問題,尋找近似解的有效算法便自然成為人們追求的方向。...
- 算法之道
算法的一大方面:基礎、設計、分析、經典和難解問題...14.9 證明NP難的技巧 26414.10 整數規劃 265...15.5 智慧型窮舉、近似算法和本地搜尋 277...
- 算法設計與分析(屈婉玲、劉田、張立昂、王捍貧編著書籍)
算法分析與問題的計算複雜度、NP完全性、近似算法、隨機算法、處理難解問題的策略等.書中突出對問題本身的分析和求解方法的闡述,從問題建模、算法設計與分析、改進...
- 李曉亞
個人簡況 主要成果:在算法最佳化設計方面,通過考慮一種NP難問題的近似算法分析,建立按需最優計算算法框架,並將這種設計理念套用在其它類NP難問題之上;基於數據包絡...
