導(dǎo)語(yǔ)：如何才能寫好一篇?jiǎng)討B(tài)規(guī)劃思想，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公文云整理的十篇范文，供你借鑒。

篇1

關(guān)鍵詞：萬州、生態(tài)涵養(yǎng)規(guī)劃、多規(guī)協(xié)同

中圖分類號(hào)： G322 文獻(xiàn)標(biāo)識(shí)碼： A

0 引言

2013年9月13日至14日，重慶市委四屆三次全會(huì)召開。會(huì)議審議通過了《關(guān)于科學(xué)劃分功能區(qū)域、加快建設(shè)五大功能區(qū)的意見》。渝東北地區(qū)被劃為生態(tài)涵養(yǎng)發(fā)展區(qū)，這個(gè)以三峽庫(kù)區(qū)為主的區(qū)域，面臨著新的發(fā)展要求。除了要實(shí)現(xiàn)生態(tài)涵養(yǎng)的要求，更有要實(shí)現(xiàn)社會(huì)經(jīng)濟(jì)迅速發(fā)展，庫(kù)區(qū)社會(huì)和諧穩(wěn)定的要求。渝東北生態(tài)涵養(yǎng)區(qū)各區(qū)縣都迅速提出了各自的生態(tài)涵養(yǎng)發(fā)展的思路與規(guī)劃，但是總體仍然是發(fā)展戰(zhàn)略性規(guī)劃，產(chǎn)業(yè)和社會(huì)經(jīng)濟(jì)發(fā)展與環(huán)保要求居多。而區(qū)縣相對(duì)較小的地理空間，需要更具體的空間落地規(guī)劃和實(shí)施指導(dǎo)，不能夠簡(jiǎn)單照搬重慶直轄市全域主體功能區(qū)劃分的方式來落實(shí)規(guī)劃意圖，而要探索以實(shí)施導(dǎo)向的區(qū)縣生態(tài)涵養(yǎng)規(guī)劃編制思路，引導(dǎo)規(guī)劃有效實(shí)施。本文結(jié)合萬州區(qū)生態(tài)涵養(yǎng)發(fā)展規(guī)劃編制的探索來進(jìn)行分析。

1、渝東北生態(tài)涵養(yǎng)區(qū)的背景與要求

1.1背景

重慶首次將全域劃分為都市功能核心區(qū)、都市功能拓展區(qū)、城市發(fā)展新區(qū)、渝東北生態(tài)涵養(yǎng)發(fā)展區(qū)、渝東南生態(tài)保護(hù)發(fā)展區(qū)“五大功能區(qū)”，并根據(jù)各自定位，在產(chǎn)業(yè)布局、人口分布、生態(tài)建設(shè)等方面作出了調(diào)整。五個(gè)功能區(qū)域在更大的空間格局和區(qū)域范圍內(nèi)優(yōu)化資源配置，以更好地推動(dòng)重慶大都市區(qū)的發(fā)展和建設(shè)；劃分生態(tài)涵養(yǎng)發(fā)展區(qū)和生態(tài)保護(hù)發(fā)展區(qū)，是為了正確處理加快發(fā)展與保護(hù)生態(tài)的關(guān)系；明確各區(qū)域功能定位、發(fā)展重點(diǎn)和發(fā)展方向，目的是強(qiáng)化五大區(qū)域聯(lián)動(dòng)，更好地突出整體性、互補(bǔ)性和聯(lián)動(dòng)性，實(shí)現(xiàn)全市一盤棋發(fā)展，引導(dǎo)形成主體功能明確、板塊之間聯(lián)動(dòng)、資源配置優(yōu)化、整體效能提升的區(qū)域一體化發(fā)展格局。在五個(gè)功能區(qū)域劃分基礎(chǔ)上，進(jìn)一步完善考核機(jī)制，充分發(fā)揮考核評(píng)價(jià)的引導(dǎo)和激勵(lì)作用。

渝東北生態(tài)涵養(yǎng)發(fā)展區(qū)包含11個(gè)區(qū)縣，以萬州為核心，包括1個(gè)大城市（萬州），10個(gè)中小城市，196個(gè)小城鎮(zhèn)，面積約3.39萬平方公里。截止2011年底，該區(qū)域戶籍人口為1096萬人，常住人口為833萬人，城鎮(zhèn)人口為325萬人，城鎮(zhèn)化率為39.02%，城鎮(zhèn)人口占全市比重20.24%。該區(qū)域地區(qū)生產(chǎn)總值為1723.56億元，占全市域比重17.03%。該區(qū)域是國(guó)家重點(diǎn)生態(tài)功能區(qū)和農(nóng)產(chǎn)品主產(chǎn)區(qū)，長(zhǎng)江流域重要生態(tài)屏障和長(zhǎng)江上游特色經(jīng)濟(jì)走廊，長(zhǎng)江三峽國(guó)際黃金旅游帶和特色資源加工基地。需要把生態(tài)文明建設(shè)放在更加突出的地位，引導(dǎo)人口相對(duì)聚集和超載人口梯度轉(zhuǎn)移，著力涵養(yǎng)保護(hù)好三峽庫(kù)區(qū)的青山綠水，提高基本公共服務(wù)水平。

1.2要求

在五大功能區(qū)的劃分中，也對(duì)渝東北生態(tài)涵養(yǎng)區(qū)提出了以下重點(diǎn)要求：

一是把萬州作為重點(diǎn)開發(fā)區(qū)加快建設(shè)，發(fā)展特色產(chǎn)業(yè)集群，承接周邊地區(qū)人口轉(zhuǎn)移，建成三峽庫(kù)區(qū)經(jīng)濟(jì)中心，帶動(dòng)形成萬（州）開（縣）云（陽(yáng)）特色產(chǎn)業(yè)板塊。

二是增強(qiáng)梁平縣、豐都縣、墊江縣、忠縣、開縣等國(guó)家農(nóng)產(chǎn)品主產(chǎn)縣農(nóng)業(yè)綜合生產(chǎn)能力，推進(jìn)縣城及市級(jí)特色工業(yè)園區(qū)開發(fā)，構(gòu)建農(nóng)產(chǎn)品特色經(jīng)濟(jì)板塊。

三是增強(qiáng)城口縣、云陽(yáng)縣、奉節(jié)縣、巫山縣、巫溪縣等國(guó)家重點(diǎn)生態(tài)功能縣生態(tài)產(chǎn)品供給能力，因地制宜發(fā)展資源環(huán)境可承載的特色產(chǎn)業(yè)，構(gòu)建特色旅游經(jīng)濟(jì)帶。

四是根據(jù)資源環(huán)境承載能力，培育壯大有資源依托、環(huán)保水平高、吸納就業(yè)多的特色優(yōu)勢(shì)產(chǎn)業(yè)，重點(diǎn)發(fā)展特色資源加工、機(jī)械加工、輕紡食品、生物醫(yī)藥、清潔能源、商貿(mào)物流等。嚴(yán)格控制并逐步淘汰落后產(chǎn)業(yè)。大力發(fā)展特色效益農(nóng)業(yè)。大力發(fā)展生態(tài)旅游、人文旅游，加快建成長(zhǎng)江三峽國(guó)際黃金旅游帶，把旅游業(yè)打造成為支柱產(chǎn)業(yè)。

2 萬州生態(tài)涵養(yǎng)發(fā)展規(guī)劃編制的探索

2.1萬州生態(tài)涵養(yǎng)發(fā)展的基礎(chǔ)

萬州是重慶第二大城市，地處三峽庫(kù)區(qū)腹心。目前該流域內(nèi)蘊(yùn)藏著全國(guó)1/3的水資源和3/5的水能資源，擁有全國(guó)1/2的內(nèi)河通航里程，是我國(guó)水資源配置的戰(zhàn)略水源地、實(shí)施能源戰(zhàn)略的主要基地、珍稀水生生物的天然寶庫(kù)、連接?xùn)|中西部的“黃金水道”和改善我國(guó)北方生態(tài)與環(huán)境的重要支撐點(diǎn)，具有十分重要的戰(zhàn)略地位。萬州區(qū)幅員面積3457平方公里，境內(nèi)山丘起伏，最高點(diǎn)海拔1760米，最低點(diǎn)海拔120米，中山、低山、丘陵面積占90%以上，少平壩和臺(tái)地，且零星散布。境內(nèi)河流、溪澗切割深，落差大，呈枝狀分布，均屬長(zhǎng)江水系。境內(nèi)流域面積100平方公里以上的河流有共13條，溪溝93條，總水域面積為108.66平方公里。在不計(jì)基本農(nóng)田的因素下，萬州全區(qū)適宜建設(shè)用地約為 71.1平方公里，較適宜建設(shè)用地約為 475.1 平方公里。萬州適合進(jìn)行城市建設(shè)用地的承載力約為190萬人左右。通過GIS分析，得出鐵峰山、方斗山、七曜山以及長(zhǎng)江沿線是低安全格局區(qū)域，是保障生態(tài)安全的最基本保障，是城市發(fā)展建設(shè)中不可逾越的生態(tài)底線，需要重點(diǎn)保護(hù)和嚴(yán)格限制。

2.2萬州生態(tài)涵養(yǎng)發(fā)展的總體思路與空間布局

規(guī)劃到2020年基本形成生態(tài)涵養(yǎng)發(fā)展的總體格局，功能區(qū)劃清晰，發(fā)展重點(diǎn)突出，特色鮮明，生態(tài)環(huán)境明顯好轉(zhuǎn)，對(duì)主要森林、水源、景區(qū)、生物多樣性保護(hù)較好，形成重點(diǎn)生態(tài)涵養(yǎng)保護(hù)區(qū)域的新發(fā)展態(tài)勢(shì)。形成以中心城區(qū)及各鎮(zhèn)鄉(xiāng)的合理城鎮(zhèn)體系結(jié)構(gòu)，新農(nóng)村聚居點(diǎn)為主的鄉(xiāng)村居住空間體系，人口分布更加科學(xué)，城鄉(xiāng)低碳綠色建設(shè)和宜居水平大幅提升?；窘ǔ沙青l(xiāng)一體化的公共服務(wù)設(shè)施和基礎(chǔ)設(shè)施體系。社會(huì)事業(yè)更加發(fā)展，文化內(nèi)涵更加濃郁，實(shí)現(xiàn)“看得見山，望得見水，記得住鄉(xiāng)愁?！?/p>

全區(qū)生態(tài)涵養(yǎng)發(fā)展形成“一核、兩軸、多點(diǎn)”的重點(diǎn)開發(fā)空間格局，形成四帶五片保育與涵養(yǎng)的生態(tài)保護(hù)空間格局，總體形成開發(fā)與保護(hù)有機(jī)結(jié)合，城鄉(xiāng)空間一體的生態(tài)涵養(yǎng)發(fā)展的新空間結(jié)構(gòu)。

一核 ―― 中心城區(qū)

兩軸 ――長(zhǎng)江和318國(guó)道兩條重點(diǎn)發(fā)展軸線

多點(diǎn) ―― 41個(gè)鎮(zhèn)鄉(xiāng)小城鎮(zhèn)和若干鄉(xiāng)村聚居區(qū)、特色產(chǎn)業(yè)項(xiàng)目、旅游、能源基地，圍繞各中心，與生態(tài)環(huán)境有機(jī)融合的點(diǎn)狀網(wǎng)絡(luò)結(jié)構(gòu)

生態(tài)保護(hù)空間格局：

四帶――長(zhǎng)江及沿線、鐵峰山脈、方斗山脈、七曜山脈等四片重點(diǎn)生態(tài)保障區(qū)

五片――甘寧龍沙武陵片、分水李河片、白羊太安片、龍駒羅田白土片、余家后山片等五片主要集中生態(tài)保育發(fā)展片區(qū)

圖1開發(fā)空間格局規(guī)劃圖

2.3萬州生態(tài)涵養(yǎng)發(fā)展功能區(qū)類型與空間布局

在全區(qū)生態(tài)安全格局分析基礎(chǔ)上，按照不同國(guó)土空間所承擔(dān)發(fā)展與涵養(yǎng)方面的不同特點(diǎn)與職責(zé)，宜建則建，宜養(yǎng)則養(yǎng)，將全區(qū)國(guó)土空間劃定為城市建設(shè)區(qū)、城鎮(zhèn)建設(shè)區(qū)、鄉(xiāng)村聚居區(qū)、農(nóng)業(yè)保養(yǎng)區(qū)、生態(tài)保障區(qū)五類功能區(qū)域，對(duì)各類分區(qū)進(jìn)行詮釋、定義，在不同功能區(qū)綜合落實(shí)城鄉(xiāng)建設(shè)規(guī)劃、土地利用規(guī)劃、生態(tài)環(huán)境保護(hù)規(guī)劃、社會(huì)事業(yè)發(fā)展規(guī)劃和產(chǎn)業(yè)空間布局規(guī)劃的主要要求，實(shí)現(xiàn)“五規(guī)合一”協(xié)同。

城市建設(shè)區(qū)以城市綜合發(fā)展為主，促進(jìn)產(chǎn)業(yè)和社會(huì)事業(yè)充分發(fā)展，引導(dǎo)區(qū)域人口集聚，是最主要的城市生產(chǎn)生活空間。

城鎮(zhèn)建設(shè)區(qū)以城鎮(zhèn)特色發(fā)展為主，優(yōu)化空間布局，緩解生境壓力，促進(jìn)人口集聚，適度發(fā)展第二產(chǎn)業(yè)和商業(yè)服務(wù)業(yè)等第三產(chǎn)業(yè)，是主要的城鎮(zhèn)生活空間。

鄉(xiāng)村聚居區(qū)以農(nóng)村人口聚居為主，新建與改造相結(jié)合，節(jié)約資源能源，提高人居環(huán)境質(zhì)量，可適當(dāng)發(fā)展鄉(xiāng)村旅游等第三產(chǎn)業(yè)，是主要的農(nóng)村生活空間。

農(nóng)業(yè)保養(yǎng)區(qū)以發(fā)展生態(tài)農(nóng)業(yè)為主，引導(dǎo)人口有序轉(zhuǎn)移，主要發(fā)展特色農(nóng)業(yè)、觀光休閑等產(chǎn)業(yè)，是主要的農(nóng)業(yè)性生產(chǎn)空間

