1、IOI2003中國國家集訓(xùn)隊(duì)難題討論活動0058 研究報(bào)告清華附中 侯啟明【題目大意】【解決情況】證明了一般模線性方程組012解的存在性判定是NP-Hard的。文中算法的復(fù)雜度上限是O(3n)，下限是O(n3)，但實(shí)際運(yùn)行效果非常好?！舅惴ü８拧扛咚瓜?搜索【討論收獲與感謝】和張家琳和陶默雷兩位同學(xué)關(guān)于高斯消元和搜索的討論?！菊摹浚ㄓ捎诤隗w有表示向量的含義，所以本文中用紅色標(biāo)出重點(diǎn)）不妨設(shè)A*B=one，設(shè)Ai=ai，Bi= xi+1。得方程組：a0 x1+an-1x2+.+a1xnb1(mod Q)a1x1+a0 x2+.+a2xnb2(mod Q).an-1x1+an-2x2+.+a

2、0 xnbn(mod Q)現(xiàn)在，問題轉(zhuǎn)化成了判定這個(gè)方程組是否有012解（就是xi0，1，2）的解。如果將條件稍稍減弱一點(diǎn)，覺得到了上面所說的一般模線性方程組012解的存在性判定問題：判定是否存在xi0，1，2使得：a11x1+a12x2+.+a1nxnb1(mod Q)a21x1+a22x2+.+a2nxnb2(mod Q).an1x1+an2x2+.+annxnbn(mod Q)我也曾經(jīng)從這方面入手想過，但一直沒有想出什么結(jié)果，最后發(fā)現(xiàn)：這個(gè)問題是NP-Hard的。證明：對任意的01背包問題“判定是否存在yi0，1使得wiyi=M”： 令Q=2p（p為充分大的質(zhì)數(shù)），a11=1，a1i=5

3、wi-1（i2,n+1），b1=10M，bi=0（i2,n+1），aij=pij，（i2,n+1，j1,n+1）。下證原問題有解是模線性方程組：a11x1+a12x2+.+a1,n+1xn+1b1(mod Q)a21x1+a22x2+.+a2,n+1xn+1b2(mod Q).an+1,1x1+an+1,2x2+.+an+1,n+1xn+1bn+1(mod Q) 有012解的充要條件。n 充分性：n i =1 存在yi0，1使得wiyi=M i =1n 令x1=0，xi=2yi-1（i2,n+1）n i =1a1,i+1*xib1 i =1pxibi(mod Q) （i2,n+1） xi為原方

4、程一組012解，充分性得證 必要性： 原方程組有012解，5|b1-a12x2+.+a1,n+1xn+1=x1pxi0(mod Q) （i2,n+1） x1=0，xi0,2 （i2,n+1）n 令yi=xi+1/2n i =1 wiyi=M，yi0，1，原問題有解，必要性得證 i =1 證畢因此，通過和張家琳和陶默雷兩位同學(xué)的討論，我決定寫一個(gè)高斯消元+搜索的程序。在寫這個(gè)程序的過程中，我發(fā)現(xiàn)簡單搜索的效率很不理想，想到題目中的方程組有很強(qiáng)的性質(zhì)，于是我做了一些分析：為了分析簡便，把本題所涉及到的方程組寫成這種形式：在模Q加法的意義下定義群NQ=0,1,.,Q-1。定義NQ上的乘法運(yùn)算為模Q乘

5、法。以下如不特別說明，所有的字母均表示群NQ的元素，加法和乘法均表示群NQ中的運(yùn)算。 A1Xb1(mod Q)A2Xb2(mod Q).AnXbn(mod Q)n i =1其中A1=(a0,an-1,an-2,.,a1)，A2=(a1,a0,an-1,.,a1)，An=(an-1,an-2,.,a0)；b1=1；b2,b3,bn=0。定義(p1,p2,.,pn)(q1,q2,.,qn)= piqi（因?yàn)橄蛄靠臻gNQn不一定是一個(gè)線性空間，即使它是，這個(gè)運(yùn)算也不完全符合內(nèi)積的性質(zhì)，所以不能成為內(nèi)積）。n i =1可以得到一些結(jié)論：結(jié)論1：如果方程組有解，且iAi=0，那么i=0。nn證明：原方程

6、組有解nn i =1 i =1n i(AiX)= ibi i =1 i =1n i =1 (iAi)X=1 i =1 1=0n 令0=n，i=i-1。n i =1 iAi=0 i =1 n=1=0 同理，對任意的i，i=0結(jié)論2：如果方程組有解，且iAi=(b1,b2,.,bn)，k|Q，k|bi，那么k|i。證明：設(shè)Q=pk。原方程組有解，piAi=0pi=0k|i但是該結(jié)論目前只能用來判定無解，不能用來將k約去（因?yàn)榉匠蘫ax=kb(mod kc)與ax=b(mod c)等價(jià)，但與ax=b(mod kc)并不等價(jià)，所以約去k會改變該方程模的值而使得后面的高斯消元無法進(jìn)行下去）。加入這兩條結(jié)

7、論后的程序可以直接判定相當(dāng)多的無解情況，但是在很多數(shù)據(jù)面前卻敗下了陣來，比如我的自擬數(shù)據(jù)的第6個(gè)點(diǎn)。經(jīng)過分析發(fā)現(xiàn)，這類數(shù)據(jù)在高斯消元的過程中會產(chǎn)生大量的增根（而且這些增根基本都是0或2），因而使得搜索量呈指數(shù)膨脹；但是如果調(diào)整一下消元的順序，這類方程經(jīng)常變得簡單到能用手算解出來。因此，我加入了“啟發(fā)式消元”：如果能不產(chǎn)生增根地消掉xi，就不產(chǎn)生增根地消掉xi。加入這個(gè)優(yōu)化后，對絕大多數(shù)隨機(jī)數(shù)據(jù)都能很快出解（對n=20，q=4或6檢測了10000個(gè)隨機(jī)數(shù)據(jù)，n=4時(shí)耗時(shí)24s，n=6時(shí)耗時(shí)28.5s）。而且該程序在1000多個(gè)隨機(jī)小數(shù)據(jù)上通過了盲目搜索的驗(yàn)證，正確性應(yīng)該可以保證。在對官方數(shù)據(jù)進(jìn)行測試時(shí)發(fā)現(xiàn)：按照文中猜想寫的程序得到的結(jié)果和林希德同學(xué)所描述的一樣：第一個(gè)點(diǎn)有解，其它的點(diǎn)都是無解，與標(biāo)準(zhǔn)輸出有很大差異。改用解方程+搜索，結(jié)果依舊。最后用完全的盲目搜索驗(yàn)證了標(biāo)準(zhǔn)輸出為有解的最小的兩個(gè)點(diǎn)，發(fā)現(xiàn)標(biāo)準(zhǔn)輸出的確有誤，因此，只好靠自制數(shù)據(jù)來測試程序了?！具M(jìn)一步研究的方向】啟發(fā)式消元的效率分析，自制數(shù)據(jù)的互相驗(yàn)證?！緟⒖嘉墨I(xiàn)】代數(shù)與幾何自制數(shù)據(jù)說明：1巨大的“平凡”數(shù)據(jù)。24從10000個(gè)Q相同的隨機(jī)數(shù)據(jù)中挑出來的“佼佼者”（有解的）。5消元順序?qū)λ阉餍视绊?/p>