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

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

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

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

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