生態(tài)保障區(qū)以生態(tài)涵養(yǎng)為主，加強(qiáng)生態(tài)建設(shè)和環(huán)境保護(hù)，適當(dāng)發(fā)展旅游度假等第三產(chǎn)業(yè)，是主要的生態(tài)空間。

2.4鎮(zhèn)鄉(xiāng)生態(tài)涵養(yǎng)涵養(yǎng)發(fā)展的引導(dǎo)與管控

對(duì)全區(qū)53個(gè)鎮(zhèn)鄉(xiāng)街道的國(guó)土空間結(jié)合其具體情況科學(xué)劃定功能區(qū)域，分別明確各區(qū)引導(dǎo)建設(shè)內(nèi)容與禁止建設(shè)內(nèi)容，既要充分發(fā)揮各鎮(zhèn)鄉(xiāng)資源優(yōu)勢(shì)，又要落實(shí)區(qū)域生態(tài)環(huán)境建設(shè)、社會(huì)經(jīng)濟(jì)發(fā)展的要求。部分鎮(zhèn)鄉(xiāng)街道擁有前述5類功能區(qū)，部分也只擁有其中的幾種。各鎮(zhèn)鄉(xiāng)街道規(guī)劃以發(fā)展規(guī)劃圖、生態(tài)涵養(yǎng)管控（負(fù)面清單）圖及發(fā)展管控說明（表）進(jìn)行表達(dá)，如下圖案例。

圖2龍沙鎮(zhèn)生態(tài)涵養(yǎng)規(guī)劃圖

2.5規(guī)劃的實(shí)施與運(yùn)用

本規(guī)劃探索實(shí)施的路徑。規(guī)劃提出經(jīng)政協(xié)協(xié)商，黨委政府審議，人大審批后實(shí)施，嚴(yán)格執(zhí)行，不得隨意調(diào)整或突破。對(duì)禁止性要求等要重點(diǎn)監(jiān)督。原則上3年修編一次,修編前對(duì)實(shí)施情況應(yīng)進(jìn)行評(píng)估。具體建設(shè)時(shí)還應(yīng)按照土地利用、城鄉(xiāng)規(guī)劃建設(shè)、環(huán)境保護(hù)等規(guī)劃的要求，相關(guān)法律法規(guī)規(guī)定及程序進(jìn)行。

要求各鎮(zhèn)鄉(xiāng)街道要加強(qiáng)規(guī)劃的實(shí)施，在招商引資、項(xiàng)目選址等活動(dòng)時(shí)要對(duì)照本規(guī)劃，作為宏觀指導(dǎo)要求。在城市規(guī)劃、小城鎮(zhèn)規(guī)劃、土地利用規(guī)劃等規(guī)劃進(jìn)行動(dòng)態(tài)調(diào)整時(shí)，要以本規(guī)劃作為中觀指導(dǎo)依據(jù)。項(xiàng)目審批時(shí)，要以本規(guī)劃作為具體的審批規(guī)劃依據(jù)。

同時(shí)也要加強(qiáng)生態(tài)補(bǔ)償機(jī)制的研究、制度設(shè)計(jì)與實(shí)施。探索完善生態(tài)涵養(yǎng)發(fā)展指標(biāo)評(píng)價(jià)體系。

3 實(shí)施導(dǎo)向的區(qū)縣生態(tài)涵養(yǎng)發(fā)展規(guī)劃方法與思路

萬州生態(tài)涵養(yǎng)發(fā)展規(guī)劃的編制，在以下實(shí)施導(dǎo)向的重點(diǎn)編制思路與方法探索，為直轄市區(qū)縣主體功能區(qū)規(guī)劃向?qū)嵤用嫣剿魈峁┝擞幸娴闹巍?/p>

3.1多規(guī)協(xié)同的規(guī)劃

生態(tài)涵養(yǎng)發(fā)展是區(qū)縣域發(fā)展思路的調(diào)整，空間布局的優(yōu)化。而傳統(tǒng)的城鄉(xiāng)建設(shè)規(guī)劃、國(guó)土規(guī)劃、社會(huì)經(jīng)濟(jì)發(fā)展規(guī)劃等各自引導(dǎo)著發(fā)展和項(xiàng)目實(shí)施。為了生態(tài)涵養(yǎng)發(fā)展規(guī)劃意圖的落實(shí)，就必須要協(xié)同各大規(guī)劃的重點(diǎn)要求，協(xié)調(diào)各大規(guī)劃在空間落地等方面的一些矛盾，在新的生態(tài)涵養(yǎng)發(fā)展思路下形成新戰(zhàn)略、新布局，同時(shí)又探索把生態(tài)涵養(yǎng)規(guī)劃的要求，反轉(zhuǎn)到城鄉(xiāng)建設(shè)規(guī)劃、國(guó)土規(guī)劃等傳統(tǒng)法定規(guī)劃的更新落實(shí)，實(shí)現(xiàn)動(dòng)態(tài)的有機(jī)融合狀態(tài)。

3.2生態(tài)規(guī)劃要點(diǎn)把控

生態(tài)涵養(yǎng)發(fā)展規(guī)劃中“生態(tài)”是重點(diǎn)。而各規(guī)劃中涉及到的生態(tài)要素眾多，規(guī)劃綜合時(shí)既要考慮實(shí)現(xiàn)產(chǎn)業(yè)轉(zhuǎn)型、城鄉(xiāng)空間布局優(yōu)化、生態(tài)環(huán)境保護(hù)等重大內(nèi)容，更要重點(diǎn)關(guān)注關(guān)鍵生態(tài)要素的管控，主要有水源地及相關(guān)區(qū)域，集中林地，自然保護(hù)區(qū)，風(fēng)景名勝區(qū)、森林公園、濕地等，石漠化、地災(zāi)點(diǎn)等生態(tài)修復(fù)區(qū)域。規(guī)劃既要加強(qiáng)保護(hù)，也要通過人為的建設(shè)，形成更優(yōu)的生態(tài)空間結(jié)構(gòu)和發(fā)展應(yīng)用模式。

3.3鎮(zhèn)鄉(xiāng)生態(tài)規(guī)劃的管控

鎮(zhèn)鄉(xiāng)是規(guī)劃實(shí)施的重要單元。當(dāng)區(qū)縣城成為發(fā)展的重點(diǎn)區(qū)域，項(xiàng)目的建設(shè)、生產(chǎn)運(yùn)行有較嚴(yán)格的控制。而鎮(zhèn)鄉(xiāng)成為生態(tài)涵養(yǎng)的重要空間，一是鎮(zhèn)鄉(xiāng)小城鎮(zhèn)發(fā)展中容易忽視環(huán)境類基礎(chǔ)設(shè)施建設(shè)，也是環(huán)境污染小企業(yè)的重點(diǎn)集聚地，人居環(huán)境較差。二是在農(nóng)業(yè)生產(chǎn)過程中，不注重對(duì)生態(tài)意義重要的資源保護(hù)，部分農(nóng)業(yè)、畜禽養(yǎng)殖等造成面源污染。本次規(guī)劃強(qiáng)化將各區(qū)域?qū)用嬉?guī)劃意圖、法規(guī)要求結(jié)合鎮(zhèn)鄉(xiāng)實(shí)際情況，細(xì)化到每個(gè)鎮(zhèn)鄉(xiāng)街道空間，重點(diǎn)強(qiáng)調(diào)了生態(tài)管控的要素與要求，并以鎮(zhèn)鄉(xiāng)領(lǐng)導(dǎo)、管理者容易懂，便于使用的圖表方式來表達(dá)，明白每塊國(guó)土空間適合干什么，不能干什么，運(yùn)用于發(fā)展戰(zhàn)略布局、招商引資等工作情況，大大增強(qiáng)實(shí)用性。

3.4 GIS的空間規(guī)劃疊加與分析

在規(guī)劃技術(shù)方法上，加強(qiáng)了GIS的空間規(guī)劃疊加與分析技術(shù)的應(yīng)用。首先是GIS技術(shù)對(duì)全域生態(tài)本底進(jìn)行分析，重點(diǎn)對(duì)山脈、水系、森林和需要控制的景源、地災(zāi)點(diǎn)進(jìn)行分析，結(jié)合地形坡度等進(jìn)行分析，綜合評(píng)判生態(tài)安全格局，成為規(guī)劃研究的基礎(chǔ)。再者對(duì)各大規(guī)劃（如城規(guī)、國(guó)土、交通、環(huán)保等）的要求分解并轉(zhuǎn)化為空間發(fā)展布局或管控要素線，進(jìn)行綜合疊加來推導(dǎo)方案，并與生態(tài)基礎(chǔ)分析疊加評(píng)估，增強(qiáng)了規(guī)劃的科學(xué)性。

3.5非法定規(guī)劃的實(shí)施應(yīng)用探索

作為非法定規(guī)劃，其應(yīng)用方式與保障路徑必須在規(guī)劃初期就應(yīng)該設(shè)計(jì)好，才能夠保障有較強(qiáng)的實(shí)施性。關(guān)鍵點(diǎn)一是要通過黨委政府審議、人大審批等方式，獲得有類似準(zhǔn)法定規(guī)劃的權(quán)威性，二是要設(shè)計(jì)好評(píng)估、檢查、監(jiān)督機(jī)制，有一定獎(jiǎng)懲的規(guī)則，以保障有足夠的實(shí)施自覺性。

篇2

【關(guān)鍵詞】動(dòng)態(tài)規(guī)劃；高維；優(yōu)化方法；渠道工程

目前，動(dòng)態(tài)規(guī)劃的“維數(shù)災(zāi)”問題受到計(jì)算機(jī)高速存儲(chǔ)量和計(jì)算時(shí)間的限制，在求解高維問題時(shí)，常遇困難.近40年來，各國(guó)學(xué)者對(duì)動(dòng)態(tài)規(guī)劃的計(jì)算方法進(jìn)行了多方面的探索，提出了各種方法，如旨在減少維數(shù)的拉格朗日乘子法[1]、動(dòng)態(tài)規(guī)劃逐次漸近法[2]，聚合法[3]，旨在減少離散狀態(tài)數(shù)的離散微分動(dòng)態(tài)規(guī)劃法[4]、雙狀態(tài)動(dòng)態(tài)規(guī)劃法[5]、狀態(tài)增量動(dòng)態(tài)規(guī)劃法[6]和不離散狀態(tài)直接求解以減少計(jì)算量的微分動(dòng)態(tài)規(guī)劃[7]（要求目標(biāo)函數(shù)、約束條件三階可微）以及H.R.Howson等人1975年提出的以減少階段數(shù)為手段的漸進(jìn)優(yōu)化法[7].這些方法雖然一定程度上減輕了“維數(shù)災(zāi)”，但進(jìn)展并不很大.作者在對(duì)大型渠道工程系統(tǒng)優(yōu)化設(shè)計(jì)研究時(shí)也遇到了這些問題，本文另辟其徑，采用文獻(xiàn)[8～12]中的系統(tǒng)試驗(yàn)選優(yōu)基本思想，來求解高維動(dòng)態(tài)規(guī)劃問題，則可在該領(lǐng)域內(nèi)取得突破性的進(jìn)展。

1. 大中型渠道工程優(yōu)化設(shè)計(jì)的高維動(dòng)態(tài)規(guī)劃模型及求解方法

1.1大中型渠道工程優(yōu)化設(shè)計(jì)的高維動(dòng)態(tài)規(guī)劃模型。文獻(xiàn)[13]提出了大中型渠道工程系統(tǒng)的定性定量混合系統(tǒng)動(dòng)態(tài)規(guī)劃模型，模型的決策變量為各渠段縱坡（Ii）和各渠段的定性方案（Si），目標(biāo)函數(shù)為工程計(jì)算分析期內(nèi)的總支出費(fèi)用，并考慮首末水位、不沖不淤、渠道最小水位銜接和工程總投資約束. 為了進(jìn)一步提高模型決策的精度，在文獻(xiàn)[13]的模型基礎(chǔ)上，再考慮以下約束：

1.1.1填挖土方量約束。若獲得滿足約束條件，且使文獻(xiàn)[13]目標(biāo)函數(shù)最小的解，而渠道工程的填方量大于挖方量，附近又沒有土方資源，此時(shí)文獻(xiàn)[13]中模型獲得的解就不一定為最優(yōu)解，因此，還應(yīng)加上填挖方量約束方程。

1.2求解方法?？紤]全部約束條件，則模型為四維問題，該模型的求解工作量、難度比文獻(xiàn)[13]的二維問題大大增加了，為此本文在模型的求解方面進(jìn)行了一定的探討，提出了高維動(dòng)態(tài)規(guī)劃的試驗(yàn)選優(yōu)方法。

1.2.1基本原理。本文對(duì)高維動(dòng)態(tài)規(guī)劃的降維傳統(tǒng)技術(shù)之一——拉格朗日乘子法[1]進(jìn)行了修正，提出了廣義拉氏方法，使加入到目標(biāo)函數(shù)中去的約束檢驗(yàn)在計(jì)算迭代過程中進(jìn)行，而不是傳統(tǒng)的計(jì)算迭代結(jié)束后檢驗(yàn)，因而不管拉格朗日乘子取值多少，采用廣義拉氏方法的解均為滿足約束條件的可行解.此時(shí)的問題就轉(zhuǎn)化為尋找最優(yōu)拉氏乘子的問題，根據(jù)數(shù)學(xué)模型和拉氏乘子的物理意義，容易知道拉氏乘子的取值范圍，在此基礎(chǔ)上則可采用部分試驗(yàn)選優(yōu)方法[8～12]（如正交試驗(yàn)法）確定最優(yōu)的乘子值。

