算法設計與分析

內容概要

　　《高等學?！笆濉币?guī)劃教材·計算機軟件工程系列：算法設計與分析》為大學計算機相關專業(yè)核心課程——“算法設計與分析”教材。全書以算法設計策略為知識單元，系統(tǒng)介紹算法設計方法與分析技巧，主要內容包括：算法概述、分治與遞歸、貪心算法、動態(tài)規(guī)劃、搜索算法、網絡流和匹配、線性規(guī)劃。在介紹每一種方法時，闡述了它的應用背景，并注意與其他方法的比較。　　《高等學?！笆濉币?guī)劃教材·計算機軟件工程系列：算法設計與分析》結構簡明、內容豐富，為突出教材的可讀性和可用性，章內設有典型例題分析，章末配有難易適度的習題，有利于讀者對相關內容的理解。本書適合于作為大學計算機科學與技術專業(yè)、軟件工程專業(yè)及相關專業(yè)本科生和研究生教材，也適合廣大工程技術人員學習參考。

書籍目錄

第1章  算法概述1.1 算法的概念1.1.1 算法與程序1.1.2 算法與數據結構1.1.3 算法表示的基本方法1.1.4 算法設計1.2 算法復雜性分析的方法1.2.1 兩個算法的效率對比1.2.2 算法復雜性的度量1.2.3 復雜性的漸近性態(tài)及其階1.2.4 復雜性漸近階的重要性1.2.5 遞歸方程解的漸近階的求法小結習題第2章  分治與遞歸2.1 遞歸概述2.2 分治法概述2.3 分治法的應用2.3.1 排隊購票問題2.3.2 整數劃分問題2.3.3 "放蘋果問題2.3.4 第后選擇問題2.4 典型問題分析2.4.1 紅與黑2.4.2 循環(huán)賽日程表2.4.3 0／1背包問題2.5 遞歸和遞推2.5.1 遞歸和遞推的比較2.5.2 "最少汽油過沙漠問題2.5.3 整數劃分遞推設計2.6 遞歸的消除小結習題第3章  貪心算法3.1 貪心算法概述3.2 活動安排問題3.3 背包問題3.4 貪心算法的兩個基本要素3.4.1 貪心選擇性質3.4.2 最優(yōu)子結構性質3.5 典型問題分析3.5.1 最優(yōu)裝載問題3.5.2 刪數問題3.5.3 均分紙牌3.5.4 攔截導彈問題小結習題第4章  動態(tài)規(guī)劃4.1 矩陣連乘問題4.2 凸多邊形最優(yōu)三角剖分4.3 最長公共子序列4.4 DNA序列比對4.5 0／1背包問題4.6 多段圖問題4.7 數字三角形問題4.8 備忘錄方法4.9 典型問題分析4.9.1 游船費問題4.9.2 航線設置4.9.3 復制書稿4.9.4 括號序列小結習題第5章  搜索算法5.1 問題解空間的分析5.1.1 兩種常見的樹形問題解空間5.1.2 解空間的兩種搜索方式5.2 回溯法概述5.3 分支限界法概述5.4 裝載問題5.4.1 回溯法解裝載問題5.4.2 分支限界法解裝載問題5.5 0／1背包問題5.5.1 回溯法解0／1背包問題5.5.2 分支限界法解0／1背包問題5.6 旅行售貨員問題5.6.1 回溯法解旅行售貨員問題5.6.2 分支限界法解旅行售貨員問題5.7 典型問題分析5.7.1 子集和問題5.7.2 油田勘探問題小結習題第6章  網絡流和匹配6.1 最大流問題6.1.1 概念6.1.2 基本定理6.1.3 求最大流的標號法6.2 最小費用流問題6.3 匹配6.3.1 二部圖6.3.2 匹配6.4 典型問題分析6.4.1 物流運輸6.4.2 電力網絡6.4.3 選擇課程6.4.4 小行星小結習題第7章  線性規(guī)劃7.1 線性規(guī)劃問題及其表示7.2 線性規(guī)劃問題的數學形式7.3 一般問題轉化為約束標準型7.4 線性規(guī)劃的基、基礎可行解7.5 單純形法算法7.5.1 用消元法描述單純形法算法7.5.2 單純形算法的框架7.6 線性規(guī)劃應用小結習題參考文獻

章節(jié)摘錄

版權頁：插圖：學習目標：理解動態(tài)規(guī)劃算法的概念；掌握動態(tài)規(guī)劃算法的使用條件；掌握動態(tài)規(guī)劃算法的步驟；理解備忘錄方法與動態(tài)規(guī)劃的差異。在現實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都要作出決策，從而使整個過程達到最好的活動效果。因此，各個階段決策確定后，組成一個決策序列，因而也就確定了整個過程的一條活動路線。這種把一個問題看做是一個前后關聯(lián)具有鏈狀結構的多階段過程，就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段采取的決策，一般來說是和時間有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產生出來的，故有“動態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃。動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，希望找到具有最優(yōu)值的解。在比較基本的算法設計思想里，動態(tài)規(guī)劃是比較難于理解的一種，但是卻又十分重要。動態(tài)規(guī)劃的實質是分治思想和解決冗余，因此它與分治法和貪心法類似，它們都是將問題的實例分解為更小的、相似的子問題，但是動態(tài)規(guī)劃又有自己的特點，適合于用動態(tài)規(guī)劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節(jié)省時間?？梢杂靡粋€表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。

編輯推薦

《算法設計與分析》采用面向對象的c++語言作為算法描述手段，在保持c++優(yōu)點的同時，盡量使算法描述簡明、清晰。在《算法設計與分析》各章的論述中，首先分析一種算法設計策略的基本思想，然后從解決實際問題人手，由易到難地描述幾個經典的實例，使讀者既能學到一些常用的精巧算法，又能通過對算法設計策略的反復應用，牢固掌握這些算法設計的基本思想，以便收到融會貫通之效。同時，《算法設計與分析》特別注重對解同一個問題的不同算法的比較，使讀者更容易體會到每一種具體算法的設計要點和各自的優(yōu)缺點。

圖書封面

評論、評分、閱讀與下載

---

    算法設計與分析 PDF格式下載

---