算法合集之《淺談“調(diào)整”思想在信息學(xué)競賽中的應(yīng)用》.ppt

1、淺談 在信息學(xué)中的應(yīng)用,浙江紹興一中 唐文斌,“調(diào)整”思想,引入,“調(diào)整”的本義為： 改變?cè)械那闆r，使之更適應(yīng)客觀環(huán)境和要求 產(chǎn)業(yè)結(jié)構(gòu)調(diào)整 軍事戰(zhàn)略調(diào)整,“調(diào)整” ? ?,單純形算法,模擬退火算法,引入,題目難度越來越大 數(shù)據(jù)關(guān)系越來越復(fù)雜,目標(biāo),已知,x,不滿足要求的 初始解,更優(yōu)解,更優(yōu)解,更優(yōu)解,調(diào)整,調(diào)整,調(diào)整,調(diào)整,信息學(xué)中的“調(diào)整”思想,例一遠(yuǎn)程通信（Baltic2001）,波羅的海上有兩個(gè)小島 每個(gè)小島上都有一些遠(yuǎn)程通信端口 每個(gè)端口都連接著對(duì)方小島上的一個(gè)端口,稱為 “目標(biāo)端口” 每個(gè)端口可以工作在 發(fā)送模式(黃色標(biāo)記) 接收模式(藍(lán)色標(biāo)記),A島,B島,1,2,3,4,1,

2、2,3,4,5,n個(gè),m個(gè),1,2,3,4,1,2,3,4,5,例一遠(yuǎn)程通信,請(qǐng)?jiān)O(shè)置這n+m個(gè)端口的工作模式，使得所有端口都處于工作狀態(tài)。(n+m105) 即要求: 對(duì)于發(fā)送端口A，其目標(biāo)端口必須處于接收模式 對(duì)于接收端口B,至少存在另一個(gè)端口以B為目標(biāo)端口且處于發(fā)送模式,n個(gè),m個(gè),發(fā)送端口,接收端口,先從樣例下手,A島,B島,發(fā)出去的數(shù)據(jù)有人接,有數(shù)據(jù)可收,1,2,3,4,1,2,3,4,5,例一遠(yuǎn)程通信,從樣例下手: A島的2號(hào) B島的1號(hào)、4號(hào) 只能設(shè)置為發(fā)送模式 其目標(biāo)端口必須為接收模式 A島的3號(hào)和B島的3號(hào),n個(gè),m個(gè),A島,B島,發(fā)送端口,接收端口,例一遠(yuǎn)程通信,這個(gè)簡單的事實(shí)

3、，看起來似乎很有用! 那它是否總是能幫助我們找到解答呢？ 答案是否定的,1,2,3,4,A島,B島,1,2,3,4,從一個(gè)不滿足要求的“初始解”開始,發(fā)送端口,接收端口,1,2,3,4,例一遠(yuǎn)程通信,“調(diào)整”算法 (1)設(shè)置初始解(不一定滿足要求) 設(shè)A島上的所有端口都是發(fā)送模式 設(shè)B島上的所有端口都是接收模式 (2) While B島上存在無用接收端口x Do (3)改變x的狀態(tài)，設(shè)為發(fā)送模式 (4)設(shè)置x的目標(biāo)端口為接收模式,A島,B島,1,2,3,4,5,“調(diào)整”操作:,例一遠(yuǎn)程通信,“調(diào)整”算法可行性 : 每一次”調(diào)整”操作,會(huì)把B島上的一個(gè)接收端口改為發(fā)送端口 B島上最初一共有m個(gè)接

4、收端口,所以調(diào)整次數(shù)不會(huì)超過m次 算法必然會(huì)結(jié)束，即算法可行 “調(diào)整”算法正確性 : 可采用“分類討論”的方法很簡單地證明,例一遠(yuǎn)程通信,更優(yōu): B島上接收端口數(shù)目減少 因?yàn)閱栴}總是出現(xiàn)在B島的接收端口上,解答,已知,x,不滿足要求的 初始解,更優(yōu)解,更優(yōu)解,更優(yōu)解,調(diào)整,調(diào)整,調(diào)整,調(diào)整,調(diào)“不可行”為“可行”,A1,1, A1,2, A1,3A1,m A2,1, A2,2, A2,3A2,m An,1, An,2, An,3An,m,Sum1 Sum2 Sumn,例三零件裝配（CTSC2004提交答案）,給定一個(gè)N*M的整數(shù)矩陣A(N,M500) 同一列中的兩個(gè)數(shù)可以調(diào)換 請(qǐng)求出一個(gè)經(jīng)過若

