算法設(shè)計(jì)與分析

內(nèi)容概要

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

書(shū)籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

評(píng)論、評(píng)分、閱讀與下載

---

    算法設(shè)計(jì)與分析 PDF格式下載

---