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

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

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

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

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

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

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

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