【問題描述】
　　高斯消元法適用的兩種情況為域上的問題和環(huán)上的問題。域上的問題就是可以通過加減乘除把系數(shù)陣化簡成為對角線全1的形式，是允許有除法的，一般用于浮點數(shù)的高斯消元。而環(huán)上的問題一般涉及整數(shù)以及取模，除法是不允許的，此外環(huán)上的問題一般都要涉及高斯消元的一個比較難處理的問題：無窮解問題。

【問題分析】
　　首先考慮比較簡單的環(huán)上的問題：模2問題，這類問題的經(jīng)典代表是開關(guān)燈問題。其實這類問題可以允許除法（用異或代替），每次消元的時候如果出現(xiàn)不確定的變量，那么跳過當前列，保持行不變，繼續(xù)消元。當消元過后會出現(xiàn)的問題是，如果系數(shù)陣的秩小于增光矩陣的秩，那么無解；或者不是所有的變量都已經(jīng)取值，導(dǎo)致這個的原因一個是消元時出現(xiàn)全0列，一個是系數(shù)陣的秩等于增光矩陣的秩且小于未知數(shù)的個數(shù)，也就是出現(xiàn)無窮解。在模2域上出現(xiàn)無窮解的時候只需枚舉每個不確定變元的值（0或1），一般是用來找到一個最優(yōu)解。這里一個比較巧妙的方法是保留消元過程的對角矩陣，這樣一旦確定了未知數(shù)，直接回帶找解，無需重新建立方程。
　　模n域上的無窮解問題更為復(fù)雜一些。一個是變元的取值范圍變大了（0到n-1，某些問題取值還會是負的），另一個問題是由于模n未必是素數(shù)，如果是素數(shù)存在解就一定唯一，不是素數(shù)的話會出現(xiàn)多組解，還得繼續(xù)枚舉才行。以幾個題目為例：
　　POJ 2947 Widget Factory：這是環(huán)上問題的基礎(chǔ)版，考察了對于變元數(shù)和方程數(shù)不確定的時候?qū)Ψ匠探鈹?shù)的判斷方法。消元的過程還是很簡單的，細節(jié)考慮清楚就可以了。
　　POJ 1395 Cog-Wheels：方程的建立很巧妙，由于數(shù)的范圍很小（100以內(nèi)），因此可以根據(jù)每個質(zhì)因數(shù)的冪次建立方程！對每個輪子除以最小的那個數(shù)后就可以進行質(zhì)因數(shù)分解，方程數(shù)很少；最后建立的是一個整系數(shù)方程。不過這里的問題是由于存在無窮解的情況，要搜索；而且變量的取值范圍不太好把握，我是取增廣陣的所有系數(shù)的最大值max，把枚舉的界定在了|max|以內(nèi)，有點像擴展歐幾里德的思想，如果有x、y滿足ax + by = d，那么x上下浮動b個，y上下浮動a個依然方程成立。另外注意的是建立方程的時候會產(chǎn)生齊次方程，要特別判斷一下。總而言之這個題目寫起來很惡心，復(fù)雜度感覺巨高，但是實際運行速度很快。
　　POJ 2055 Kid's Problem：這個題目BT程度又進了一步，是個模線性方程組，不僅可能存在無窮解，而且模不一定是素數(shù)，對于確定的變元取值也會很多，總之就是各種搜索。不過這個題目很無聊的一點是在消元過程中，之前我一直是取要消元的兩個系數(shù)的最小公倍數(shù)，分別放大然后再減去，就像分數(shù)通分的做法，做其他的題目都沒有問題（因為沒有影響解的情況）；但是這個題目這樣居然會超時，當然不是超時在高斯消元的過程，而是之后枚舉的過程。這個題目必須利用那種類似求gcd的方法，兩個方程互相減來減去，因為這個題目數(shù)據(jù)取值范圍太小了（20以內(nèi)），因此這樣做的復(fù)雜度也不高。這兩種做法的唯一區(qū)別就是后者消元后的對角陣中，主對角線的系數(shù)很小（減來減去減得很小），而用“通分”的方法系數(shù)會保留為原系數(shù)（可能很大），雖然最后計算的結(jié)果完全相同，但是可能后者能夠快速得到一個好的可行解，利用這個剪掉了不少冗余情況，而前者也許差了一些，就超時了。
　　Ural 1561 Winnie the Pooh：應(yīng)該是高斯消元問題的終極版本了，考察的是對高斯消元的理解（不過沒有在方程的建立上設(shè)置太多的坎）。這個題目可以歸結(jié)為包含若干操作的動態(tài)高斯消元問題：添加一個變元，添加一個方程，詢問給定方程解的情況。因為不是詢問方程組的解，而是詢問方程的解，這樣的話有可能雖然有多組解但是最后對應(yīng)方程的值是相同的。我一開始采用枚舉方程的取值判斷有解的方法，超時了；后來改成出現(xiàn)不確定解的時候搜索判斷解的情況，依然超時。這兩種方法的復(fù)雜度都達到O(n ^ 3)以上，所以需要好的辦法。仔細思考之后發(fā)現(xiàn)，如果方程有解且唯一，那么它一定和已經(jīng)存在的方程組（看成是向量）是線性相關(guān)的，這樣的話可以每次添加方程都維護對角陣，對于一次詢問，利用已有的方程組依次對給定的方程消元，到最后判斷這個方程的系數(shù)是否全0，如果是的話解個模方程就行了，如果不是的話說明這個方程的取值會有很多種情況。每次添加方程都判斷是否產(chǎn)生矛盾（無解），如果無解以后不再判斷，一直輸出無解。利用這種方式可以很快的處理查詢，每次復(fù)雜度才O(n ^ 2)。

【問題總結(jié)】
　　環(huán)上的高斯消元問題應(yīng)用比較廣泛，但是編碼的復(fù)雜度也比較高。此外，不同的題目往往要求各異，因此也沒有統(tǒng)一的模板，需要根據(jù)題目的要求來編寫程序。通過以上幾個題目的練習，對于高斯消元的求解已經(jīng)沒有太大的問題了。但是題目中方程的建立以及優(yōu)化求解依然是難點，需要不斷地積累和總結(jié)。

注：本文作于2009年7月3日20點整

<strike id="wuk4w"></strike>