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

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

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

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

4、收端口,所以調(diào)整次數(shù)不會超過m次 算法必然會結(jié)束，即算法可行 “調(diào)整”算法正確性 : 可采用“分類討論”的方法很簡單地證明,例一遠程通信,更優(yōu): B島上接收端口數(shù)目減少 因為問題總是出現(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提交答案）,給定一個N*M的整數(shù)矩陣A(N,M500) 同一列中的兩個數(shù)可以調(diào)換 請求出一個經(jīng)過若

5、干次調(diào)換的矩陣 使得最大的行和最小,可交換,最大和 最小,可交換,貪心算法: 最大和最小，等價與讓所有的和都盡量平均。 一個直觀的貪心思想： 把最大和最小湊一起 依次安排每一列。 當我們安排第c列時，前c-1列已經(jīng)被安排好。 Tab For this Level,常規(guī)算法： 動態(tài)規(guī)劃:狀態(tài)是指數(shù)級別的 搜索:N,M 過大,搜索不可能出解 貪心算法:,例三零件裝配,前c-1列,第c列,例三零件裝配,然而這個貪心算法得到的解并不優(yōu)。 請看下面例子:,1,1,4,2,2,6,3,3,8,8 10 12,1 1 8 2 2 6 3 3 4,局部的最優(yōu)，可能導致全局的不優(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) 得到一個隨機的初始方案A (2) While 方案A“可調(diào)整” DO (3)尋找數(shù)對進行調(diào)整操作 (4) 得到“極優(yōu)”方案A,由于不同的初始方案可能得到不同的“極優(yōu)”方案,所以我們可以采用多次隨機

7、初始方案，得到若干個極優(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,基準列,從小到大排序,從小到大排序,按照貪心思想分配,每次調(diào)整，方案很可能會更優(yōu)，至少不會變差,例三零件裝配,局部調(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),模擬退火算法來源于固體退火原理。 將固體加溫至溫度充分高，再讓其徐徐冷卻. 加溫時，固體內(nèi)部粒子隨著溫度升高變?yōu)闊o序狀，內(nèi)能增大；而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡狀態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。 根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為,模擬退火算法簡介(2),(1)初始化: 初始溫度T(足夠大),初始解(S),L (2)For k = 1 L Do (3)產(chǎn)生新解S (4)計算增量dt = C(S) C(S) (5)如果dt 0),回到第(2)步,“調(diào)整”思想,例一調(diào)整算法正確性證明,(2) While B島上存在無用接收端口x Do (3)改變x的狀態(tài)，設為發(fā)送模式 (4)設置x的目標端口為接收模式,B島上的接收端口,B島上的發(fā)送端口,A島上的接收端口,A