1.4實(shí)例分析。采用文獻(xiàn)[13]算例，有關(guān)主要參數(shù)和可能的定性方案見表1.通過計(jì)算分析u2，u3，u4的取值范圍均取為[0，2.4]，選用L9（34）型正交表對(duì)所選的9個(gè)uj組合進(jìn)行了對(duì)應(yīng)的一維動(dòng)態(tài)規(guī)劃問題求解，其最優(yōu)解和采用DDDP法求解結(jié)果目標(biāo)值相差5.6%，對(duì)uj進(jìn)一步離散選用L25（56）型正交表選擇對(duì)應(yīng)25個(gè)uj組合進(jìn)行對(duì)應(yīng)的一維動(dòng)態(tài)規(guī)劃問題求解分析，其最優(yōu)解和采用DDDP法求解結(jié)果基本相同，此時(shí)占用計(jì)算機(jī)的運(yùn)算時(shí)間不到DDDP法的1/6，有關(guān)計(jì)算主要成果摘要見表2和表3。

2. 結(jié)論

（1）尋求高維動(dòng)態(tài)規(guī)劃的求解方法是近40年國(guó)內(nèi)外眾多學(xué)者久攻不下的系統(tǒng)科學(xué)重大研究的課題.目前經(jīng)典方法一般僅能求解3～5維問題，其它近似方法也只能求解數(shù)拾維問題.本文提出的試驗(yàn)選優(yōu)方法可以使較高維數(shù)的高維動(dòng)態(tài)規(guī)劃問題求解成為可能.本文的試驗(yàn)方法主要針對(duì)正交試驗(yàn)法而言的，對(duì)于采用其它部分試驗(yàn)選優(yōu)方法進(jìn)行優(yōu)化分析，還有待于進(jìn)一步探討。

（2）本文提出的大型渠道工程優(yōu)化設(shè)計(jì)的高維動(dòng)態(tài)規(guī)劃模型對(duì)大型調(diào)水工程優(yōu)化設(shè)計(jì)具有較為重要的參考價(jià)值。

參考文獻(xiàn)

[1]Leon C， Mary W C.Introduction to Dynimic Programming.PergamonmPress， 1981， 197～207.

[2]Bellman R E， Dreyfus S E. Applied Dynamic Programming.Princeton Unversity Press， 1962， 293～3852.

[3]Turgeon A. A decomposition method for the long＼|term schednling of reservoirs in series. Water resources research， 1981，17（6）.

[4]Heidar M，Chow V T， et al. Disrete differential dynamic programming approach to water resource optimization.Water resources research， 1971，17（2）.

[5]Ozden M. A binary state DP algorithm for operation problem of multireservoir system. Water resource resecrch.1984，20（1）.

[6]Larson R E. State increment dynamic prorgamming.Management science 19， 1973，1452～1458.

[7]白憲臺(tái)，多維動(dòng)態(tài)規(guī)劃.北京：水利電力出版社，1988，43～52.

[8]程吉林，金兆森，大系統(tǒng)模擬試驗(yàn)選優(yōu)方法及應(yīng)用.水利學(xué)報(bào)，1993，（11）.

[9]程吉林，孫學(xué)華，模擬技術(shù)、正交設(shè)計(jì)、層次分析及其在灌區(qū)優(yōu)化規(guī)劃中的應(yīng)用.水利學(xué)報(bào)，1990，（9）.

[10]程吉林.某些特殊路徑問題的正交表法.系統(tǒng)工程，1991，（2）.

[11]程吉林.介紹一種大系統(tǒng)優(yōu)化的知識(shí)模型.系統(tǒng)工程理論和實(shí)踐，1992，（4）.

[12]Jilin C， et al. Optimal test theory of large scale system and applying in irrigation district scheme.System science and system engineering，（ICCSSE'93）Edited by Zheng Weimin， International Academic Publishers Press， 1993， 348～356.

[13]Jilin C， et al. A dynamic programming medol of mixture system for conveyance canal engineering.Journal of system science and system engineering， 1993，4（2）.

[14]高侖彥.正交及回歸設(shè)計(jì)方法.北京：冶金工業(yè)出版社，1985.

[15]北京大學(xué)力學(xué)系概率統(tǒng)計(jì)組.關(guān)于正交設(shè)計(jì)的優(yōu)良性.應(yīng)用數(shù)學(xué)學(xué)報(bào)，1977，（1～2）.

篇3

動(dòng)態(tài)規(guī)范是算法里一種非常重要的方法,是求解決策過程最優(yōu)化的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃自問世以來,在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問題,用動(dòng)態(tài)規(guī)劃方法比用其他方法求解更為方便。

本文通過對(duì)經(jīng)典的01背包問題的求解,從動(dòng)態(tài)規(guī)劃的角度進(jìn)行闡述,通過案例對(duì)該算法的計(jì)算過程進(jìn)行了直觀的描述,并對(duì)該算法進(jìn)行了一定的優(yōu)化,最后指出該算法的優(yōu)缺點(diǎn)。

[關(guān)鍵詞]背包 動(dòng)態(tài)規(guī)劃 時(shí)間復(fù)雜度 空間復(fù)雜度

[中圖分類號(hào)]TP31[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1009-5349(2010)05-0121-03

前言

背包問題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃模型,很多關(guān)于算法的教材都把它作為一道例題,該問題既簡(jiǎn)單又容易理解,而且在某種程度上還能夠揭示動(dòng)態(tài)規(guī)劃的本質(zhì)。

將具有不同重量和價(jià)值的物體裝入一個(gè)有固定載重量的背包,以獲取最大價(jià)值,這類問題被稱為背包問題。

背包問題可以擴(kuò)展出很多種問題,而01背包問題是最常見、最有代表性的背包問題。

一、問題描述

給定一個(gè)載重量為M的背包及n個(gè)物體,物體i的重量為wi、價(jià)值為pi,1≤i≤n,要求把這些物體裝入背包,使背包內(nèi)的物體價(jià)值總量最大。此處我們討論的物體是不可分割的,通常稱這種物體不可分割的背包問題為01背包問題。

二、基本思路

01背包問題的特點(diǎn)是:每種物體只有一件,可以選擇放或者不放。假設(shè):xi表示物體i被裝入背包的情況,xi=0,1。當(dāng)xi=0時(shí),表示物體沒有被裝入背包;當(dāng)xi=1時(shí),表示物體被裝入背包。根據(jù)問題的要求,有如下的約束方程(1)和目標(biāo)函數(shù)(2):

三、利用動(dòng)態(tài)規(guī)劃法求解01背包問題

(一)動(dòng)態(tài)規(guī)劃算法的基本思想

動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中,可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值,我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個(gè)子問題,先求解子問題,然后從這些子問題的解得到原問題的解。與分治法不同的是,適合于用動(dòng)態(tài)規(guī)劃求解的問題,經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題,則分解得到的子問題數(shù)目太多,有些子問題被重復(fù)計(jì)算很多次。如果我們能夠保存已解決的子問題的答案,而在需要時(shí)再找出已求得的答案,這樣就可以避免大量的重復(fù)計(jì)算,節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到,只要它被計(jì)算過,就將其結(jié)果填入表中,這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣,但它們具有相同的填表格式。

(二)算法設(shè)計(jì)

假定背包的載重量范圍為0～m。類似于資源分配那樣,令optpi(j)表示在前i個(gè)物體中,能夠裝入載重量為j的背包所得的最大價(jià)值,j=1,2,……,m。顯然,此時(shí)在前i個(gè)物體中,有些物體可以裝入背包,有些物體不能裝入背包。于是,可以得到下面的動(dòng)態(tài)規(guī)劃函數(shù):

(4)式表明:把前面i個(gè)物體裝入載重量為0的背包,或者把0個(gè)物體裝入載重量為j的背包,得到的價(jià)值都為0。(5)式表明:當(dāng)?shù)趇個(gè)物體的重量大于背包的載重量時(shí),裝入前i個(gè)物體得到的最大價(jià)值,與裝入前i-1個(gè)物體得到的最大價(jià)值一樣,即第i個(gè)物體沒有裝入背包。(6)式表明:當(dāng)?shù)趇個(gè)物體的重量小于背包的載重量時(shí),如果第i個(gè)物體裝入背包,背包中物體的價(jià)值,等于把前i-1個(gè)物體裝入載重量為j-wi的背包所得到的價(jià)值與第i個(gè)物體的價(jià)值pi之和;如果第i個(gè)物體沒有裝入背包,則背包中物體的價(jià)值,等于把前i-1個(gè)物體裝入載重量為j的背包,卻不裝入第i個(gè)物體所取得的價(jià)值。顯然,這兩種裝入方法,在背包中所取得的價(jià)值不一定相同,因此,取這兩者中的最大值,作為把前面i個(gè)物體裝入載重量為j的背包所取得的最優(yōu)價(jià)值。

該算法可分為n階段:

第一階段,只裝入一個(gè)物體,計(jì)算在不同載重量的背包情況下,所取得的最大價(jià)值;

第二階段,裝入前兩個(gè)物體,按(5)式和(6)式計(jì)算在不同載重量的背包情況下,取得的最大價(jià)值;

……

第n階段,裝入前n個(gè)物體,按(5)式和(6)式計(jì)算在不同載重量的背包情況下,取得的最大價(jià)值,而在背包載重量為M時(shí),所得結(jié)果就是我們想要的結(jié)果。

為了確定具體哪個(gè)物體裝入背包,從optpn(m)的值向前倒推。有如下遞推關(guān)系式:

(7)式表明:如果optpi(j)大于optpi-1(j),則物體i被裝入背包;如果optpi(j)等于optpi-1(j),表明i物體未被裝入背包。按照該關(guān)系式,i從n到1依次類推,直到確定第一個(gè)物體是否被裝入背包為止,就能確定裝入背包的具體物體。

(三)存儲(chǔ)結(jié)構(gòu)

該算法需要將每一個(gè)物體的重量和價(jià)值分別存儲(chǔ)起來,并針對(duì)不同載重量的背包對(duì)物體分別計(jì)算,故考慮使用數(shù)組來實(shí)現(xiàn)。對(duì)于物體i,用weight[i]來表示重量、用p[i]表示價(jià)值,解向量用x[i]表示物體i是否被放入,上面提到的optpi(j)則用二維數(shù)組相應(yīng)的optp[i][j]來表示,物體個(gè)數(shù)n,背包載重量為m。

(四)算法實(shí)現(xiàn)

initial knapsack_dynamic(initial optp[][],weight[],p[],x[],n,m)

