集訓(xùn)隊(duì)作業(yè)solution關(guān)系挖掘解題報(bào)告

1、關(guān)系挖掘 解題市復(fù)旦大學(xué)附屬中學(xué)April 10, 20111試題描述給定一張圖 = (, ) 與一個(gè)整數(shù) ，求出一個(gè) 的子集 ，使得| = ，最大化下述表達(dá)式(1)(,) and and 題本題為一道遞交2試題分析對于遞交題一般來說就是分析數(shù)據(jù)并且研究不同數(shù)據(jù)的特點(diǎn)并各個(gè)擊破，比較浪費(fèi)時(shí)間，建議選手應(yīng)該在再講。剛開始的時(shí)候完成，理由之后接下來我分類描述每個(gè)數(shù)據(jù)點(diǎn)我觀測到的數(shù)據(jù)特征：數(shù)據(jù)點(diǎn) 1 20，這樣的測試點(diǎn)只要搜索就能跑出完美解。數(shù)據(jù)點(diǎn) 2 1000，一條鏈，這樣的數(shù)據(jù)得到最優(yōu)解?？梢允褂面溕系膭?dòng)態(tài)規(guī)劃來數(shù)據(jù)點(diǎn) 3、4 一棵樹，對于這樣的測試數(shù)據(jù)可以使用樹上的動(dòng)態(tài)規(guī)劃（需要左兒子右兄弟表

2、示法或者二次 DP）較為繁瑣，不過這樣一下子拿 2、3、4 三個(gè)測試點(diǎn)都能拿到最優(yōu)解12試題分析數(shù)據(jù)點(diǎn) 5、6 二分圖，并且左側(cè)的的點(diǎn)數(shù)量很少，右側(cè)的點(diǎn)數(shù)量很多，測試點(diǎn) 6 的數(shù)據(jù)經(jīng)過打亂過。這些數(shù)據(jù)點(diǎn)可以通過狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃解決（遞交題，規(guī)模不是問題）。數(shù)據(jù)點(diǎn) 7、8 幾乎是完全圖，補(bǔ)圖中的邊特別少，好像補(bǔ)圖是很特殊的圖，可以直接構(gòu)造最優(yōu)解。數(shù)據(jù)點(diǎn) 9、10 貌似沒有規(guī)律，不過如果你對他們求一次最大密度子圖的話你會(huì)發(fā)展密度子圖中的點(diǎn)數(shù)與題目中所給定的點(diǎn)數(shù)是一樣，所求的必然是最優(yōu)解。所有數(shù)據(jù)都是可以通過針對程序跑出滿分來的，不過緊張的考場上分秒必爭，種題不可能有如此多的時(shí)間觀察數(shù)據(jù)并想出針對

3、算法的。對于這一般采取隨機(jī)調(diào)整的策略直接編寫針對所有測試點(diǎn)的程序。隨機(jī)調(diào)整很簡單，一上來隨便選取 個(gè)點(diǎn)，然后隨機(jī)改變其中的一個(gè)點(diǎn)，判斷是否更優(yōu)，如果更優(yōu)則保留，否則退回去。這樣重復(fù)很多很多次就能得到一個(gè)相對不錯(cuò)的解?？紙錾虾芏嗳硕歼@么寫，不過最后得分相差卻相差很多，當(dāng)時(shí)這題我考場上的得分算是挺高（不記得幾名了）的，我在所有的測試數(shù)據(jù)中使用的都是調(diào)整算法。這里介紹下調(diào)整算法的經(jīng)驗(yàn)。1.當(dāng)你發(fā)現(xiàn)隨機(jī)了很多很多次（設(shè)置一個(gè)常數(shù)）沒有更優(yōu)，應(yīng)該重新初始化一個(gè)初始解再調(diào)整，最后取最優(yōu)。2.算法的常數(shù)盡可能低，不要看是遞交題為了簡單就用速度很慢的算法，因?yàn)檫@種調(diào)整程序時(shí)要跑到比賽結(jié)束的。跑的時(shí)間盡可能長（

4、盡可能跑到結(jié)束），所以應(yīng)該在開3.始的時(shí)候做遞交題使得程序運(yùn)行時(shí)間最大化。4.同時(shí)跑 4 個(gè)以上的程序，機(jī)器是四核的，Linux 并行做的很不錯(cuò)，同時(shí)跑 4 個(gè)以上的程序并不會(huì)使機(jī)器太慢而影響你做其他題目。5.為了精確控制一個(gè)程序運(yùn)行的時(shí)間，應(yīng)該讓程序能響應(yīng) Ctrl-C鍵而不是設(shè)置一個(gè)固定的運(yùn)行常數(shù)（調(diào)常數(shù)很累而且不太準(zhǔn)）。響應(yīng)Ctrl-C 在 Linux 下就是響應(yīng) SIG信號(hào)，F(xiàn)ree Pascal 中有 UnixBase 庫可以調(diào)用，而 C 的話則是直接有 GlibC 的函數(shù)，大家可以參考 FreePascal 和 Man提供）冊與因特網(wǎng)以獲取的知識(shí)。（此方法由睿23總結(jié)3總結(jié)在考上應(yīng)對遞交題時(shí)應(yīng)該根據(jù)自己能力選擇