從數(shù)模競(jìng)賽到出題和科研

1、從數(shù)模競(jìng)賽到出題和科研 肖華勇一、從數(shù)模競(jìng)賽到出題從對(duì)生活和社會(huì)的觀察，從實(shí)際課題中提出可用于數(shù)模競(jìng)賽的問(wèn)題?；蛘咴谂c其它學(xué)科的人員的交流討論中獲得一定素材。逐步修改為賽題。2008年全國(guó)數(shù)模征題：傳感器節(jié)點(diǎn)配置優(yōu)化問(wèn)題由于發(fā)生汶川大地震，在討論中逐漸改為地震救援搜索問(wèn)題，成為2008年大專組的D題。當(dāng)年做這個(gè)問(wèn)題的隊(duì)很多。校內(nèi)競(jìng)賽中出過(guò)的賽題：2007B 高校分類與排名2008B 自習(xí)教室開放的優(yōu)化管理2008C Kakuro數(shù)獨(dú)的難度級(jí)別劃分問(wèn)題2009 校車安排問(wèn)題2010 送貨路線設(shè)計(jì)問(wèn)題2011 碩士論文質(zhì)量評(píng)價(jià)問(wèn)題出題要求： 1基本要求：提供素材，問(wèn)題的背景和要解決的問(wèn)題。 2較高

2、要求：提供數(shù)據(jù)，給出參考的解答?；蚪袑W(xué)生搜集數(shù)據(jù)，給出參考方案或模型。 參賽對(duì)象：針對(duì)大學(xué)二年級(jí)學(xué)生為主。二、從數(shù)模競(jìng)賽到科研 從數(shù)模賽題中進(jìn)行研究，寫出論文發(fā)表。主要有兩條路。一條是直接對(duì)原來(lái)問(wèn)題提出更好的解法、或者對(duì)某個(gè)問(wèn)題深入研究。這樣的文章比較多。案例1：鉆井布局問(wèn)題1998年B題鉆井布局問(wèn)題，競(jìng)賽后經(jīng)過(guò)進(jìn)一步研究，我寫出了文章兩種不同距離下鉆井布局的模型研究在數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)（2003）上發(fā)表。主要給出了包含n個(gè)點(diǎn)的最小正方形(車氏距離下)與最小圓(Euclid距離定義下)的一般算法，并給出了4個(gè)定理。然后用此方法求解了在兩種不同距離下的計(jì)算結(jié)果。比原來(lái)的要求解決得更漂亮。但沿這樣的

3、路子，很多時(shí)候要有新意比較難，發(fā)表也不易。特點(diǎn)：就問(wèn)題研究問(wèn)題。第二條是從賽題中引出新的實(shí)際問(wèn)題。然后進(jìn)行研究。建立新的模型、設(shè)計(jì)新的算法進(jìn)行求解?；蛘呓o出一些理論性的結(jié)果。這種思路空間更大。案例2：公交問(wèn)題全國(guó)數(shù)模競(jìng)賽 2007年B題“迎奧運(yùn)，乘公交”。該題主要側(cè)重于對(duì)學(xué)生算法設(shè)計(jì)能力及編程能力的要求?？疾禳c(diǎn)較為單一。但在該單點(diǎn)上對(duì)能力的要求很高。該題的結(jié)果雖然很難算，但結(jié)果的好壞卻很容易自己進(jìn)行驗(yàn)證。該題的另一大好處由該題可引申出實(shí)際的課題。如研究一個(gè)大城市中實(shí)際的公交換成，如何尋找最優(yōu)線路，并與8684公交網(wǎng)的查詢結(jié)果進(jìn)行比較，很有實(shí)際價(jià)值。我們從8684公交網(wǎng)上搜索了北京、上海的公交線

4、路，進(jìn)行了前期數(shù)據(jù)預(yù)處理，設(shè)計(jì)了自己的優(yōu)化枚舉快速算法。利用該算法對(duì)上海市的公交系統(tǒng)站點(diǎn)對(duì)的換乘線路進(jìn)行計(jì)算。該公交網(wǎng)絡(luò)巨大，共有8793個(gè)站點(diǎn)，1015條線路（計(jì)算中考慮上下行按照2030條計(jì)算）。下面以從公交公司獲得的上海公交線路信息，通過(guò)Visaul C+編程，得出本算法的換乘方案，與從8684公交網(wǎng)絡(luò)查詢結(jié)果的換乘方案作比較，見(jiàn)表1與表2。表1：8684查詢結(jié)果與本算法結(jié)果對(duì)照表1控江路內(nèi)江路中山北路中潭路8684查詢結(jié)果本算法結(jié)果換乘次數(shù)兩次三次兩次4次經(jīng)過(guò)站數(shù)約34站33站12站乘 車 路 線控江路內(nèi)江路 坐 169路（原589路） 在 張楊路巨野路/張楊路民生路/張楊路桃林路/東