{

initial i,j,value;

//根據(jù)(4)式初始化第0列及解向量X

//解向量初始值設(shè)置為false,表示起初所有物體均未放入背包

for(i = 0; i

{

optp[i][0] = 0;

x[i] = FALSE;

}

//根據(jù)(4)式初始化第0行

for(i = 0; i

{

optp[0][i] = 0;

}

//利用(5)(6)式計(jì)算optp[i][j]

for(i = 1; i

{

for(j = 1; j

{

optp[i][j] = optp[i-1][j];

if((j >= weight[i]) && (optp[i-1][j - weight[i]]+p[i]) > optp[i-1][j])

optp[i][j] = optp[i-1][j-weight[i]] + p[i];

}

}

//確定裝入背包的具體物體

j = m;

for(i = n; i > 0; i--)

{

if(optp[i][j] > optp[i-1][j])

{

x[i] = TRUE;

j = j - weight[i];

}

}

//value就是所要求的值

value = optp[n][m];

return value;

}

1.案例分析

現(xiàn)有載重量為10的背包,有四個(gè)物體A、B、C、D,其重量分別為4、2、5、3,價(jià)值分別為4、3、5、8,要求放入物體使背包所獲價(jià)值最大。

用optp[i][j]來存儲(chǔ)這四個(gè)物體在不同載重量的背包下所獲的價(jià)值,計(jì)算過程如下表所示:

2.時(shí)間空間復(fù)雜度

該算法中,矩陣optp的大小為(m+1)×(n+1),物體的重量、價(jià)值和解向量大小都等于物體個(gè)數(shù)n,故該算法的空間復(fù)雜度為O(nm)。對(duì)物體重量、價(jià)值的初始化(算法實(shí)現(xiàn)略)所需時(shí)間都為n,解向量和矩陣第0行初始化時(shí)間為n,矩陣第0列初始化時(shí)間為m,對(duì)矩陣optp的計(jì)算所需時(shí)間為n×m,解向量X的確定時(shí)間為n,故整個(gè)算法的時(shí)間復(fù)雜度為O(nm)。

(五)算法優(yōu)化

在上述算法中,時(shí)間復(fù)雜度不能再繼續(xù)優(yōu)化了,但是空間復(fù)雜度是可以繼續(xù)優(yōu)化的。

上述算法中,存儲(chǔ)optp使用的是二維數(shù)組,其大小為(m+1)×(n+1),但是仔細(xì)觀察發(fā)現(xiàn),optp[i][j]只與optp[i-1][j]和optp[i-1][j - weight[i]]有關(guān),與optp[k][l](k=1,2,……,i-2,i+1,……n,j=1,2,……,m)無關(guān),故可考慮只用一維數(shù)組_optp來存儲(chǔ),_optp[j]相當(dāng)于optp[i][j]。而考慮到optp[i][j]是由optp[i][j]和optp[i-1][j - weight[i]]共同計(jì)算得到的,故該算法中的j循環(huán)要從后往前計(jì)算,_optp[]的計(jì)算算法設(shè)計(jì)如下所示:

for(i = 1; i

{

for(j = m; j >= 1; j--)

{

if((j >= weight[i]) && (_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

上述例子中,相應(yīng)的_optp[j]計(jì)算結(jié)果如下表所示:

}

}

上述例子中,相應(yīng)的_optp[j]計(jì)算結(jié)果如下表所示:

顯然,對(duì)于物體i,_optp[j]的計(jì)算不會(huì)影響到_optp[0,1,……,weight[i]-1],故上述算法可繼續(xù)優(yōu)化為:

for(i = 1; i

{

for(j = m; j >= weitht[i]; j--)

{

if((_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

對(duì)于01背包問題,常見的要求有兩種:一種是恰好裝滿背包、另一種則沒有要求,針對(duì)這兩種問法,可從初始化上來區(qū)分。

當(dāng)要求恰好裝滿背包時(shí),初始化時(shí)將_optp[0]設(shè)為0,其他_optp[1,2,……,m]全部設(shè)為-∞,這樣就可保證最終得到的_optp[n]是一種恰好裝滿的最優(yōu)解,此時(shí)可以把初始化理解成沒有任何物體可放時(shí),只有容量為0的背包能被價(jià)值為0的nothing“恰好裝滿”;當(dāng)沒有這個(gè)限制時(shí),初始化時(shí)應(yīng)將_optp[0,1,……,m]都設(shè)為0,此時(shí)可以理解為任何一個(gè)背包都有一個(gè)合法的解“什么都不裝”,這個(gè)解的價(jià)值為0。

當(dāng)優(yōu)化后,空間復(fù)雜度變?yōu)镺(m),計(jì)算所需時(shí)間為:

當(dāng)weitht[i]較大時(shí),可以節(jié)省很多時(shí)間。

動(dòng)態(tài)規(guī)劃的缺點(diǎn):對(duì)于01背包問題,用動(dòng)態(tài)規(guī)劃方法解很容易理解,但是這種方法有一些弊端,從上述算法可以看出:當(dāng)物體的重量較大時(shí),所需的物理空間較大;當(dāng)物體的重量不是整數(shù)時(shí),無法利用數(shù)組來存儲(chǔ)該結(jié)構(gòu)。

四、結(jié)束語(yǔ)

在日常生活中,01背包問題有很多應(yīng)用,比如如何利用有限空間的手提包,裝入外出旅行的各種必需品。

篇4

關(guān)鍵詞:背包算法;優(yōu)先策略;動(dòng)態(tài)規(guī)劃;棧操作

中圖分類號(hào):TP274文獻(xiàn)標(biāo)識(shí)碼:B

文章編號(hào):1004-373X(2010)02-128-03

Design and Analysis of Knapsack Problem

YU Miao

(Anshan Meteorological Bureau of Liaoning Province,Anshan,114004,China)

Abstract:Knapsack problem is typical problem in computer science and its solution is a hot spot in algorithms design and verification.The solutions for the knapsack problems,algorithms design and verification with three different means:preference strategy,dynamic programming and recursion.Correctness of these three algorithms are proved,in the complexity analysis,the complexity of space and time in preference strategy is lowest,while the dynamic programming has obvious superiority.

Keywords:knapsack problem;preference strategy;dynamic programming;stack peration

0 引 言

算法研究是計(jì)算機(jī)科學(xué)的重要組成部分,有觀點(diǎn)認(rèn)為 “計(jì)算機(jī)科學(xué)是一門研究算法的科學(xué)”[1,2],無論這種觀點(diǎn)是否全面,都足以說明算法研究在計(jì)算機(jī)科學(xué)發(fā)展中所具有的重要作用及地位。算法研究是通過程序來實(shí)踐的。程序=算法+數(shù)據(jù)結(jié)構(gòu)[3,4],這一大家都熟知的公式更加表明算法研究不是單純的數(shù)學(xué)問題,必須通過 “實(shí)踐”掌握算法的實(shí)質(zhì)。這里對(duì) “背包問題”采用優(yōu)先策略、動(dòng)態(tài)規(guī)劃及遞歸三種不同方法進(jìn)行求解、算法設(shè)計(jì)及驗(yàn)證,并通過各種算法予以實(shí)現(xiàn)。本文研究、分析了實(shí)現(xiàn) “背包問題”算法的實(shí)質(zhì)。

1 問題描述

一旅行者攜帶背包去登山,已知所能隨身攜帶的背包重量限度為 b,現(xiàn)有n種物品可供選擇裝入背包。第i種物品重量為ai,其重要性價(jià)值指標(biāo)為ci,旅行者應(yīng)如何選擇攜帶各種物品,以使總價(jià)值最大[5,6]。

“背包問題”的數(shù)學(xué)模型為:

max z=∑ni=1cixi

約束條件為:

∑ni=1aixi≤b,ai>0,ci>0,

xi=0或1, 1≤i≤n

2 優(yōu)先策略的算法設(shè)計(jì)

按重量a1≥a2≥a3≥a4≥…≥an對(duì)xi進(jìn)行調(diào)整,作為待選隊(duì)列[7,8]。

假設(shè)前面已經(jīng)選擇了s個(gè),即jr1,jr2,…,jrs為最優(yōu)選擇的前s件物品,則應(yīng)滿足:

cr1,cr2,…,crs,且∑si=1 ai

對(duì)后面等待選擇的物品jk來說,與之對(duì)應(yīng)的ak無疑滿足:

ak≤ari, i=1,2,…,s

即所選擇的物品重量比其所有待選擇的物品重量大。因此,對(duì)待選擇的物品是否被選中將分為:∑si=1ari+ak≤b和∑si=1ari+ak>b 兩種情況。

(1) 對(duì)于∑si=1ari+ak≤b的情況,將xk插入已選擇的J隊(duì)列中,然后根據(jù)ci的大小找到其相應(yīng)的位置。

(2) 對(duì)于∑si=1ari+ak>b的情況,有:

① 若存在ck≥cri,則將xk插入并按ci排序后,將jri從已選擇的隊(duì)列中刪除并插入按ci從大到小、重量從小到大地排序到二次篩選隊(duì)列中。

② 若存在ck

③ 當(dāng)待選隊(duì)列為空時(shí),選擇隊(duì)列從s到1與從二次篩選隊(duì)列中選擇的元素進(jìn)行優(yōu)化選擇。若存在:

∑n-s-mj=1aj+∑s-1i=1ari≤b, ∑n-s-1j=1cj>cri

將組合的各元素Xi插入已選擇的J隊(duì)列中,然后根據(jù) ci的大小找到其相應(yīng)的位置:jri,jr2,…,jrs。

④ 當(dāng)③中已完成對(duì)首元素組合的篩選后,此時(shí)的J隊(duì)列為最優(yōu)選擇。

3 動(dòng)態(tài)規(guī)劃法的算法設(shè)計(jì)

動(dòng)態(tài)規(guī)劃的基礎(chǔ)是最優(yōu)化原理,其關(guān)鍵問題是建立動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型(狀態(tài)轉(zhuǎn)移方程)。主要步驟是:劃分階段,確定階段的狀態(tài);確定決策變量、權(quán)函數(shù)以及指標(biāo)函數(shù);建立狀態(tài)轉(zhuǎn)移方程;根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理建立遞歸方程;自底向上遞推逐步求解。

(1) 劃分階段k:將供選擇的物品按 1,2,…,n排序,每個(gè)階段可裝入一種物品;

(2) 確定決策變量:xk裝入第k種物品的件數(shù);背包中允許裝入前k種物品的總重量;

(3) 建立狀態(tài)轉(zhuǎn)移方程:sk=sk-1+akxk;

決策集合為:

D(sk-1)={xk|0≤xk≤[sk/xk],xk∈Z}

(4) 建立遞歸方程:

fk(sk)=maxxk=0,1,…,\{fk-1(sk-1- xkak+ ck)}

f0(0)=0

(5) 遞推求解:逐步計(jì)算出f1(s1),f2(s2),…,fn(sn)最后求得,fn(a)即為所求的最大價(jià)值。

4 遞歸的算法設(shè)計(jì)

遞歸算法的基本思想是假設(shè)用布爾函數(shù) knap(s,n) 表示 n件物品放入可容質(zhì)量為 s的背包中是否有解,當(dāng)knap函數(shù)的值為真時(shí),說明問題有解,相反當(dāng)值為假時(shí),無解。這里可以通過輸入s和n的值,進(jìn)行以下幾種情況的討論。

(1) 當(dāng)s=0時(shí),可知問題有解,即函數(shù)knap(s,n)的值為true。

(2) 當(dāng)s

(3) 當(dāng)s>0且n0且n≥1 時(shí),才符合實(shí)際情況,這時(shí)又分為兩種情況。即:

篇5

關(guān)鍵詞：管網(wǎng)設(shè)計(jì)；直接及間接優(yōu)化；設(shè)計(jì)方法

中圖分類號(hào)：S276 文獻(xiàn)標(biāo)識(shí)號(hào)：A 文章編號(hào)：2306-1499（2013）06-（頁(yè)碼）-頁(yè)數(shù)

目前，對(duì)于城市排水管道系統(tǒng)優(yōu)化設(shè)計(jì)問題，已開發(fā)了一些水力計(jì)算程序和優(yōu)化算法如直接優(yōu)化法、動(dòng)態(tài)規(guī)劃法、遺傳算法等，并在設(shè)計(jì)過程中得到一定應(yīng)用，并能顯著提高設(shè)計(jì)水平和設(shè)計(jì)效率。下面就排水管網(wǎng)優(yōu)化方法及特點(diǎn)做一簡(jiǎn)要介紹。

1.直接優(yōu)化設(shè)計(jì)方法及優(yōu)缺點(diǎn)

在管線平面布置己定情況下的污水管網(wǎng)各個(gè)參數(shù)的優(yōu)化設(shè)計(jì)，被分為直接優(yōu)化法和間接優(yōu)化法。直接優(yōu)化法是根據(jù)排水管道系統(tǒng)性能指標(biāo)的變化，通過直接對(duì)各種方案或可調(diào)參數(shù)的選擇、計(jì)算和比較，來得到最優(yōu)解或滿意解，它具有直接、直觀和容易驗(yàn)證的優(yōu)點(diǎn)。直接優(yōu)化法主要包括電子表格法和兩相優(yōu)化法。電子表格法是利用“電子表格”統(tǒng)計(jì)數(shù)據(jù)和分析數(shù)據(jù)的功能進(jìn)行管網(wǎng)優(yōu)化的。它提供了一種啟發(fā)式費(fèi)用估算方法，利用這種方法，用戶可尋找最小費(fèi)用的設(shè)計(jì)。兩相優(yōu)化法是當(dāng)設(shè)計(jì)流量確定后，在滿足約束條件的前提下，選取最小流速和最大充滿度進(jìn)而得到最優(yōu)管徑和最小坡度，最大限度的降低管道埋深。其算法與人工計(jì)算基本相同，即按污水流動(dòng)方向，先計(jì)算支管后計(jì)算干管和主干管，通過從上游至下游依次對(duì)各設(shè)計(jì)管段進(jìn)行計(jì)算，繼而完成一條管道及整個(gè)管網(wǎng)的計(jì)算。

2.間接優(yōu)化法

間接優(yōu)化法對(duì)其中的某些條件適當(dāng)取舍，把問題簡(jiǎn)化、抽象為容易解決的數(shù)學(xué)模型，通過計(jì)算得出最優(yōu)解線性規(guī)劃法是優(yōu)化技術(shù)中最常用的一種方法。它對(duì)于污水管網(wǎng)設(shè)計(jì)計(jì)算模型中的約束條件和目標(biāo)函數(shù)的非線性，分別用它們的一級(jí)泰勒展開式代替，將之化為線性規(guī)劃問題，用線性規(guī)劃的解作為問題的近似解，反復(fù)迭代，使迭代點(diǎn)序列逼近非線性規(guī)劃的最優(yōu)解。它的缺點(diǎn)是把管徑當(dāng)作連續(xù)變量來處理，存在計(jì)算管徑與市售規(guī)格管徑相矛盾的問題。把非線性函樹轉(zhuǎn)為線性函數(shù)，前期準(zhǔn)備工作量大，且難以保證結(jié)果的計(jì)算精度?；旌险麛?shù)規(guī)劃法，作為線性規(guī)劃法發(fā)展形式，克服了線性規(guī)劃的部分缺點(diǎn)，可以解出離散的標(biāo)準(zhǔn)管徑，但由于整形變量過多，往往難以求解，從而應(yīng)用受到限制。

2.1非線性規(guī)劃法

非線性規(guī)劃法是為了適應(yīng)排水管道系統(tǒng)優(yōu)化設(shè)計(jì)計(jì)算模型中目標(biāo)函數(shù)和約束條件的非線性特征而提出來的。它可以優(yōu)化選擇排水管道的直徑和埋深，以及中途泵站的位置。其假定管徑是離散的，易于對(duì)目標(biāo)函數(shù)和約束條件進(jìn)行敏感性分析。但是該方法極大地限制了目標(biāo)函數(shù)和約束條件的形式。

2.2罰函數(shù)離散優(yōu)化法

罰函數(shù)離散優(yōu)化法將排水工程的特點(diǎn)與罰函數(shù)離散思想相聯(lián)系，可以排除不合理的設(shè)計(jì)方案，以管系末端管底標(biāo)高為全局控制因素，建立與目標(biāo)函數(shù)的可行解對(duì)應(yīng)關(guān)系，并通過同時(shí)進(jìn)行整體控制與局部控制的水力計(jì)算方法，遍歷目標(biāo)函數(shù)的可行解及局部最優(yōu)解，從而得到管系的全局最優(yōu)設(shè)計(jì)方案。該方法由于對(duì)管道系統(tǒng)的各種可行解進(jìn)行遍歷，在解決大型管網(wǎng)問題時(shí)，必然存在運(yùn)行時(shí)間長(zhǎng)和內(nèi)存占用量大的缺點(diǎn)。

2.3動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法是目前在國(guó)內(nèi)外廣泛應(yīng)用的排水管道優(yōu)化設(shè)計(jì)計(jì)算方法。它的基本思想是認(rèn)為排水管道是一個(gè)多階段的決策過程，通過對(duì)研究課題劃分階段，尋求最優(yōu)路線來進(jìn)行優(yōu)化設(shè)計(jì)。它在應(yīng)用中分為兩支：一支是以各節(jié)點(diǎn)埋深做為狀態(tài)變量，通過坡度決策進(jìn)行全方位搜索，其優(yōu)點(diǎn)是直接利用標(biāo)準(zhǔn)管徑，優(yōu)化結(jié)果與初始解無關(guān)，且能控制計(jì)算精度，但要求狀態(tài)點(diǎn)的埋深間隔很小，使存儲(chǔ)量和計(jì)算時(shí)間大為增加。為了節(jié)省運(yùn)算時(shí)間，引入了逆差動(dòng)態(tài)規(guī)劃法。逆差動(dòng)態(tài)規(guī)劃法是在動(dòng)態(tài)規(guī)劃法的基礎(chǔ)上引入了縮小范圍的迭代過程，可以顯著地減小計(jì)算時(shí)間和存儲(chǔ)量，但在迭代過程中可能遺漏最優(yōu)解，而且在復(fù)雜地形條件處理跌水，緩坡情況時(shí)受到限制。另一支是以管徑為狀態(tài)變量，通過流速和充滿度決策進(jìn)行搜索的動(dòng)態(tài)規(guī)劃法。由于標(biāo)準(zhǔn)管徑的數(shù)目有限，較以節(jié)點(diǎn)埋深為決策變量方法在計(jì)算機(jī)存儲(chǔ)和計(jì)算時(shí)間上有顯著優(yōu)勢(shì)。最初的動(dòng)態(tài)規(guī)劃對(duì)每一管段選取的一組標(biāo)準(zhǔn)管徑中并不全是可行管徑，因此發(fā)展出可行管徑法?？尚泄軓椒ㄍㄟ^數(shù)學(xué)分析，對(duì)每一管段的管徑采用滿足約束條件的最大和最小管徑及其之間的標(biāo)準(zhǔn)管徑，構(gòu)成可行管徑集合，進(jìn)而應(yīng)用動(dòng)態(tài)規(guī)劃計(jì)算?？尚泄軓椒ㄊ沟脙?yōu)化計(jì)算精度得以提高，并顯著減少了計(jì)算工作量和計(jì)算機(jī)存儲(chǔ)量。盡管動(dòng)態(tài)規(guī)劃法是解決多階段決策問題最優(yōu)化的一種有效方法，但其狀態(tài)變量均應(yīng)滿足“無后效性”的特點(diǎn)?！盁o后效性”是指當(dāng)給定某一階段的狀態(tài)時(shí)，在以后各階段的行進(jìn)要不受當(dāng)前各階段狀態(tài)的影響。從前面的分析可知，在排水管道系統(tǒng)設(shè)計(jì)計(jì)算時(shí)，前一管段的設(shè)計(jì)結(jié)果將直接影響到后續(xù)管段設(shè)計(jì)參數(shù)的選用，無論是利用節(jié)點(diǎn)埋深還是管短管徑作為狀態(tài)變量，都沒有充足的證據(jù)能夠狀態(tài)變量的“無后效性”。因此利用動(dòng)態(tài)規(guī)劃法求出的污水管道優(yōu)化設(shè)計(jì)方案并不一定是真正的最優(yōu)方案。

3.優(yōu)化設(shè)計(jì)的遺傳算法

遺傳算法是近幾年迅速發(fā)展起來的一項(xiàng)優(yōu)化技術(shù)，是一種模擬自然界生物進(jìn)化過程的全局隨機(jī)優(yōu)化算法。遺傳算法借助于生物進(jìn)化機(jī)制與遺傳學(xué)原理，按照自然選擇和適者生存的原則，利用簡(jiǎn)單的編碼技術(shù)和繁殖機(jī)制，模擬自然界生物群體優(yōu)勝劣汰的進(jìn)化過程，使待優(yōu)化問題逐步從初始解進(jìn)化到問題的最優(yōu)解。簡(jiǎn)單易用、靈活方便、通用性強(qiáng)以及隱含并行性等特點(diǎn)使遺傳算法比傳統(tǒng)優(yōu)化方法具有更大的優(yōu)越性，為解決復(fù)雜系統(tǒng)優(yōu)化問題提供了一種通用框架，成為解決函數(shù)優(yōu)化、網(wǎng)絡(luò)優(yōu)化、組合優(yōu)化等許多工程優(yōu)化問題的重要技術(shù)之一。是進(jìn)化算法的一個(gè)重要分枝。利用這一進(jìn)化理論同樣可以作為排水工程實(shí)踐中的尋優(yōu)方法。應(yīng)用遺傳算法進(jìn)行污水管網(wǎng)優(yōu)化設(shè)計(jì)的關(guān)鍵在于確定合適的編碼方式以及將實(shí)際問題的優(yōu)化目標(biāo)函數(shù)轉(zhuǎn)換為遺傳算法的個(gè)體適應(yīng)度函數(shù)。

目前，遺傳算法與神經(jīng)網(wǎng)絡(luò)的結(jié)合越來越受到人們的關(guān)注，并且己經(jīng)形成了一種新穎的遺傳神經(jīng)網(wǎng)絡(luò)研究領(lǐng)域。近年來，該領(lǐng)域的研究非?；钴S，并取得了不少成果，這為遺傳神經(jīng)網(wǎng)絡(luò)更為廣泛深入的應(yīng)用帶來了充滿希望的前景。目前主要的結(jié)合方式是將遺傳算法用于神經(jīng)網(wǎng)絡(luò)權(quán)值的優(yōu)化和拓?fù)浣Y(jié)構(gòu)的設(shè)計(jì)。用遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)權(quán)值是在網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)確定的前提下進(jìn)行的，無需計(jì)算梯度信息，遺傳算法就能夠發(fā)現(xiàn)神經(jīng)網(wǎng)絡(luò)連接權(quán)值的一個(gè)接近全局最優(yōu)的權(quán)值集，這使得用遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)權(quán)值對(duì)那些大而復(fù)雜、誤差梯度信息很難獲取或根本不可用的問題特別具有吸引力。如果神經(jīng)網(wǎng)絡(luò)誤差的梯度信息容易獲取，則把遺傳算法與基于梯度信息的BP算法相結(jié)合的方法可以提高權(quán)值訓(xùn)練算法的性能。

4.結(jié)語(yǔ)

優(yōu)化設(shè)計(jì)系統(tǒng)將設(shè)計(jì)人員計(jì)算量大大降低，把設(shè)計(jì)人員從查閱圖表的繁雜過程中解脫出來，加快設(shè)計(jì)進(jìn)度，與此同時(shí)，整個(gè)排水管道系統(tǒng)得到了優(yōu)化設(shè)計(jì)。研究標(biāo)明，優(yōu)化后的排水工程大約可以降低約10%的工程造價(jià)。應(yīng)用各種優(yōu)化算法進(jìn)行排水管網(wǎng)的優(yōu)化設(shè)計(jì)在實(shí)際工程優(yōu)化設(shè)計(jì)中有較大的推廣應(yīng)用潛力，可以為工程設(shè)計(jì)優(yōu)化和科學(xué)的方案決策提供科學(xué)的參考依據(jù)，能夠達(dá)到節(jié)省工程投資和提高設(shè)計(jì)質(zhì)量的良好效果。當(dāng)然，排水管網(wǎng)的優(yōu)化算法要想被廣大工程技術(shù)廣泛接受，一方面需要設(shè)計(jì)人員勇于嘗試和應(yīng)用新技術(shù)、新方法，另一方面也需要開發(fā)出能夠?qū)⒑线m的優(yōu)化算法和傳統(tǒng)計(jì)算方法有效融合在一起的計(jì)算機(jī)輔助設(shè)計(jì)軟件，以促進(jìn)新方法在實(shí)際工程設(shè)計(jì)過程中推廣應(yīng)用。

參考文獻(xiàn)

篇6

關(guān)鍵詞：0-1背包；動(dòng)態(tài)規(guī)劃

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2007)17-31378-02

The Dynamic Programming Algorithms of 0-1 Knapsack Problem Based on Visual C++

CHEN Zi-li, PAN Yan-yan

(Fujian Communication Technology College,Fuzhou 350007,China)

Abstract:The 0-1knapsack problem is a classic NP problem.In this paper,the 0-1 knapsack problem and its algorithm is analyzd ,the algorithms is based on Dynamic Programming.And carry out that algorithms in the Visual C++.

Key words:0-1 Knapsack;Dynamic Programming

1 0-1背包問題

0-1背包問題是：已知n個(gè)物品的重量及其價(jià)值分別為Wi>0和Pi>0，背包的容量假設(shè)設(shè)為Ci>0，如何選擇哪些物品裝入背包可以使得在背包的容量約束限制之內(nèi)所裝物品的價(jià)值最大？

2 幾種解法的比較

2.1 動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對(duì)于背包問題可以對(duì)子過程用枚舉法求解，而且約束條件越多，決策的搜索范圍越小，求解也越容易。

2.2 回溯法

回溯法需要為問題定義一個(gè)解空間，這個(gè)解空間必須至少包含問題的一個(gè)解（可能是最優(yōu)的）。使用遞歸回溯法解決背包問題的優(yōu)點(diǎn)在于它算法思想簡(jiǎn)單， 而且它能完全遍歷搜索空間，肯定能找到問題的最優(yōu)解；但是由于此問題解的總組合數(shù)有2n個(gè)，因此，隨著物件數(shù) n 的增大，其解的空間將以2n級(jí)增長(zhǎng)，當(dāng) n 大到一定程度上，用此算法解決背包問題將是不現(xiàn)實(shí)的。

2.3 貪心算法

使用貪心方法求解時(shí)計(jì)算的復(fù)雜度降低了很多。貪心算法是一種不要求最優(yōu)解，只希望得到較為滿意解的方法。一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪心方法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不是考慮各種可能的整體情況，所以貪心算法不需要回溯。但是，對(duì)于某些情況，實(shí)際上有解，而該算法不能找到解。

2.4 分枝-限界法

分枝界限是另一種系統(tǒng)地搜索解空間的方法，與回溯法的主要區(qū)別在于對(duì)E節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次會(huì)變成E節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋節(jié)點(diǎn)是，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生產(chǎn)的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入到活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充才結(jié)束。

2.5 遺傳算法

遺傳算法是一類借鑒生物自然選擇和自然遺傳機(jī)制的隨機(jī)化的搜索算法。它適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題。遺傳算法是一種群體型操作，該操作以群體中所有個(gè)體為對(duì)象。選擇、交叉和變異是遺傳算法的三個(gè)主要算子，它們構(gòu)成了遺傳算法的主要操作。使用遺傳算法解決物件數(shù)較大的背包問題，它具有收斂快、搜索速度快的特點(diǎn)。然而在一般情況下，使用基本遺傳算法解決背包問題時(shí)，得到問題的近似解也不能滿足逼近最優(yōu)解的要求。

下面介紹用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)0-1背包問題的求解。

3 動(dòng)態(tài)規(guī)劃算法

3.1 0-1背包問題的描述

3.2 最優(yōu)子結(jié)構(gòu)性質(zhì)

0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)(y1,y2,…,yn)是所給0-1背包問題的一個(gè)最優(yōu)解。則

3.3 遞歸關(guān)系

設(shè)所給0-1背包問題的子問題：

的最優(yōu)解值為m(i.j),即m(i.j)是背包容量為j,可選擇物品為i,i+1,…,n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，就可以建立計(jì)算m(i.j)的遞歸式如下：

4 C++實(shí)現(xiàn)算法

#include

#include

#include

int min(int w,int c)

{int temp;

if (w

else

temp=c;

return temp;}

int max(int w,int c)

{int temp;

if (w>c)temp=w;

else temp=c;

return temp;}

void knapsack(int v[],int w[],int c,int ,int**m)

//求最優(yōu)值

{int jmax=min(w[n]-1,c);

for(int j=0;j

m[n][j]=0;

for(int jj=w[n];jj

m[n][jj]=v[n];

for(int i=n-1;i>1;i--){ //遞歸部分

jmax=min(w[i]-1,c);

for(int j=0;j

m[i][j]=m[i+1][j];

for(int jj=w[i];jj

m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);}

m[1][c]=m[2][c];

if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

cout

for(int l=2;l

for(int j=0;j

{cout

cout

int traceback(int **m,int w[],int c,int n,int x[])

//回代，求最優(yōu)解

{cout

for(int i=1;i

if(m[i][c]==m[i+1][c]) x[i]=0;

else {x[i]=1;

c-=w[i];}

x[n]=(m[n][c])?1:0;

for(int y=1;y

{cout

return x[n];}

void main(){

int n,c;

int**m;

cout

cin>>n>>c;

int *v=new int[n+1];

cout

for(int i=1;i

cin>>v[i];

int *w=new int[n+1];

cout

for(int j=1;j

cin>>w[j];

int *x=new int[n+1];

m=new int*[n+1];//動(dòng)態(tài)的分配二維數(shù)組

for(int p=0;p

m[p]=new int[c+1];}

knapsack(v,w,c,n,m);

traceback(m,w,c,n,x);}

5 測(cè)試

在Visual C++ 下對(duì)該算法進(jìn)行測(cè)試 ：例：背包的容量c＝10，物品個(gè)數(shù)n＝5，w＝{2,2,6,5,4},

v＝{6,3,5,4,6}。

輸出結(jié)果： 1 1 0 0 1

背包的總重量：8

背包的總價(jià)值：15

6 算法分析

上述算法Knapsack需要O (nc)計(jì)算時(shí)間，traceback需要O（n）計(jì)算時(shí)間。采用動(dòng)態(tài)規(guī)劃算法解決0-1背包問題，并通過編程在Visual C++下進(jìn)行測(cè)試得到了較好的結(jié)果，證明了算法的正確性。但是，算法還是有缺陷的，當(dāng)c很大時(shí)，算法需要計(jì)算的時(shí)間較多，還需改進(jìn)。

參考文獻(xiàn)：

[1]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京:電子工業(yè)出版社,2004.

[2]劉玉娟,王相海.0-1背包2問題的兩種擴(kuò)展形式及其解法[J].計(jì)算機(jī)應(yīng)用研究,2006.

[3]楊曉紅.基于Visual C++的0-1背包問題的貪婪算法[J].科技資訊導(dǎo)報(bào),2007.

[4]黃波,蔡之華.0/1背包問題及其解法研究[J].電腦知識(shí)與技術(shù),2007.

篇7

隨著AlphaGo（圍棋人工智能程序）在2016年初擊敗了世界圍棋冠軍后，人工智能技術(shù)的研發(fā)與討論繼續(xù)走向一個(gè)新的高峰，而語(yǔ)音識(shí)別技術(shù)則是其核心內(nèi)容。

本文主要基于語(yǔ)音識(shí)別技術(shù)的語(yǔ)音解碼模塊進(jìn)行討論，從其涉及技術(shù)、設(shè)計(jì)、實(shí)現(xiàn)進(jìn)行全面描述。運(yùn)用解碼器進(jìn)行解碼操作，通過搜索算法在解碼端尋找最優(yōu)詞串，搭建和訓(xùn)練聲學(xué)模型，并提高語(yǔ)音識(shí)別率。本項(xiàng)目基于一個(gè)完整的Android軟件作為依托，但由于篇幅有限，本文重點(diǎn)討論離線語(yǔ)音包、搭建語(yǔ)言模型、以及語(yǔ)音解碼模塊的設(shè)計(jì)過程。

1.項(xiàng)目背景

語(yǔ)音識(shí)別技術(shù)是能夠?qū)⑷说恼Z(yǔ)音信號(hào)轉(zhuǎn)換成機(jī)器可以識(shí)別的指令的一種方法，通過指令來控制機(jī)器的正常運(yùn)轉(zhuǎn)。語(yǔ)音識(shí)別的任務(wù)主要包括：孤立詞識(shí)別、關(guān)鍵詞識(shí)別、連續(xù)語(yǔ)音識(shí)別等。

市面上的離線語(yǔ)音識(shí)別一直不成熟，識(shí)別慢、識(shí)別率低等問題一直被人詬病。本項(xiàng)目離線語(yǔ)音識(shí)別部分是基于Sphinx-4自行訓(xùn)練得到的聲學(xué)模型和語(yǔ)言模型，在小詞匯量識(shí)別方面盡量提高其識(shí)別率。

2.需求分析

一個(gè)成熟的語(yǔ)音識(shí)別系統(tǒng)可以劃分為特征提取、聲學(xué)模型訓(xùn)練、語(yǔ)言模型訓(xùn)練和解碼器四個(gè)重要組成部分；而離線端語(yǔ)音解碼模塊，包括了對(duì)原始語(yǔ)音進(jìn)行信號(hào)處理、特征提取、通過Viterbi動(dòng)態(tài)規(guī)劃算法搜索最優(yōu)結(jié)果、語(yǔ)義分析及輸出文本結(jié)果等步驟。

1、 原始信號(hào)處理：獲取通過麥克風(fēng)按鈕接收到的原始音頻數(shù)據(jù)，過濾非必要信息以及背景噪音對(duì)語(yǔ)音前端點(diǎn)和后端點(diǎn)進(jìn)行截取，對(duì)語(yǔ)音信號(hào)分割成若干個(gè)進(jìn)行分析；

2、 特征提?。焊鶕?jù)sphinxbase語(yǔ)音系統(tǒng)給出的接口，提取出語(yǔ)音信號(hào)的關(guān)鍵特征，并將其生成一個(gè)序列，以供解碼處理時(shí)搜索這個(gè)隱式序列，得出結(jié)果；

3、 算法搜索最優(yōu)序列：根據(jù)Viterbi算法設(shè)計(jì)出計(jì)算序列中出現(xiàn)概率最大的詞串的方法，搜索出每一幀語(yǔ)音信號(hào)的最優(yōu)路徑，輸出結(jié)果；

4、 語(yǔ)義分析及輸出識(shí)別結(jié)果：根據(jù)孤立的關(guān)鍵詞判斷搜索出來的語(yǔ)音結(jié)果屬于哪一個(gè)應(yīng)用場(chǎng)景，如“打電話”、“發(fā)短信”、“上一頻道”、“下一頻道”等等孤立詞；

離線語(yǔ)音解碼模塊流程如下圖2-1所示：

3.系統(tǒng)設(shè)計(jì)

3.1.特征提取

特征提取的主要目的是減少語(yǔ)音噪聲靜音等無用的雜訊，獲取必要的訊號(hào)數(shù)據(jù)，將數(shù)據(jù)轉(zhuǎn)換成電腦可以識(shí)別的數(shù)字信號(hào)，以便作識(shí)別和語(yǔ)義分析。

本語(yǔ)音識(shí)別技術(shù)模塊基于Sphinx4語(yǔ)音識(shí)別系統(tǒng)進(jìn)行開發(fā)的，其中聲音的預(yù)處理是利用MATLAB這一便于算法開發(fā)的軟件來實(shí)現(xiàn)對(duì)語(yǔ)音信號(hào)進(jìn)行數(shù)字處理與分析，也可稱為特征處理。其包括對(duì)原語(yǔ)音信號(hào)進(jìn)行預(yù)加重處理，然后需要進(jìn)行分幀和加窗、采樣和量化、端點(diǎn)檢測(cè)等。

其中，包括：預(yù)加重處理、分幀、量化處理以及語(yǔ)音端點(diǎn)檢測(cè)等過程。如下3-1所示：

3.2. 基于動(dòng)態(tài)規(guī)劃的Viterbi算法

動(dòng)態(tài)規(guī)劃算法的基本思想是將問題分解成若干個(gè)子問題，求解子問題，最后從子問題的解中得到原問題的解。通常利用動(dòng)態(tài)規(guī)劃算法解決問題的步驟是先找出最優(yōu)解的性質(zhì)，刻畫最優(yōu)解的結(jié)構(gòu)特征，然后遞歸定義出最優(yōu)解，用自底向上的方法計(jì)算出最優(yōu)路徑，最后根據(jù)計(jì)算出來的最優(yōu)值信息，構(gòu)造最優(yōu)解。圖下圖3-2所示：

因此，基于動(dòng)態(tài)規(guī)劃的Viterbi算法的整體設(shè)計(jì)思路如下：

1、 對(duì)于每一個(gè)語(yǔ)音狀態(tài)要設(shè)置一個(gè)三元組作為記錄：（prob，v_path，v_prob），這里聲明的prob是從最初狀態(tài)的到當(dāng)前狀態(tài)的所有路徑的出現(xiàn)概率相加的結(jié)果，其中最優(yōu)的路徑為viterbi路徑，v_path代表的就是viterbi路徑，而v_prob代表的則是此路徑出現(xiàn)的概率；

2、 算法開始后，初始化一個(gè)Map集合，把每一種語(yǔ)音狀態(tài)都映射進(jìn)三元組中

3、 設(shè)置三重for循環(huán)，計(jì)算從當(dāng)前語(yǔ)音狀態(tài)到下一階段的過渡概率會(huì)出現(xiàn)什么變化，所有下一狀態(tài)判斷完之后，從集合中遍歷找出最優(yōu)結(jié)果，即出現(xiàn)概率最大的路徑；

4、 保留每一幀語(yǔ)音在某個(gè)狀態(tài)的最優(yōu)路徑，輸出結(jié)果。

4.總結(jié)

語(yǔ)音識(shí)別技術(shù)的核心是HMM技術(shù)（隱式馬爾科夫模型），而本文主要基于語(yǔ)音識(shí)別技術(shù)的語(yǔ)音解碼模塊進(jìn)行討論，從其涉及技術(shù)、設(shè)計(jì)、實(shí)現(xiàn)進(jìn)行全面描述，對(duì)離線解碼模塊中的特征提取、以及使用動(dòng)態(tài)規(guī)劃的Viterbi算法實(shí)現(xiàn)搜索最優(yōu)序列進(jìn)行了詳細(xì)介紹。模塊基本實(shí)現(xiàn)完成，但仍有很多值得提升和完善空間，今后可以使用更先進(jìn)的算法進(jìn)行優(yōu)化。

參考文獻(xiàn)

[1] 朱元濤.Android應(yīng)用開發(fā)范例大全[M]. 清華大學(xué)出版社.2015.

[2] 郭霖. 第一行代碼 Android [M]. 人民郵電出版社. 2014.

[3] 何紅輝，關(guān)愛民.Android 源碼設(shè)計(jì)模式解析與實(shí)戰(zhàn) [M]. 人民郵電出版社. 2015.

[4] Android Studio Applicati [M]. 進(jìn)口原版圖書.

[5] The Definitive Guide to Sqlite [M]. Apress.

[6] 李興華.Android開發(fā)實(shí)戰(zhàn)經(jīng)典[M].清華大學(xué)出版社.2012.

[7] Android開發(fā)實(shí)戰(zhàn)[M].清華大學(xué)出版社.2013.

[8] 趙卓君.Java語(yǔ)言程序設(shè)計(jì)高級(jí)教程[M].北京.清華大學(xué)出版社.2010.

[9] 朱少民.軟件測(cè)試方法和技術(shù)（第2版）[M].北京.清華大學(xué)出版社.2010.

[10] UML和模式應(yīng)用[M].機(jī)械工業(yè)出版社.2006.

篇8

關(guān)鍵詞：市政給排水；管道設(shè)計(jì)；優(yōu)化設(shè)計(jì)

引言

城市普遍存在水質(zhì)污染的問題，致使城市水環(huán)境遭受到嚴(yán)重破壞，水質(zhì)型缺水的區(qū)域不斷擴(kuò)大，水資源供需失衡，這一問題已對(duì)城市中居民的生活，健康及城市現(xiàn)代化進(jìn)程構(gòu)成了危害，嚴(yán)重威脅到城市的水系統(tǒng)以及城市的可持續(xù)發(fā)展。隨著城市化進(jìn)程的發(fā)展，城市市政自來水給排水工程是城市舉出設(shè)施的重要組成部分之一，如何降低市政自來水管道減少爆管漏水等問題帶來的水資源的浪費(fèi)，有效提高城市自來水供排水管道的效率和輸水能力，為城市居民日常生活和城市建設(shè)提供經(jīng)濟(jì)實(shí)惠、安全可靠的水資源保障，如何改善市政自來水給排水管道的設(shè)計(jì)是必要的。

1.市政給排水工程的結(jié)構(gòu)設(shè)計(jì)

1.1市政給排水工程的結(jié)構(gòu)設(shè)計(jì)

在市政給排水工程中，根據(jù)工程的埋設(shè)深度。工程管道規(guī)格、材質(zhì)以及地下水位和試驗(yàn)壓力等綜合指標(biāo)，對(duì)管道的強(qiáng)度和剛度進(jìn)行計(jì)算及復(fù)核，提供給排水的管道等級(jí)、壁厚以及結(jié)構(gòu)配筋圖。通常采用的加固措施有混凝土、管廊包管等，對(duì)于一些必須要滿足剛度和強(qiáng)度要求的管道應(yīng)該及時(shí)采取加固方法來進(jìn)行加固，而且在施工過程中根據(jù)計(jì)算采用具體的加強(qiáng)加固措施，加固的具體方法和方式應(yīng)根據(jù)經(jīng)濟(jì)指標(biāo)和實(shí)際情況來確定。

1.2市政給排水工程的結(jié)構(gòu)形式

在市政給排水工程中，排水專業(yè)確定管道的結(jié)構(gòu)形式，一般來說，結(jié)構(gòu)專業(yè)應(yīng)根據(jù)管道的工作環(huán)境。結(jié)構(gòu)用途以及水文地質(zhì)情況等經(jīng)濟(jì)指標(biāo)等從專業(yè)角度提出參考意見。特殊地段以及特殊情況的非承壓管也采用鋼管等形式當(dāng)污水管道；而對(duì)于口徑較大時(shí)應(yīng)采用現(xiàn)澆鋼筋混凝土箱涵，或采用盾構(gòu)結(jié)構(gòu)形式。

2.市政給排水管道對(duì)于城市的意義

在市政基礎(chǔ)設(shè)施建設(shè)和完善中，給排水管道的鋪設(shè)和維修護(hù)養(yǎng)對(duì)城市有著極其重要的影響。給水管道關(guān)系整個(gè)城市的生活和工業(yè)用水的供給，而排水管道則關(guān)系城市污水的排出和雨水等可能造成市內(nèi)積水的多余水量及時(shí)排空。在這樣一種背景下，市政給排水工程的完善程度和施工質(zhì)量對(duì)城市居民生活將會(huì)產(chǎn)生重要的影響。

另外，市政管道的鋪設(shè)有些是在城市生活區(qū)和工業(yè)區(qū)劃定建成后或者建設(shè)過程中開始施工，在不破壞原有市政建筑的前提下完成新的給排水管道的鋪設(shè)，便對(duì)施工技術(shù)提出了一定的要求。同時(shí)，給排水工程質(zhì)量的要求也必然要求我們加強(qiáng)對(duì)施工技術(shù)的嚴(yán)格控制。只有在高質(zhì)量標(biāo)準(zhǔn)要求下完成的工程才能減少使用過程中的一些問題，從而減少給排水工程維修護(hù)養(yǎng)的經(jīng)濟(jì)成本。

3.市政排水管網(wǎng)優(yōu)化設(shè)計(jì)

3.1管線的平面優(yōu)化布置

排水管網(wǎng)的布置原則是既要使工程量最小，又要使水流暢通、節(jié)省能量。正確的定線是合理經(jīng)濟(jì)的設(shè)計(jì)管網(wǎng)的先決條件。定線的基本原則是：干管支管的設(shè)計(jì)盡量采用直線布局，不要拐彎；定線應(yīng)盡量利用地勢(shì)，使污水在重力作用下流入污水廠；設(shè)計(jì)時(shí)應(yīng)盡量減少管道埋深；在管道的中途盡量減少提升泵站的設(shè)置。在早期的研究中，設(shè)計(jì)方法為假定每一段管徑相同，以挖方費(fèi)用為優(yōu)選依據(jù)，選擇一初始布置方案，然后通過算法逐步進(jìn)行調(diào)整。后來又引入了排水線的概念，將排水區(qū)域內(nèi)與最終出水口節(jié)點(diǎn)相距同樣可行管數(shù)的節(jié)點(diǎn)用一根排水線連接起來。這樣把問題轉(zhuǎn)化為最短路問題，可用動(dòng)態(tài)規(guī)劃法求解。但此方法把尋優(yōu)的范圍被限制，使人們?cè)谠O(shè)計(jì)過程中很容易把最優(yōu)方案排除。后來，人們把城市排水系統(tǒng)排水布置抽象為由點(diǎn)和線構(gòu)成的決策圖，從圖論中尋找方法。1986年發(fā)展到利用三種權(quán)值來解決問題。三種權(quán)值是各管段地面坡度的倒數(shù)；各管段的管長(zhǎng)；各管段在滿足最小覆土條件下，按最小坡度設(shè)計(jì)時(shí)的挖方量。分別對(duì)這三種權(quán)值運(yùn)用最短路生成樹算法求管線平面布置方案，再進(jìn)行管徑、埋深和提升泵站的優(yōu)化設(shè)計(jì)，最后取投資費(fèi)用最小的平面布置方案作為最優(yōu)設(shè)計(jì)方案。

3.2已定平面布置下的管道系統(tǒng)優(yōu)化設(shè)計(jì)

排水管道優(yōu)化設(shè)計(jì)主要是指：對(duì)于某一設(shè)計(jì)管段，當(dāng)設(shè)計(jì)流量確定后，在滿足設(shè)計(jì)規(guī)范要求的管徑和坡度的多種組合中，取得管材費(fèi)用與敷設(shè)費(fèi)用的平衡。在排水管線平面布置已定情況下，對(duì)于管段管徑，埋深的優(yōu)化設(shè)計(jì)，國(guó)內(nèi)外做了大量研究工作。

（1）線性規(guī)劃法和非線性規(guī)劃法。a線性規(guī)劃法，是針對(duì)排水管網(wǎng)設(shè)計(jì)計(jì)算中的約束條件和目標(biāo)函數(shù)的非線性，分別用其一級(jí)泰勒公式展開式代替，用線性規(guī)劃的解作為問題的近似解，反復(fù)迭代，使迭代序列逼近非線性規(guī)劃的最優(yōu)解。缺點(diǎn)是把管徑當(dāng)作連續(xù)變量來處理，存在計(jì)算管徑與市售管徑不一致的矛盾，且前期準(zhǔn)備工作量大，以后發(fā)展的整數(shù)規(guī)劃法，雖然在一定程度上解決了線性規(guī)劃的缺點(diǎn)，但是其整型變量比較多，難以求解。b非線性規(guī)劃法適應(yīng)了計(jì)算模型中目標(biāo)函數(shù)和變量的非線性特征，可以優(yōu)化選擇管道的直徑和埋深，但極大限制了目標(biāo)函數(shù)和約束條件的形式。

（2）動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃法是目前國(guó)內(nèi)外比較常用的一種方法，基本思想是把排水管道設(shè)計(jì)看作一個(gè)多階段的過程，通過對(duì)設(shè)計(jì)過程進(jìn)行階段劃分來對(duì)管道進(jìn)行優(yōu)化設(shè)計(jì)。其應(yīng)用主要分為兩方面。a以節(jié)點(diǎn)埋深為狀態(tài)變量，通過坡度決策進(jìn)行全方位搜索。其優(yōu)點(diǎn)是直接采用標(biāo)準(zhǔn)管徑，結(jié)果與初始管徑無關(guān)，且能控制計(jì)算深度，但要求狀態(tài)點(diǎn)之間的埋深間隔很小，使存儲(chǔ)量和時(shí)間間隔大為增加。因此在此基礎(chǔ)上引入了擬差動(dòng)態(tài)規(guī)劃法，在動(dòng)態(tài)規(guī)劃法的基礎(chǔ)上引入了縮小范圍的迭代過程，但應(yīng)用有一定的局限性。b以管徑為狀態(tài)變量，通過流速和充滿度決策。由于可使用的標(biāo)準(zhǔn)管徑數(shù)目有限，因此在計(jì)算速度和存儲(chǔ)量上都有很大優(yōu)勢(shì)。以后又發(fā)展出了可行管徑法。此法使優(yōu)化計(jì)算精度得以提高，并顯著減少了計(jì)算工作量和計(jì)算機(jī)存儲(chǔ)量。盡管動(dòng)態(tài)規(guī)劃法是解決多階段決策問題的一種有效方法，但在排水管道系統(tǒng)設(shè)計(jì)計(jì)算時(shí)，前一段的設(shè)計(jì)結(jié)果將直接影響到后續(xù)管段設(shè)計(jì)參數(shù)的選用，因此利用動(dòng)態(tài)規(guī)劃法求出的污水管道優(yōu)化設(shè)計(jì)方案也并不一定是真正的最優(yōu)方案。

（3）直接優(yōu)化法。直接優(yōu)化法是直接對(duì)各種方案或可調(diào)參數(shù)的選擇設(shè)計(jì)計(jì)算和比較來得到最優(yōu)解，具有直觀和容易驗(yàn)證的優(yōu)點(diǎn)。主要方法有：a電子表格法是一種啟發(fā)式的費(fèi)用估算方法，允許用戶尋找最小費(fèi)用設(shè)計(jì)，能得出比動(dòng)態(tài)規(guī)劃法要好的結(jié)果而且更符合設(shè)計(jì)規(guī)范的要求。b兩相優(yōu)化法是設(shè)計(jì)流量確定后，在滿足約束條件的前提下，選取最經(jīng)濟(jì)流速和最大充滿度進(jìn)而得到最優(yōu)管徑和最小坡度，最大限度地降低管道埋深.直接優(yōu)化法的算法與人工算法基本相同，但受設(shè)計(jì)人員的能力所限，所得結(jié)果不盡相同，所以所求結(jié)果不一定是最優(yōu)解。

（4）遺傳算法。遺傳算法是進(jìn)化算法一個(gè)分支，是模擬生物學(xué)中的自然遺傳變異機(jī)制而提出的隨機(jī)優(yōu)化算法。遺傳算法在解決中小型管道系統(tǒng)優(yōu)化設(shè)計(jì)問題時(shí)可以求得最優(yōu)設(shè)計(jì)方案。但解決大型管道系統(tǒng)問題時(shí)，只能求得趨近于最優(yōu)解的設(shè)計(jì)方案，在排水管道系統(tǒng)優(yōu)化設(shè)計(jì)中，不論采用何種方法，都以設(shè)計(jì)規(guī)范為基本要求，同時(shí)使費(fèi)用達(dá)到最小。

4.結(jié)束語(yǔ)

在整個(gè)市政基礎(chǔ)建設(shè)工作中，各專業(yè)一環(huán)扣一環(huán)，最重要的是市政排水管道工程是隱蔽工程，維修起來比較麻煩，有的甚至是無法維修，并且維修費(fèi)用較大，因此，在設(shè)計(jì)施工過程中，必須有效避免這些常見問題，加強(qiáng)對(duì)排水管道工程的質(zhì)量控制，消除工程質(zhì)量缺陷，切實(shí)保障人民的利益。

參考文獻(xiàn)：

[1]韋從勝，蔣全華.市政給排水管道設(shè)計(jì)[J].技術(shù)與市場(chǎng)，2011，（7）.

篇9

關(guān)鍵詞：0-1背包；回溯

中圖分號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）36-0076-02

The B_tracking Algorithm of 0-1 Knapsack Problem Based on C#

CHEN Zi-li

（Fujian Chuanzheng Communications College， Fuzhou 350007， China）

Abstract： The 0-1knapsack problem is a classic NP problem. In this paper， the 0-1 knapsack problem and its algorithm is analyzed， the algorithms is based on B_tracking algorithm. And carry out the algorithms in the C#.

Key words： 0-1 Knapsack； b_tracking algorithm

1 0-1背包思想

0-1背包問題的思想：如果n個(gè)物品的重量和價(jià)值分別為[wi>0]和[pi>0]，背包的大小設(shè)置成[ci>0]，應(yīng)該怎樣往背包中放置物品可以達(dá)到最大值或者最佳裝載方式？[5]

在實(shí)際進(jìn)行裝包操作時(shí)，規(guī)定每種物品只能載入一次，而且每種物品只能執(zhí)行載入或者不載入操作，則把該問題叫做0-1背包問題。

給定[wi]>0，c>0，[vi]>0，[1≤i≤n]，尋求一個(gè)n元0-1向量[（x1，x2，...，xn），xi∈{0，1}，][1≤i≤n]，使得[i=1nwixi≤c]，而且[i=1nvixi]是最值。

[maxi=1nvixi] [i=1nwixi≤cxi∈{0.1}，1≤i≤n]

2 幾種解法的比較

2.1 回溯法

回溯法就是為問題聲明一個(gè)解集合，這個(gè)集合存在一個(gè)可能是最優(yōu)的解。遞歸回溯法算法思想非常簡(jiǎn)單，能夠?qū)λ阉骺臻g進(jìn)行遍歷，必然可以找到背包問題的最優(yōu)解，缺點(diǎn)是背包問題解集合將隨著物品數(shù)量n的變大以2的幾何級(jí)數(shù)增長(zhǎng)，當(dāng)n大到一定程度上，要遍歷搜索空間需耗費(fèi)大量的時(shí)間和資源，因此當(dāng)物件數(shù)過多的時(shí)候，就很難依靠回溯法來求解。

2.2 動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃指的是把復(fù)雜的多階段問題分解成相對(duì)簡(jiǎn)單的單階段問題。對(duì)于背包問題可以用窮舉法對(duì)子過程進(jìn)行求解，并且決策的搜索范圍會(huì)因?yàn)闂l件的增多而變小，這樣求解也更簡(jiǎn)單。

2.3 貪心算法

貪心方法的使用可以降低求解時(shí)計(jì)算的復(fù)雜度。貪心算法不是片面追求最優(yōu)解，因此不理會(huì)所有情況，所以不象回溯法那樣進(jìn)行遍歷，一般情況下，就以目前情形最為最優(yōu)的 。

2.4 分枝限界法

分枝界限與回溯法拓展E節(jié)點(diǎn)的方法不一樣，為另一種全面地遍歷解集合的方法，按這種算法，任何活節(jié)點(diǎn)只可能一次改變?yōu)镋節(jié)點(diǎn)。當(dāng)某節(jié)點(diǎn)一旦改變成E節(jié)點(diǎn)，會(huì)同時(shí)產(chǎn)生一些新節(jié)點(diǎn)（也就是分枝），新產(chǎn)生的節(jié)點(diǎn)是從原節(jié)點(diǎn)跳轉(zhuǎn)一步實(shí)現(xiàn)的。產(chǎn)生的新節(jié)點(diǎn)里，只留下有希望得到行得通解的節(jié)點(diǎn)，添加到活節(jié)點(diǎn)表，剩下的拋棄。接著從活節(jié)點(diǎn)表里挑選節(jié)點(diǎn)再進(jìn)行拓展，最后就可以得到最后解，并且活動(dòng)表清空了。

3 回溯算法

回溯法為一種在問題的結(jié)果空間樹T上查詢問題答案的算法。回溯法在全部解的結(jié)果空間樹中，依照深度優(yōu)先的方法，從根節(jié)點(diǎn)開始查詢結(jié)果空間樹。算法搜索至結(jié)果空間樹的每個(gè)節(jié)點(diǎn)時(shí)，先看看是不是不存在結(jié)果。假設(shè)確定不存在，那么忽略該子樹，繼續(xù)向其父節(jié)點(diǎn)進(jìn)行回溯，反之，使用該子樹，仍然以深度優(yōu)先的方法進(jìn)行查詢。當(dāng)回溯法來尋找結(jié)果時(shí)，一定要回溯到頂點(diǎn)，并且，頂點(diǎn)節(jié)點(diǎn)的全部子樹都查找完才停止。這樣，按照深度優(yōu)先的策略全面查詢問題的結(jié)果的算法叫做回溯法，可以解決組合數(shù)很多的情況。

假設(shè)選取回溯法來解決0-1背包問題，可以用在采取子集數(shù)表示0-1背包問題的結(jié)果集合。執(zhí)行查找結(jié)果空間樹時(shí)，如果左節(jié)點(diǎn)是能用的節(jié)點(diǎn)，查找行為轉(zhuǎn)到它的左子樹。那什么時(shí)候進(jìn)入右邊的子樹查找呢？那就是只有在右邊子樹里有希望找找最優(yōu)解的時(shí)候，才轉(zhuǎn)到右邊子樹查詢。要不然就把右子樹刪除。此過程由上界函數(shù)來完成。假定r是現(xiàn)在還沒有使用的剩下物品總價(jià)值，cp是現(xiàn)在已有的價(jià)值，yestp為目前最優(yōu)的價(jià)值。那么在cp+r

要使上界函數(shù)的計(jì)算更方便，不妨讓物品按照重量?jī)r(jià)值進(jìn)行降序排序。執(zhí)行的時(shí)候，由函數(shù)fanwei來尋找最新節(jié)點(diǎn)的上界。只有在要進(jìn)入右邊子樹時(shí)，才計(jì)算上界函數(shù)fanwei，由此判斷是不是要將右子樹刪除。轉(zhuǎn)到左子樹時(shí)不要查找上界，這時(shí)候上界和基類節(jié)點(diǎn)的上界是一樣的。

4 算法實(shí)現(xiàn)

int n；//物品數(shù)量

double c；//背包容量

double[] v=new double[100]；//各個(gè)物品的價(jià)值

double[] w=new double[100]；//各個(gè)物品的重量

double cw = 0.0；//當(dāng)前背包重量

double cp = 0.0；//當(dāng)前背包中物品價(jià)值

double yestp = 0.0；//當(dāng)前最優(yōu)價(jià)值

double[] perp=new double[100]；//單位物品價(jià)值排序后

int[] order=new int[100]；//物品編號(hào)

int[] put= new int[100]；//設(shè)置是否裝入

//按單位價(jià)值排序

public void knapsack（）

{ int i，j；

int temporder = 0；

double temp = 0.0；

for（i=1；i

perp[i]=v[i]/w[i]；

for（i=1；i

{ for（j=i+1；j

if（perp[i]

{temp = perp[i]；

perp[i]=perp[i]；

perp[j]=temp；

temporder=order[i]；

order[i]=order[j]；

order[j]=temporder；

temp = v[i]；

v[i]=v[j]；

v[j]=temp；

temp=w[i]；

w[i]=w[j]；

w[j]=temp； }}}

//回溯函

public void b_track（int i）

{ double fanwei（int i）；

if（i>n）

{ yestp = cp；

return； }

if（cw+w[i]

{ cw=cw+w[i]；

cp= cp+v[i]；

put[i]=1；

b_track（i+1）；

cw=cw-w[i]；

cp=cp-v[i]； }

if（fanwei（i+1）>yestp）//符合條件搜索右子數(shù)

b_track（i+1）； }

//計(jì)算上界函數(shù)

public double fanwei（int i）

{double leftw= c-cw；

double b = cp；

while（i

{ leftw-=w[i]；

b+=v[i]；

i++；}

if（i

b+=v[i]/w[i]*leftw；

return b； }

static void Main（string[] args）

{int i；

Console.WriteLine（"請(qǐng)輸入物品的數(shù)量和容量："）；

n=Convert.ToInt32（Console.ReadLine（））；

c= Convert.ToDouble（Console.ReadLine（））；

Console.WriteLine （"請(qǐng)輸入物品的重量和價(jià)值："）；

for（i=1；i

{ Console.WriteLine （"第{0}個(gè)物品的重量："，i）；

w[i]=Convert.ToDouble（Console.ReadLine（））；

Console.WriteLine （"價(jià)值是："）；

v[i]=Convert.ToDouble（Console.ReadLine（））；

order[i]=i； }

knapsack（）；

b_track（1）；

Console.WriteLine （"最有價(jià)值為："+yestp）；

Console.WriteLine （"需要裝入的物品編號(hào)是："）；

for（i=1；i

{if（put[i]==1）

printf（"%d "，order[i]）； }

return 0； }

5 測(cè)試

在VS2010下對(duì)該算法進(jìn)行測(cè)試 ，例如背包的最大容量c=10，要放入的物品個(gè)數(shù)n=5，重量w={2，6，2，5，4}，價(jià)值v={5，6，3，4，6}。

輸出結(jié)果： 1 0 1 0 1

背包的總價(jià)值：15

背包的總重量：8

6 算法分析

因?yàn)閷ふ疑辖绾瘮?shù)fanwei需要O（n）時(shí)間，當(dāng)復(fù)雜度最壞時(shí)有O（2n）個(gè)右邊派生節(jié)點(diǎn)需要求解上界函數(shù)，因此，用回溯法來計(jì)算0-1背包問題的時(shí)間復(fù)雜度是O（n2n）?；厮莘艿玫?-1背包的最優(yōu)解。另一方面回溯法是以樹當(dāng)成基礎(chǔ)的算法，所以其空間開銷很多。

參考文獻(xiàn)：

[1] 王曉東. 計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京： 電子工業(yè)出版社，2004.

[2] 賀毅朝， 田海燕. 基于動(dòng)態(tài)規(guī)劃法求解動(dòng)態(tài)0-1背包問題[J].計(jì)算機(jī)科學(xué)，2012 ，39（7）：237-241..

[3] 徐穎. 回溯法在0-1背包問題中的應(yīng)用[J].軟件導(dǎo)刊，2008（12）.

篇10

關(guān)鍵詞：運(yùn)籌學(xué)；規(guī)劃論；EXCEL軟件

中圖分類號(hào)G642.4 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2014）10-0278-03

一、引言

運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，可以為決策者選擇最優(yōu)決策提供定量依據(jù)。運(yùn)籌學(xué)經(jīng)過多年的發(fā)展已經(jīng)成為體系，包括規(guī)劃論（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃和非線性規(guī)劃）、圖論與網(wǎng)絡(luò)、排隊(duì)論、存儲(chǔ)論、對(duì)策論和決策論等[1]。傳統(tǒng)的運(yùn)籌學(xué)主要是以講授理論為主，尤其是比較枯燥的數(shù)學(xué)理論。近年來，運(yùn)籌學(xué)改革不斷提高其應(yīng)用性，減少枯燥的理論。此外，隨著運(yùn)籌學(xué)計(jì)算機(jī)支撐技術(shù)的迅速發(fā)展，運(yùn)籌學(xué)應(yīng)用得到極大的推動(dòng)，運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)提上日程，因此開設(shè)運(yùn)籌學(xué)的實(shí)驗(yàn)課程勢(shì)在必行。秦必瑜[2]和石磊[3]在運(yùn)籌學(xué)的課程改革中都提出要增加軟件應(yīng)用。我院運(yùn)籌學(xué)教學(xué)團(tuán)隊(duì)多年致力于運(yùn)籌學(xué)的教改研究，在提出應(yīng)用軟件的基礎(chǔ)上，進(jìn)一步開設(shè)了除理論課程外的專門實(shí)踐課程，將理論課上學(xué)習(xí)到的內(nèi)容使用軟件來進(jìn)行求解。

國(guó)內(nèi)運(yùn)籌學(xué)的實(shí)驗(yàn)教學(xué)已經(jīng)有很大進(jìn)展，目前運(yùn)籌學(xué)經(jīng)常使用的軟件主要有l(wèi)ingo[4][5]、WinQSB[6]、MATLAB[7]等。近年來，美國(guó)高校運(yùn)籌學(xué)（管理科學(xué)）的思想、內(nèi)容、方法和手段發(fā)生根本轉(zhuǎn)變，開始使用“電子表格”這一全新的教學(xué)方法。在運(yùn)籌學(xué)中使用EXCEL已經(jīng)成為運(yùn)籌學(xué)教學(xué)的一個(gè)新潮流。EXCEL軟件使用方便，不需要重新安裝和學(xué)習(xí)新軟件的使用方法，一般的PC機(jī)上都安裝有EXCEL軟件，因此使用方便、應(yīng)用廣泛。但是目前將EXCEL在運(yùn)籌學(xué)中的應(yīng)用并不多，李雪虎[8]給出用EXCEL求解運(yùn)輸問題和網(wǎng)絡(luò)最優(yōu)化問題的例子；魏杰羽[9]闡述了用EXCEl求解運(yùn)輸問題的過程；而張輝[10]給出了使用EXCEL求解線性規(guī)劃問題的例子。在運(yùn)籌學(xué)的體系中，內(nèi)容遠(yuǎn)遠(yuǎn)不止這些，即使規(guī)劃論的內(nèi)容也不止這些。本文中探討將EXCEL應(yīng)用于運(yùn)籌學(xué)規(guī)劃論的內(nèi)容中。運(yùn)籌學(xué)規(guī)劃論包括線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃和非線性規(guī)劃，由于非線性規(guī)劃一般不屬于本科教學(xué)的范圍，因此這里主要用EXCEL求解線性規(guī)劃、目標(biāo)規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃模型，其中每個(gè)部分的模型均來自清華大學(xué)編寫的運(yùn)籌學(xué)教材[1]，此為我院教學(xué)的教材。本文使用EXCEL求解教材中的案例，進(jìn)行應(yīng)用分析。

二、EXCEL在規(guī)劃論教學(xué)中的應(yīng)用

（一）使用EXCEL求解線性規(guī)劃模型

Maxz=2x11+3x12

對(duì)于如下線性規(guī)劃問題，模型1

s.t.x1+2x2≤84x1≤164x2≤16x1，x2≥0

采用EXCEL求解該問題包括以下步驟：

第一步：模型輸入

1.在EXCEL表格中輸入數(shù)據(jù)，輸入目標(biāo)函數(shù)的系數(shù)和約束條件的系數(shù)

2.標(biāo)識(shí)數(shù)據(jù)，可以用不同顏色標(biāo)識(shí)不同類型的數(shù)據(jù)

3.計(jì)算中間數(shù)據(jù)，數(shù)據(jù)、公式分離，顯示出完整模型

第二步：模型求解

1.安裝“規(guī)劃求解”工具。在“工具”中選擇“加載宏”，選中“規(guī)劃求解”，確定后，工具菜單中可顯示“規(guī)劃求解”選項(xiàng)，選擇工具-規(guī)劃求解。

2.設(shè)置參數(shù)，選擇目標(biāo)，輸入約束條件；選擇選項(xiàng)中的“使用線性函數(shù)”和“假定非負(fù)”，點(diǎn)擊求解（見下圖）。

根據(jù)以上求解結(jié)果，可以知道兩個(gè)決策變量的取值分別為4和2，目標(biāo)值最優(yōu)為14。

3.求解出結(jié)果后，選中“敏感性報(bào)告”，點(diǎn)擊確定。得到線性規(guī)劃的求解結(jié)果以及敏感性報(bào)告，可以在此基礎(chǔ)上進(jìn)行靈敏度分析，可與理論教學(xué)中的靈敏度分析進(jìn)行對(duì)比，將理論教學(xué)與實(shí)踐教學(xué)相結(jié)合。

根據(jù)上面的敏感性報(bào)告可以知道，此問題所需要的三種資源的影子價(jià)格分別是1.5，0.125和0，根據(jù)這個(gè)結(jié)果可知當(dāng)最優(yōu)情況下，第一和第二種資源已經(jīng)全部用光。

運(yùn)輸問題是線性規(guī)劃的一種特殊情況，因此用EXCEL求解運(yùn)輸問題的模型和過程是完全相同的，在此不做贅述。

（二）使用EXCEL求解整數(shù)規(guī)劃模型

這里的整數(shù)規(guī)劃其實(shí)指的都是整數(shù)線性規(guī)劃，該模型與線性規(guī)劃模型唯一的區(qū)別就是增加了整數(shù)約束，在求解過程中與線性規(guī)劃模型的區(qū)別就在于約束條件上。比如模型1中，如果要求所有的變量均為整數(shù)，則在EXCEL中做如下設(shè)置：

（三）使用EXCEL求解目標(biāo)規(guī)劃模型

這里的目標(biāo)規(guī)劃主要是指線性目標(biāo)規(guī)劃，即其每個(gè)目標(biāo)都是線性的，其所有約束也是線性的。線性目標(biāo)規(guī)劃的求解可以認(rèn)為是一般線性規(guī)劃的延伸，但是卻與一般線性規(guī)劃有很大區(qū)別。目標(biāo)規(guī)劃中的約束條件有優(yōu)先順序，而且不一定能夠同時(shí)滿足所有的目標(biāo)，因此其求解過程需要考慮優(yōu)先級(jí)，首先考慮第一優(yōu)先級(jí)的偏差最小化作為目標(biāo)函數(shù)，求出最優(yōu)解。在第二步的時(shí)候?qū)⒌诙?yōu)先級(jí)的偏差最小化作為目標(biāo)函數(shù)，并將第一目標(biāo)的最優(yōu)偏差作為約束條件放到第二步的模型中，以此類推直到最后一個(gè)目標(biāo)。下面以模型2為例進(jìn)行說明：

min P■d■■+P■d■■+P■（2d■■+d■■）

模型2

s.t.x1+x2+d■■+d■■=40x1+x2+d■■-d■■=50x1+d■■-d■■=24x2+d■■-d■■=30x1，x2，d■■，d■■≥0，i=1，L 4

在EXCEL求解過程中，首先求解第一優(yōu)先級(jí)，以第一優(yōu)先級(jí)作為目標(biāo)，形成模型

min p1d■■

s.t.x1+x2+d■■+d■■=40x1+x2+d■■-d■■=50x1+d■■-d■■=24x2+d■■-d■■=30x1，x2，d■■，d■■≥0，i=1，L 4

這是一個(gè)典型的線性規(guī)劃問題，可用EXCEL求解，基本模型如下圖：

第一優(yōu)先級(jí)可以獲得最優(yōu)，在此基礎(chǔ)上求第二優(yōu)先級(jí)，第二優(yōu)先級(jí)的模型是在原模型基礎(chǔ)上，將目標(biāo)函數(shù)變化為第二優(yōu)先級(jí)，并且將第一優(yōu)先級(jí)的結(jié)果作為第二優(yōu)先級(jí)計(jì)算的約束條件。

min p2d■■

s.t.x1+x2+d■■-d■■=40x1+x2+d■■-d■■=50x1+d■■-d■■=24x2+d■■-d■■=30d■■=0x1，x2，d■■，d■■≥0，i=1，L 4

使用EXDEL求解的過程如圖所示：

以此類推，可以求得目標(biāo)規(guī)劃的滿意解。

三、結(jié)論

該文介紹了如何使用EXCEL軟件求解線性規(guī)劃、目標(biāo)規(guī)劃、整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃，而運(yùn)籌學(xué)中的內(nèi)容不止這些，因此下一步工作是要將EXCEL用于求解運(yùn)籌學(xué)中除了規(guī)劃論外的其他模型。

參考文獻(xiàn)：

[1]運(yùn)籌學(xué)教材編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2005.

[2]秦必瑜，付海燕.管理類專業(yè)運(yùn)籌學(xué)課程教學(xué)改革研究[J].中國(guó)林業(yè)教育，2010，28（3）：57-59.

[3]石磊，蔡定教.關(guān)于運(yùn)籌學(xué)課程教學(xué)改革的幾點(diǎn)思考[J].廣西教育學(xué)院學(xué)報(bào)，2010，（2）：108-110.

[4]梁桂航，王健，李棟，趙萬勝，林紅旗.Lingo軟件在物流工程運(yùn)籌學(xué)教學(xué)過程中的應(yīng)用[J].物流技術(shù)，2010，（12）：226-228.

[5]萬義國(guó)，游小青.優(yōu)化建模軟件LINGO在運(yùn)籌學(xué)中的應(yīng)用[J].山西建筑，2007，33（15）：367-368.

[6]許巖.淺談《管理運(yùn)籌學(xué)》課程教學(xué)中WINQSB軟件的應(yīng)用[J].現(xiàn)代計(jì)算機(jī)，2013，（3）0：28-31.

[7]張明，王文文.Matlab在經(jīng)管類運(yùn)籌學(xué)教學(xué)中的探索與實(shí)踐[J].大學(xué)教育，2012，（7）：81-89.

[8]李雪虎.EXCEl軟件在物流運(yùn)籌學(xué)教學(xué)中應(yīng)用探索[J].物流科技，2012，（8）：108-111.

[9]魏杰羽.EXCEl在物流運(yùn)籌課程中的應(yīng)用[J].物流工程與管理，2012，（5）：201-203.

[10]張輝如何試用EXEL軟件求解運(yùn)籌學(xué)模型[J].現(xiàn)代企業(yè)文化，2009，（11）：144-145.