5、干次調(diào)換的矩陣 使得最大的行和最小,可交換,最大和 最小,可交換,貪心算法: 最大和最小，等價(jià)與讓所有的和都盡量平均。 一個(gè)直觀的貪心思想： 把最大和最小湊一起 依次安排每一列。 當(dāng)我們安排第c列時(shí)，前c-1列已經(jīng)被安排好。 Tab For this Level,常規(guī)算法： 動(dòng)態(tài)規(guī)劃:狀態(tài)是指數(shù)級(jí)別的 搜索:N,M 過大,搜索不可能出解 貪心算法:,例三零件裝配,前c-1列,第c列,例三零件裝配,然而這個(gè)貪心算法得到的解并不優(yōu)。 請(qǐng)看下面例子:,1,1,4,2,2,6,3,3,8,8 10 12,1 1 8 2 2 6 3 3 4,局部的最優(yōu)，可能導(dǎo)致全局的不優(yōu),10,例三零件裝配,A1,1,

6、 A1,2, A1,3A1,m A2,1, A2,2, A2,3A2,m An,1, An,2, An,3An,m,嘗試交換,Sum1,Sumn,如果滿足 |Sum1-Sum2| |Sum1-Sumn|,我們稱此方案“可調(diào)整”,調(diào)整算法:,“極優(yōu)”方案, Sum1 Sum2 Sumn,Sum1= Sum1-A1,3+An,3,Sumn= Sumn-An,3+A1,3,例三零件裝配,調(diào)整算法: (1) 得到一個(gè)隨機(jī)的初始方案A (2) While 方案A“可調(diào)整” DO (3)尋找數(shù)對(duì)進(jìn)行調(diào)整操作 (4) 得到“極優(yōu)”方案A,由于不同的初始方案可能得到不同的“極優(yōu)”方案,所以我們可以采用多次隨機(jī)

7、初始方案，得到若干個(gè)極優(yōu)方案從中取最優(yōu)的方法，效果非常好。,A1,3A1,m A2,3A2,m An,3An,m,例三零件裝配,把最大的和最小的湊在一起 第二種”調(diào)整”方法,A1,1, A2,1, An,1,A1,2, A2,2, An,2,基準(zhǔn)列,從小到大排序,從小到大排序,按照貪心思想分配,每次調(diào)整，方案很可能會(huì)更優(yōu)，至少不會(huì)變差,例三零件裝配,局部調(diào)整 整體調(diào)整,極優(yōu)方案,初始 可行方案,調(diào)“可行”為“更優(yōu)”,回顧與總結(jié),例一 調(diào)“不可行” 為“可行” 一類構(gòu)造性問題 例二混合圖歐拉回路問題 例三 調(diào)“可行”為“更優(yōu)” 一類非最優(yōu)化的開放性問題中 例四Ural著名難題皇帝的困惑,從無到有

8、,從有到優(yōu),調(diào)整思想的精髓,Thank You !,模擬退火算法簡介(1),模擬退火算法來源于固體退火原理。 將固體加溫至溫度充分高，再讓其徐徐冷卻. 加溫時(shí)，固體內(nèi)部粒子隨著溫度升高變?yōu)闊o序狀，內(nèi)能增大；而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡狀態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為,模擬退火算法簡介(2),(1)初始化: 初始溫度T(足夠大),初始解(S),L (2)For k = 1 L Do (3)產(chǎn)生新解S (4)計(jì)算增量dt = C(S) C(S) (5)如果dt 0),回到第(2)步,“調(diào)整”思想,例一調(diào)整算法正確性證明,(2) While B島上存在無用接收端口x Do (3)改變x的狀態(tài)，設(shè)為發(fā)送模式 (4)設(shè)置x的目標(biāo)端口為接收模式,B島上的接收端口,B島上的發(fā)送端口,A島上的接收端口,A