5、方路峨山路 換乘 736路 到 中山南路復(fù)興東路 再換乘 801路 到 中山北路中潭路不 能 提 供控江路內(nèi)江路坐589路（下行）到東方路峨山路轉(zhuǎn)736路（下行）到中山南路復(fù)興東路轉(zhuǎn)801路（下行）到中山北路中潭路控江路內(nèi)江路坐589路（下行）到控江路雙陽(yáng)路轉(zhuǎn)220路大站車（下行）到海寧路吳淞路轉(zhuǎn)922路（上行）到天目西路恒豐路轉(zhuǎn)801路（下行）到中山北路中潭路表2：8684查詢結(jié)果與本算法結(jié)果對(duì)照表2薀藻南路上海鑄管廠華洲路太平村8684查詢結(jié)果本算法結(jié)果換乘次數(shù)兩次三、四次三次四次共坐站點(diǎn)49站41站乘 車 路 線不 能 提 供不 能 提 供薀藻南路上海鑄管廠坐98路（下行） 在廣粵路車站

6、北路換乘21路（下行）到四川北路黃渡路(魯迅公園)換乘991路（上行）到川沙路新源路再換乘622路（上行）到達(dá)華洲路太平村薀藻南路上海鑄管廠坐98路（下行） 在廣粵路車站北路換乘21路（下行）到廣靈四路廣粵路換乘975路（上行）到德平路浦東大道再換乘申川專線（下行）到川沙路新源路再換乘622路（上行）到達(dá)華洲路太平村 特點(diǎn)：從原問(wèn)題中引出新問(wèn)題，進(jìn)行擴(kuò)展性研究，空間更廣闊。案例3：110警車配置問(wèn)題研究生數(shù)模競(jìng)賽2009D的“110警車配置及巡邏方案”。我們從中提出一般性問(wèn)題”。給定一個(gè)城市的街道地圖，同時(shí)給出兩組數(shù)據(jù)：一組是個(gè)街道交點(diǎn)坐標(biāo) ；另一組是條街道中每條街道連接的兩個(gè)端點(diǎn)序號(hào), 。假

7、定警車巡邏可位于任何位置，當(dāng)某處發(fā)生案件時(shí)，最近的警車立刻趕去，其行駛速度為(可取40km/h)。若要求任何一處發(fā)生案件，要求警車3分鐘內(nèi)趕到，問(wèn)整個(gè)城市需要至少配置多少輛警車？如何配置？如果要求3分鐘內(nèi)到達(dá)的概率為95%，90%，結(jié)果又如何？原來(lái)解答中主要針對(duì)巡邏如何優(yōu)化，我們?cè)O(shè)想將街道離散化后變成一般性的圖論問(wèn)題，轉(zhuǎn)化為一個(gè)數(shù)學(xué)問(wèn)題進(jìn)行求解，并針對(duì)該問(wèn)題設(shè)計(jì)算法，給出結(jié)果，并進(jìn)行驗(yàn)證。 此工作正在進(jìn)行。 案例4：數(shù)獨(dú)的難度級(jí)別劃分問(wèn)題 美國(guó)數(shù)模競(jìng)賽2008年B題。開發(fā)一個(gè)產(chǎn)生數(shù)獨(dú)題目的算法，該算法能產(chǎn)生不同難度級(jí)別的數(shù)獨(dú)題目。要求首先定義數(shù)獨(dú)難度級(jí)別，并將其作為你產(chǎn)生不同難度級(jí)別數(shù)獨(dú)題目的

8、標(biāo)準(zhǔn)。你的算法和度量標(biāo)準(zhǔn)應(yīng)該具有可擴(kuò)展性，能夠很容易擴(kuò)展到更多難度級(jí)別。你至少用4個(gè)難度級(jí)別來(lái)進(jìn)行例證說(shuō)明。另外一定要保證你的數(shù)獨(dú)題目要具有唯一解。特別注意要分析你的算法的復(fù)雜性，并在滿足前面要求的條件下使算法復(fù)雜性達(dá)到最小。數(shù)獨(dú)基于規(guī)則的逐步枚舉算法設(shè)計(jì)。我們首先給出了數(shù)獨(dú)的6條性質(zhì)，并在此基礎(chǔ)上提出了幾條推理規(guī)則，然后結(jié)合空格填寫的一個(gè)一組，兩個(gè)一組及更多個(gè)一組的枚舉算法，在枚舉中進(jìn)行推理。使推理和枚舉結(jié)合起來(lái)，對(duì)有唯一解的數(shù)獨(dú)問(wèn)題，其求解速度比回溯法快得多，同時(shí)也能完成許多數(shù)獨(dú)軟件無(wú)法進(jìn)行推理計(jì)算的數(shù)獨(dú)難題。進(jìn)一步研究：將數(shù)獨(dú)問(wèn)題變成一個(gè)變量為0-1型的方程組，然后討論方程組的求解方法。給出方程的候選數(shù)刪除性質(zhì)、唯一確定性性質(zhì)、矛盾性