算法合集之用改進(jìn)算法思想解決規(guī)模維數(shù)增大問(wèn)題-在線(xiàn)瀏覽
2025-07-28 01:38本頁(yè)面
【正文】 【參考文獻(xiàn)】 10【附錄】 11(廣東省奧林匹克競(jìng)賽2001) 11（NOI2001） 12 Selection (BalkanOI 2004 Day 1 Task 2) 13 一、概述每個(gè)學(xué)習(xí)信息學(xué)奧林匹克的選手總是要先學(xué)習(xí)一些基本的算法，然后才能把算法應(yīng)用到題目當(dāng)中去。有的時(shí)候我們分析到某個(gè)問(wèn)題好像可以用某種方法解決，但是這個(gè)問(wèn)題卻與之前見(jiàn)過(guò)的問(wèn)題有些不同，例如本文所討論的情況：?jiǎn)栴}的規(guī)模維數(shù)比原問(wèn)題大，一維的變二維的，二維的變?nèi)S的，等等。二、引子：從一道IQ題說(shuō)起【IQ題題目】在走入正題之前，還是讓我們來(lái)玩一道IQ題(據(jù)說(shuō)是IBM公司招聘面試用過(guò)的題目)：有兩根完全相同但分布不均勻的香（提示：不妨假設(shè)是蚊香，一圈圈的那種），每根香燒完的時(shí)間是一個(gè)小時(shí)，你能用什么方法來(lái)確定一段45分鐘的時(shí)間？【……】（思考中）【思路】在公布答案之前，還是讓我們來(lái)循序漸進(jìn)地思考下去吧。A模型顯然是不可能成立的；B、C模型的共同點(diǎn)是：我們必須使一根香的計(jì)時(shí)減小。由于這里筆者已經(jīng)降低了難度，根據(jù)提示，比較容易想到香是可以?xún)深^一起燒的。方案已經(jīng)更進(jìn)一步了。余下的選擇只有“C模型+兩頭燒方法”了，但是C模型不能直接應(yīng)用“兩頭燒”，因?yàn)檫@樣套用的話(huà)，+。特別地，當(dāng)t=60min時(shí)，t/2=30min。那么我們計(jì)出的總的時(shí)間就為45分鐘了。主要流程是：1. 找出原始解法和可能改進(jìn)的方向（即分析成A、B、C模型）；2. 分析算法的原理（由燒一根香計(jì)時(shí)半小時(shí)，引申為燒剩t的時(shí)候點(diǎn)兩頭就能計(jì)時(shí)）；3. 改進(jìn)算法（改進(jìn)的過(guò)程中，往往不是依靠算法改進(jìn)算法本身，反而是利用算法的內(nèi)涵、實(shí)質(zhì)，結(jié)合問(wèn)題，構(gòu)造算法）；4. 解決問(wèn)題（我們得出了正確的解法）。三、改進(jìn)算法的途徑(1)直接增加算法的規(guī)模，解決問(wèn)題解決簡(jiǎn)單的問(wèn)題，常?？梢圆捎弥苯犹幚淼姆椒?，但是很多時(shí)候還是需要一些技巧。（經(jīng)典問(wèn)題）【題目大意】〖原題〗在右圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。【問(wèn)題分析】原題是一道簡(jiǎn)單而又典型的動(dòng)態(tài)規(guī)劃題，很顯然，可以用這樣的動(dòng)態(tài)規(guī)劃方程解題：（這里Distance表示相鄰兩點(diǎn)間的邊長(zhǎng)）但是對(duì)于擴(kuò)展后的題目：再用這種簡(jiǎn)單的方法就不太好辦了。我們來(lái)分析一下原方法的實(shí)質(zhì)：按照?qǐng)D中的斜線(xiàn)來(lái)劃分階段，即階段變量k表示走過(guò)的步數(shù)，而狀態(tài)變量xk表示當(dāng)前處于這一階段上的哪一點(diǎn)。用決策變量uk=0表示向右走，uk=1表示向上走，則狀態(tài)轉(zhuǎn)移方程為：(這里的row是地圖豎直方向的行數(shù))。即用分別表示兩條路徑走到階段k時(shí)所處的位置，相應(yīng)的，決策變量也增加一維，用分別表示兩條路徑的行走方向。(2)用枚舉處理增加的規(guī)模，從而解決問(wèn)題【例二】旅行（廣東省奧林匹克競(jìng)賽2001）【題目大意】給出一個(gè)NM的數(shù)字矩陣，要求這個(gè)矩陣的一個(gè)子矩陣，并要求這個(gè)子矩陣的數(shù)字和最大。這樣，時(shí)間復(fù)雜度達(dá)到O(N4)，顯然不可以接受。先看一維時(shí)候的情況：在數(shù)列ai中找出和最大的一段。但是如果純粹三重循環(huán)，枚舉頭，枚舉尾，枚舉中間求和，顯然是太浪費(fèi)了。這樣，動(dòng)態(tài)規(guī)劃的思路就明顯了，Si,j與Si1,j有直接的關(guān)系，而且我們還可以發(fā)現(xiàn)Si,*（表示從Si,1到Si,i1構(gòu)成的數(shù)列）只比Si1,*多了一項(xiàng)。我們可以嘗試著構(gòu)造上下、左右同時(shí)進(jìn)行的動(dòng)態(tài)規(guī)劃，但是也許我們無(wú)能為力。不難想到，枚舉上下方向的數(shù)列和，在左右方向用動(dòng)態(tài)規(guī)劃求解，可以得到時(shí)間復(fù)雜度在O(N3)的算法。但是枚舉這個(gè)簡(jiǎn)單的方法，卻能解決很復(fù)雜的問(wèn)題。（NOI2001）【題目大意】在圖中標(biāo)為P的格子中放炮兵，如圖灰色區(qū)域放了炮兵后，黑色區(qū)域不能放炮兵，問(wèn)圖中最多能放多少炮兵？【問(wèn)題分析】簡(jiǎn)化的問(wèn)題：若只有一列，問(wèn)最多可以放多少炮兵。但是容易觀察到，mn，最大只有10，又因?yàn)榕诒舴秶艽螅瑢?shí)際上能放炮兵的組合數(shù)很小，可以考慮枚舉組合，從而得到改進(jìn)的動(dòng)態(tài)規(guī)劃方法：以?xún)尚袨橐粋€(gè)狀態(tài)，s1表示狀態(tài)中上行的炮兵布置情況，s2表示下行的布置情況，（可以預(yù)先枚舉所有可能的情況并給這些情況標(biāo)號(hào)）當(dāng)?shù)趇行能不能布置s1或第i+1行不能布置s2時(shí)，或者s1,s2在同一位置布置了炮兵時(shí)，都是不符合情況的，令此時(shí)；否則：，其中counts2表示s2的炮兵個(gè)數(shù)；s表示該s1,s2的前一行的炮兵布置情況，而且滿(mǎn)足：不存在這樣的j。（經(jīng)典問(wèn)題）顯然，求最小費(fèi)用最大流可以由求最大流的算法改進(jìn)。那么，又如何把費(fèi)用也考慮進(jìn)去呢？我們先來(lái)看看網(wǎng)絡(luò)的費(fèi)用的定義吧。（弧的費(fèi)用由可能為負(fù)）所以網(wǎng)絡(luò)的最小費(fèi)用最大流是指可行流中費(fèi)用最小的。這樣可以得出一個(gè)改進(jìn)：每次選取一條費(fèi)用最?。ǘ曳钦┑目稍鰪V路徑，直到最終不存在費(fèi)用非正的可增廣路徑。(4)多種途徑的綜合運(yùn)用【例五】Team Selection (Balkan OI 2004 Day1)【題目大意】IOI要來(lái)了，BP隊(duì)要選擇最好的選手去參加。為了選出的選手是最好的，教練組織了三次競(jìng)賽并給出每次競(jìng)賽排名。當(dāng)A在所有競(jìng)賽中名次都比B前，我們就說(shuō)A是比B better。求excellent選手的個(gè)數(shù)?！驹妓悸贰恳荒玫竭@一題，很容易會(huì)有以下的思路。簡(jiǎn)單地根據(jù)better和excellent的定義，現(xiàn)只需要枚舉每一個(gè)選手X，判斷X是否excellent。判斷是容易的，我們只需要簡(jiǎn)單地判斷X和Y的三次排名。主要流程1： for(X從1到N) for(Y從1到N) 判斷Y是否比X better〖改進(jìn)一〗原始算法是可以改進(jìn)的。不過(guò)這樣小的改進(jìn)提起來(lái)只是開(kāi)闊開(kāi)闊思路，它對(duì)時(shí)間復(fù)雜度不會(huì)有太大影響。我們發(fā)現(xiàn)：如果Y不是excellent（因?yàn)橛衂比Y better），當(dāng)我們檢查X是否excellent時(shí)，我們檢查了Z是否比X better的話(huà)，可以不檢查Y。然后可以通過(guò)簡(jiǎn)單地修改“改進(jìn)一”。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1