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

2、置這n+m個端口的工作模式，使得所有端口都處于工作狀態(tài)。(n+m105)n即要求:n對于發(fā)送端口A，其目標端口必須處于接收模式n對于接收端口B,至少存在另一個端口以B為目標端口且處于發(fā)送模式n個m個發(fā)送端口接收端口先從樣例下手A島島B島島發(fā)出去的數(shù)據(jù)有人接有數(shù)據(jù)可收AB123412345例一遠程通信n從樣例下手:nA島的2號nB島的1號、4號n只能設置為發(fā)送模式n其目標端口必須為接收模式nA島的3號和B島的3號n個m個A島島B島島發(fā)送端口接收端口例一遠程通信n這個簡單的事實，看起來似乎很有用!n那它是否總是能幫助我們找到解答呢？n答案是否定的1234A島島B島島1234從一個不滿足要求的“初始

3、解”開始發(fā)送端口接收端口1234例一遠程通信n“調(diào)整”算法n(1)設置初始解(不一定滿足要求)設A島上的所有端口都是發(fā)送模式設B島上的所有端口都是接收模式n(2) While B島上存在無用接收端口x Don(3)改變x的狀態(tài)，設為發(fā)送模式n(4)設置x的目標端口為接收模式A島島B島島12345“調(diào)整”操作:例一遠程通信n“調(diào)整”算法可行性 :n每一次”調(diào)整”操作,會把B島上的一個接收端口改為發(fā)送端口nB島上最初一共有m個接收端口,所以調(diào)整次數(shù)不會超過m次n算法必然會結束，即算法可行n“調(diào)整”算法正確性 :n可采用“分類討論”的方法很簡單地證明例一遠程通信n更優(yōu): B島上接收端口數(shù)目減少 因為

4、問題總是出現(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,mA2,1, A2,2, A2,3A2,m An,1, An,2, An,3An,mSum1Sum2Sumn例三零件裝配（CTSC2004提交答案）n給定一個N*M的整數(shù)矩陣A(N,M500)n同一列中的兩個數(shù)可以調(diào)換n請求出一個經(jīng)過若干次調(diào)換的矩陣n使得最大的行和最小可交換最大和 最小可交換n貪心算法:n最大和最小，等價與讓所有的和都盡量平均。n一個直觀的貪心思想： 把最大和最小湊一起n依次安排每一列。n當我們安排第c列時，前c-1列

5、已經(jīng)被安排好。nTab For this Leveln常規(guī)算法：n動態(tài)規(guī)劃:狀態(tài)是指數(shù)級別的n搜索:N,M 過大,搜索不可能出解n貪心算法:例三零件裝配前c-1列第c列從小到大排序從小到大排序例三零件裝配n然而這個貪心算法得到的解并不優(yōu)。n請看下面例子:114226338810121 1 82 2 63 3 4局部的最優(yōu)，可能導致全局的不優(yōu)10例三零件裝配A1,1, A1,2, A1,3A1,mA2,1, A2,2, A2,3A2,m An,1, An,2, An,3An,m嘗試交換Sum1Sumn如果滿足 |Sum1-Sum2| |Sum1-Sumn|我們稱此方案“可調(diào)整”n調(diào)整算法:“極優(yōu)

6、”方案 Sum1 Sum2 SumnSum1= Sum1-A1,3+An,3Sumn= Sumn-An,3+A1,3例三零件裝配n調(diào)整算法:n(1) 得到一個隨機的初始方案An(2) While 方案A“可調(diào)整” DOn(3)尋找數(shù)對進行調(diào)整操作n(4) 得到“極優(yōu)”方案An由于不同的初始方案可能得到不同的“極優(yōu)”方案,所以我們可以采用多次隨機初始方案，得到若干個極優(yōu)方案從中取最優(yōu)的方法，效果非常好。A1,3A1,mA2,3A2,m An,3An,m例三零件裝配n把最大的和最小的湊在一起n第二種”調(diào)整”方法A1,1, A2,1, An,1, A1,2,A2,2, An,2,基準列從小到大排序從

7、小到大排序按照貪心思想分配按照貪心思想分配每次調(diào)整，方案很可能會更優(yōu)，至少不會變差例三零件裝配n局部調(diào)整n整體調(diào)整極優(yōu)方案初始可行方案“調(diào)整”操作調(diào)“可行”為“更優(yōu)”回顧與總結例一調(diào)“不可行” 為“可行”一類構造性問題例二混合圖歐拉回路問題例三調(diào)“可行”為“更優(yōu)”一類非最優(yōu)化的開放性問題中例四Ural著名難題皇帝的困惑從無到有從有到優(yōu)調(diào)整思想的精髓模擬退火算法簡介(1)n模擬退火算法來源于固體退火原理。n將固體加溫至溫度充分高，再讓其徐徐冷卻.n加溫時，固體內(nèi)部粒子隨著溫度升高變?yōu)闊o無序狀序狀，內(nèi)能增大；而徐徐冷卻時粒子漸趨有有序序，在每個溫度都達到平衡狀態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。n根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為 ()(*Eek BoltzmannT內(nèi)能改變量常數(shù))模擬退火算法簡介(2)n(1)初始化: 初始溫度T(足夠大),初始解(S),Ln(2)For k = 1 L Don(3)產(chǎn)生新解Sn(4)計算增量dt = C(S) C(S)n(5)如果dt 0),回到第(2)步“調(diào)整”思想例一調(diào)整算法正確性證明n(2) While B島上存在無用接收端口x Don(3)改變x的狀態(tài)，設為發(fā)送模式n(4)設置x的目標端口為接收模式B島上的接收端口B島上的發(fā)送端口A島上的接收端口A島上的發(fā)