算法合集之用改進(jìn)算法思想解決規(guī)模維數(shù)增大問題(已修改)
2025-06-22 01:38 本頁面
【正文】 從1到2，從2到3——用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達(dá)用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題廣東韶關(guān)一中 張偉達(dá)【關(guān)鍵字】 增大規(guī)模 改進(jìn)算法 降維 分析 構(gòu)造【摘要】我們常常會(huì)遇到一些特殊的問題，它們把我們能夠解決的問題改了一改，增加了一維，或者增加了一個(gè)因素，從1到2或者是從2到3，本文把它們統(tǒng)稱規(guī)模維數(shù)增大的問題。解決這類問題可以用改進(jìn)算法的思想：本文第一部分先是概述這種思想；第二部分則從一道有趣的IQ題目說起，引入改進(jìn)算法的基本思路和基本途徑；第三部分則用多個(gè)例子解釋說明如何改進(jìn)算法；最后一部分是總結(jié)改進(jìn)算法的思想?！灸夸洝恳?、概述 2二、引子：從一道IQ題說起 2三、改進(jìn)算法的途徑 3(1)直接增加算法的規(guī)模，解決問題 3【例一】街道問題及其擴(kuò)展。（經(jīng)典問題） 3(2)用枚舉處理增加的規(guī)模，從而解決問題 4【例二】旅行（廣東省奧林匹克競賽2001） 4【例三】炮兵陣地。（NOI2001） 5(3)用貪心解決增加的規(guī)模，從而解決問題 5【例四】求網(wǎng)絡(luò)的最小費(fèi)用最大流。（經(jīng)典問題） 5(4)多種途徑的綜合運(yùn)用 6【例五】Team Selection (Balkan OI 2004 Day1) 6四、總結(jié) 9【感謝】 9【參考文獻(xiàn)】 10【附錄】 11(廣東省奧林匹克競賽2001) 11（NOI2001） 12 Selection (BalkanOI 2004 Day 1 Task 2) 13 一、概述每個(gè)學(xué)習(xí)信息學(xué)奧林匹克的選手總是要先學(xué)習(xí)一些基本的算法，然后才能把算法應(yīng)用到題目當(dāng)中去。但是，題目形式多種多樣，這些算法往往是不能夠直接套用的。有的時(shí)候我們分析到某個(gè)問題好像可以用某種方法解決，但是這個(gè)問題卻與之前見過的問題有些不同，例如本文所討論的情況：問題的規(guī)模維數(shù)比原問題大，一維的變二維的，二維的變?nèi)S的，等等。我們不妨把這類問題叫做規(guī)模維數(shù)增大的問題，解決這一類問題，往往需要觀察問題的特殊性，改進(jìn)原有算法，從而解決實(shí)際問題。二、引子：從一道IQ題說起【IQ題題目】在走入正題之前，還是讓我們來玩一道IQ題(據(jù)說是IBM公司招聘面試用過的題目)：有兩根完全相同但分布不均勻的香（提示：不妨假設(shè)是蚊香，一圈圈的那種），每根香燒完的時(shí)間是一個(gè)小時(shí)，你能用什么方法來確定一段45分鐘的時(shí)間？【……】（思考中）【思路】在公布答案之前，還是讓我們來循序漸進(jìn)地思考下去吧。要確定45分鐘的時(shí)間，而每根香燒完的時(shí)間是一個(gè)小時(shí)，現(xiàn)在應(yīng)該有三個(gè)模型讓我們思考：，兩根香加在一起計(jì)時(shí)是45分鐘；，使其計(jì)時(shí)減小，直接計(jì)時(shí)45分鐘；，使兩根香加起來是45分鐘。A模型顯然是不可能成立的；B、C模型的共同點(diǎn)是：我們必須使一根香的計(jì)時(shí)減小。但是怎樣減，能減成什么呢？顯然是不能直接把它們分開的，因?yàn)橄愕姆植疾痪鶆?。由于這里筆者已經(jīng)降低了難度，根據(jù)提示，比較容易想到香是可以兩頭一起燒的。這樣，我們就能把一根香的計(jì)時(shí)減成半個(gè)小時(shí)。方案已經(jīng)更進(jìn)一步了。通過這一步，B模型只用一根香，是很容易被排除的。余下的選擇只有“C模型+兩頭燒方法”了，但是C模型不能直接應(yīng)用“兩頭燒”，因?yàn)檫@樣套用的話，+。我們需要對“兩頭燒”做進(jìn)一步改進(jìn)：如果一根香只燒了一頭，當(dāng)剩余時(shí)間為t的時(shí)候，我們把另一頭也點(diǎn)燃——那么，我們就能夠計(jì)出t/2的時(shí)間了（前提是我們已知當(dāng)前剩余時(shí)間t）。特別地，當(dāng)t=60min時(shí)，t/2=30min。根據(jù)這一改進(jìn)后的方法，我們很容易就得出正確的解法：分別點(diǎn)燃第一根的兩頭和第二根的一頭，第一根燒完的時(shí)候，已經(jīng)過了30分鐘；第二根還剩30分鐘，點(diǎn)燃第二根的另一頭；當(dāng)?shù)诙矡炅?，即時(shí)間又過了15分鐘。那么我們計(jì)出的總的時(shí)間就為45分鐘了?！拘〗Y(jié)】上面這個(gè)例子中，我們從構(gòu)造模型和改進(jìn)算法兩方面入手，一步一步地達(dá)到了優(yōu)化的解法。主要流程是：1. 找出原始解法和可能改進(jìn)的方向（即分析成A、B、C模型）；2. 分析算法的原理（由燒一根香計(jì)時(shí)半小時(shí)，引申為燒剩t的時(shí)候點(diǎn)兩頭就能計(jì)時(shí)）；3. 改進(jìn)算法（改進(jìn)的過程中，往往不是依靠算法改進(jìn)算法本身，反而是利用算法的內(nèi)涵、實(shí)質(zhì)，結(jié)合問題，構(gòu)造算法）；4. 解決問題（我們得出了正確的解法）。但是如何來改進(jìn)原有的算法呢，筆者認(rèn)為可以有以下途徑：1. 直接增加算法的規(guī)模，解決問題2. 用枚舉處理增加的規(guī)模，從而解決問題3. 用貪心解決增加的規(guī)模，從而解決問題4. 以上各個(gè)途徑的綜合運(yùn)用圍繞這一主線，筆者將用例題做進(jìn)一步的闡明。三、改進(jìn)算法的途徑(1)直接增加算法的規(guī)模，解決問題解決簡單的問題，常?？梢圆捎弥苯犹幚淼姆椒ǎ呛芏鄷r(shí)候還是需要一些技巧。【例一】街道問題及其擴(kuò)展。（經(jīng)典問題）【題目大意】〖原題〗在右圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走?！紨U(kuò)展〗在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，并且要求兩條路徑的總長度最短。【問題分析】原題是一道簡單而又典型的動(dòng)態(tài)規(guī)劃題，很顯然，可以用這樣的動(dòng)態(tài)規(guī)劃方程解題：（這里Distance表示相鄰兩點(diǎn)間的邊長）但是對于擴(kuò)展后的題目：再用這種簡單的方法就不太好辦了。如果非得套用這種方法的話，則最優(yōu)指標(biāo)函數(shù)就需要有四維的下標(biāo)，并且難以處理兩條路徑“不能重疊”的問題。我們來分析一下原方法的實(shí)質(zhì)：按照圖中的斜線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變量xk表示當(dāng)前處于這一階段上的哪一點(diǎn)。這時(shí)的模型實(shí)際上已經(jīng)轉(zhuǎn)化成了一個(gè)特殊的多段圖。用決策變量uk=0表示向右走，uk=1表示向上走，則狀態(tài)轉(zhuǎn)移方程為：(這里的row是地圖豎直方向的行數(shù))。通過這一步觀察，我們就會(huì)發(fā)現(xiàn)這個(gè)問題很好
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1