數(shù)學(xué)歸納法與解題之道

1、IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,數(shù)學(xué)歸納法與解題之道,山西省實(shí)驗(yàn)中學(xué)　張昆瑋,道,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,貪心,構(gòu)造,優(yōu)化,如此之多的算法，是怎樣想到的？這些算法巧誠(chéng)巧矣，可正確性怎么證明呢？,引言,道生一，一生二，二生三，三生萬(wàn)物。,——老子：《道德經(jīng)》,數(shù)學(xué)歸納法,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,概覽,2.在證明算法正確性上的應(yīng)用貪心算法其他算法,3.在構(gòu)造性算法中的應(yīng)用數(shù)據(jù)結(jié)

2、構(gòu)的恢復(fù)性構(gòu)造策略與解決方案的構(gòu)造,4.數(shù)學(xué)歸納法與算法優(yōu)化巧妙選擇歸納對(duì)象力求完善歸納基礎(chǔ)慎重選擇歸納方向適當(dāng)加強(qiáng)歸納假設(shè),5.啟發(fā)作用與美學(xué)價(jià)值,6.問(wèn)題與缺陷理論上是否欠完備應(yīng)用上是否較繁瑣不適用的問(wèn)題,1.關(guān)于數(shù)學(xué)歸納法簡(jiǎn)短的回顧基本的定理、概念與方法是總結(jié)更是探索,例5（線性結(jié)構(gòu)）Set Cover例6（樹狀結(jié)構(gòu)）Roman Roads,√,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,難,缺乏固定套路依

3、賴于具體的數(shù)據(jù)結(jié)構(gòu),通用靈活適用于各種數(shù)據(jù)結(jié)構(gòu),易,構(gòu)造性問(wèn)題,,,數(shù)學(xué)歸納法,,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,【例5】Set Cover——數(shù)據(jù)結(jié)構(gòu)的恢復(fù)性構(gòu)造,子集覆蓋問(wèn)題定義為選出盡量少的子集，使已知集合中的每個(gè)元素至少屬于其中的一個(gè)。 線段覆蓋問(wèn)題定義為選出盡量少的整點(diǎn)，使給定的每條線段上都至少有其中的一個(gè)。 以整點(diǎn)為子集，所有包含這個(gè)整點(diǎn)的線段為子集中的元素，可以把一

4、個(gè)線段覆蓋問(wèn)題歸約到子集覆蓋問(wèn)題。如果給定一個(gè)由線段覆蓋問(wèn)題歸約成的子集覆蓋問(wèn)題，該怎么解決呢？,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,線段覆蓋問(wèn)題,在數(shù)軸上選出盡量少的整點(diǎn)給定的每條線段上必須至少有其中的一個(gè)按左端點(diǎn)排序后有簡(jiǎn)單的貪心算法,,,,,,,,,,√,√,√,√,√,,,,,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,轉(zhuǎn)化成子集覆蓋問(wèn)題,整點(diǎn)作為集合（實(shí)際上只需每線段的右端點(diǎn)）所有包含此整點(diǎn)的線段為其元素一般的子集

5、覆蓋問(wèn)題→NP完全,,,,,,,,,,,,1,2,3,4,5,1,2,2,3,3,4,4,5,5,,,,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,怎么辦？,恢復(fù)線性結(jié)構(gòu),直接搜索,Tips：只需要恢復(fù)線段的位置關(guān)系和每個(gè)線段的右端點(diǎn),IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,定義線段的位置,線段的位置即為其中點(diǎn)的位置兩線段距離即為其中點(diǎn)的距離兩線段距離可以使用對(duì)應(yīng)集合運(yùn)算求出,,兩線段必須相交！,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張

6、昆瑋,到底是“＋”還是“－”？,問(wèn)題：如何拓展連通分量？,我們把問(wèn)題分為連通分量來(lái)處理兩個(gè)連通分量之間線段距離可以任意，不影響結(jié)論每個(gè)連通分量的第一條線段位置任意,,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,調(diào)整歸納假設(shè),只有一條線段時(shí)方向無(wú)關(guān)緊要初始時(shí)刻選擇不同的方向只會(huì)使最終的結(jié)果互為軸對(duì)稱而已。其他情形中為了判斷方向，我們需要調(diào)整歸納假設(shè),,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,同側(cè)？異側(cè)？,,X與B在A的同側(cè)的充分必

7、要條件是他們?cè)贏之內(nèi)的部分存在包含關(guān)系,,,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,同側(cè)？異側(cè)？,,X與B在A的同側(cè)的充分必要條件是他們?cè)贏之內(nèi)的部分存在包含關(guān)系,,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,線段的右端點(diǎn),,,所有與A相交、在A右側(cè)的線段與A的公共點(diǎn),問(wèn)題解決,IOI2009國(guó)家集訓(xùn)隊(duì)論文演示 張昆瑋,小結(jié),以上解題過(guò)程用庖丁解牛的方法步步推進(jìn)，將問(wèn)題分為多個(gè)部分，逐一化解數(shù)學(xué)歸納法靈活的歸納假設(shè)為主要問(wèn)題的求解提供