火災(zāi)、爆炸專項(xiàng)應(yīng)急預(yù)案 - 廣東省安全生產(chǎn)技術(shù)中心辦公系統(tǒng)

矩陣乘積可換的條件及應(yīng)用數(shù)計(jì)學(xué)院 劉艷萍摘 要：矩陣的乘法運(yùn)算一般不滿足交換律，但在特殊的條件下可交換。本文從可交換矩陣和相關(guān)定義出發(fā)，對(duì)可交換矩陣做了深入的探討，得到了矩陣可交換的一些條件和可交換矩陣的部分性質(zhì)，并且介紹可交換矩陣的應(yīng)用。關(guān)鍵詞：矩陣乘法；可交換條件；應(yīng)用 Interchangeable Conditions of the product of matricesand Its ApplicationsLiu Yanping(College of Mathematics and Computer Science, Guangxi University for Nationalities, Nanning 530006)Abstract: Generally the arithmetic of the matrix multiplication unconformity commutative law, but under special conditions they are interchangeable. In this paper, the interchangeable matrix is discussed, some conditions of the matrix exchange and part of the property of the interchangeable matrix are obtained, and the applications of the interchangeable matrix are introduced also. All of these are discussed from the concept of interchangeable matrix and related definitions. Key word: product of matrices; Interchangeable conditions; application1 引言及定義在高等代數(shù)學(xué)習(xí)中，矩陣是一個(gè)重要內(nèi)容，由矩陣的理論可知，矩陣的乘法不同于復(fù)數(shù)的乘法，矩陣的乘法運(yùn)算一般不滿足交換律，即對(duì)兩個(gè)方陣，在一般情形下。但在某些特殊情況下，矩陣的乘法也滿足交換律，這時(shí)我們稱是可交換矩陣。可交換矩陣有著許多特殊性質(zhì)和作用。本文從可交換矩陣定義及相關(guān)定義出發(fā)，探討矩陣可交換的一些條件和可交換矩陣的部分性質(zhì)，并介紹可交換矩陣的一些應(yīng)用。為研究矩陣可交換條件，我們先給出下列定義1。定義1 若同階方陣有，則稱方陣與為可交換矩陣.定義2 階方陣中若元素滿足，稱為階對(duì)角陣，記作.定義3 若階方陣滿足，其中為階單位陣，則稱為階正交矩陣.用表示的轉(zhuǎn)置矩陣；表示的伴隨矩陣2。2 矩陣乘積可交換的條件及性質(zhì)2.1 矩陣乘積可交換的條件定理1 設(shè)是的伴隨矩陣，則與乘積可交換.證明 由即知.定理2 （1）設(shè)，其中,為非零實(shí)數(shù)，則,可交換；（2）設(shè)，其中為正整數(shù)，為非零實(shí)數(shù)，則,可交換.證明 （1）由可得，即，得，于是，所以.（2）由得，故，于是，從而.定理33 設(shè), 均是階可逆矩陣, 若對(duì)任意實(shí)數(shù)，均有，其中為 階單位矩陣，則,可交換.定理4 設(shè)都是階矩陣，則下列均是可交換的充要條件：(1) ；(2) ； (3) ；(4) .證明 (1) 由及即得.(2) 由 可證得；(3) 因，兩端分別取它們的轉(zhuǎn)置，得，又，故.由矩陣運(yùn)算性質(zhì)及已知條件，即得，兩端分別取它們的轉(zhuǎn)置，得.(4) 分別由，兩邊取伴隨可證得.定理5 （1）設(shè)均為階(反)對(duì)稱矩陣，則可交換的充要條件是為對(duì)稱矩陣；（2）設(shè)為階對(duì)稱陣，為階反對(duì)稱陣，可交換的充要條件是為反對(duì)稱陣。證明 （1） 若均為階對(duì)稱矩陣，則 因 且，故，即為對(duì)稱陣。 因又，故，即為可交換矩陣。 若均為反對(duì)稱矩陣，則因且，故，即為對(duì)稱陣。因又，故，即為可交換矩陣。（2）因，故，即為反對(duì)稱陣。 因?yàn)榉磳?duì)稱陣, ，又，故，即可交換。定理6 設(shè)均為對(duì)稱正定矩陣，則可交換的充要條件是為對(duì)稱正定矩陣.證明 充分性顯然. 下面證明必要性。因?yàn)閷?duì)稱正定矩陣，故有可逆矩陣，使，于是，所以為對(duì)稱正定矩陣，其特征值全為正數(shù)。而與相似，從而 的特征值也全為正數(shù)，因此為對(duì)稱正定矩陣。定理7 設(shè)均為階矩陣，若滿足，則可交換的充要條件是.證明 因，故即. 由于，即,分別用左乘,右乘式的兩邊，得到，即.定理8 設(shè)是階方陣，則與任一階矩陣可換的充要條件是（數(shù)量矩陣）.證明 令是第行，第列處的元素為，其余元素為的階方陣，因與任一階矩陣可換，所以與所有可換，又(列)所以由的第行除外其余元素全為,，即除外，其余元素全為，故. 設(shè)，則對(duì)任意階矩陣，有.定理9 設(shè)矩陣，其中當(dāng)時(shí)，則可交換的充要條件是為對(duì)角矩陣.定理10 設(shè)為準(zhǔn)對(duì)角矩陣，其中當(dāng)時(shí)， ，是階單位矩陣，則可交換的充要條件是為準(zhǔn)對(duì)角矩陣.2.2 乘積可交換矩陣的性質(zhì)性質(zhì)1 設(shè)均為階可交換矩陣，則有(1),其中都是正整數(shù)；(2) 對(duì)任意正整數(shù)， (矩陣二項(xiàng)式定理)；(3) 平方差公式：；(4) 完全平方和（差）公式：；(5) 矩陣積的乘冪公式：（是正整數(shù)）.證明 （1）先證明對(duì)任意正整數(shù)，有，對(duì)作數(shù)學(xué)歸納法 當(dāng)時(shí)，由已知條件，即當(dāng)時(shí)結(jié)論成立；假設(shè)當(dāng)時(shí)結(jié)論成立，即，則當(dāng)時(shí)， ，故當(dāng)時(shí)結(jié)論也成立，由歸納法原理，對(duì)一切正整數(shù)，有；再證明， 對(duì)作數(shù)學(xué)歸納法. 當(dāng)時(shí)，由上面結(jié)論知，即當(dāng)時(shí)結(jié)論成立；假設(shè)當(dāng)時(shí)結(jié)論成立，即，則當(dāng)時(shí)，故當(dāng)時(shí)結(jié)論也成立；由歸納法原理，對(duì)一切正整數(shù)，有 .(2) 對(duì)作數(shù)學(xué)歸納法.當(dāng)時(shí) 當(dāng)時(shí)，由，有即當(dāng)時(shí)結(jié)論成立；假設(shè)當(dāng)時(shí)結(jié)論成立，即 ，當(dāng)時(shí)， .（倒數(shù)第三式到第二式利用了組合的性質(zhì)：，及，）即當(dāng)時(shí)結(jié)論也成立。從而由歸納法原理，對(duì)任意正整數(shù)，有= .(3)(5) 較明顯，證明從略.性質(zhì)24 設(shè)是階復(fù)矩陣，則存在一個(gè)階可逆矩陣，使得與同為上三角矩陣.證明 對(duì)的階數(shù)作數(shù)學(xué)歸納法。當(dāng)時(shí)，結(jié)論顯然成立。假設(shè)結(jié)論對(duì)于階矩陣也成立。當(dāng)?shù)碾A數(shù)為時(shí)，由于，至少有一個(gè)公共的特征向量設(shè)將擴(kuò)充為的一組基(均為列向量). 設(shè) (1) (2)由得于是，由歸納法假設(shè)，存在階可逆矩陣使得 ，令，由（1）,（2）兩式得,令則.3 可交換矩陣的應(yīng)用3.1 利用矩陣可交換性,求矩陣的方冪例1 計(jì)算, 是正整數(shù).解 設(shè), 由于,因?yàn)榕c可交換，所以由二項(xiàng)式定理得 ,即.例2 計(jì)算 , 是正整數(shù).解 設(shè), 因?yàn)?又因?yàn)榕c可交換，所以由二項(xiàng)式定理得 即.例3 計(jì)算 是正整數(shù).解 設(shè), 因?yàn)?所以當(dāng)時(shí)，又和是可交換的，所以由二項(xiàng)式定理得， 即.例4 設(shè) 對(duì)任意正整數(shù)，求.解 令 則，又，設(shè)故利用矩陣乘法的結(jié)合律得其中從而，因此 注意到：移項(xiàng)，得從而有，所以即的主對(duì)角線上的元均為而其余元素均為.從以上各例的求解過程中，我們可以看到此種類型的題的解法都是把復(fù)雜的矩陣變成兩個(gè)可交換矩陣的和，再利用二項(xiàng)式定理，求出最后結(jié)果。而在將一個(gè)矩陣分解成兩個(gè)矩陣的和時(shí)，這兩個(gè)矩陣最好簡單點(diǎn)，它們中至少有一個(gè)矩陣的某次冪為零矩陣，這樣再運(yùn)用二項(xiàng)式定理算矩陣次冪就非常簡單了。3.2 利用矩陣可交換性,證明某些問題例5 （2002年浙江大學(xué)碩士生入學(xué)考試試題）設(shè)是階復(fù)矩陣，其中是冪零矩陣而且，求證：.證明 由于，由性質(zhì)2，存在階可逆矩陣，使得同為上三角矩陣，又是冪零矩陣，故其特征值全為零. 于是，有，從而.故.例6 （2001年浙江大學(xué)碩士生入學(xué)考試試題）設(shè)是數(shù)域上階矩陣且，求證：秩 秩秩秩.證明 設(shè)秩，秩. 由于，由性質(zhì)2，存在階可逆矩陣，使得 與同為上三角矩陣，即不妨設(shè)則 從而，秩秩秩秩.參考文獻(xiàn) 1 北京大學(xué)數(shù)學(xué)力學(xué)系幾何與代數(shù)教研室代數(shù)小組. 高等代數(shù)M . 北京:人民教育出版社,1978. 2 北京大學(xué)數(shù)學(xué)系. 高等代數(shù)(第三版) M. 高等教育出版社,2003. 3 韓錦揚(yáng). 矩陣乘法AB = BA 成立的兩個(gè)充要條件與一個(gè)充分條件J . 工科數(shù)學(xué),1995 ,11:169-170. 4 曾梅蘭. 線性變換及矩陣可交換的性質(zhì)與應(yīng)用J. 孝感學(xué)院學(xué)報(bào),2006,26:44-46. 306關(guān)于等冪和的一個(gè)新性質(zhì)數(shù)計(jì)學(xué)院 李彬瑜摘要：等冪和是一個(gè)歷史悠久的古老難題 ，曾有許多人進(jìn)行了研究，它們?cè)跀?shù)論中有著重要的作用，本文運(yùn)用同余原理和數(shù)論的方法來探討等幕和的一個(gè)新的性質(zhì)。證明了p為奇素?cái)?shù)，m為奇數(shù)時(shí)，獲得了的值;當(dāng)p為奇素?cái)?shù),與m奇偶相異時(shí)，獲得了，并證明了的解為無限集。關(guān)鍵詞：等冪和 同余 數(shù)學(xué)競賽 整除And so on and the power of a new nature Li Bin-yu(Guangxi University for Nationalities Institute of Mathematics and Computer Science of the 04 (2) classes Nanning, Guangxi 530006)Instructor: Wang Yunkui Abstract: such as power and is a long history of the ancient problems, there have been many people were studied, in a few of them plays a significant role in this, with more than principle, the use of several methods, such as screen and to explore a new nature . P surprising that the number of m is odd, given the value of the definition of ，when p is the odd prime, and m parity differences, as well as the definition of the given proof of the is the model for the solution of unlimited Set.Key words: Idempotent sum, Congruence,Mathematics Olympiad, divisibility§1.等冪和與數(shù)學(xué)競賽問題等冪和 （1）是一個(gè)歷史悠久的古老難題。自從2000年前的希臘數(shù)學(xué)家阿基米德開，就吸引了國內(nèi)外數(shù)學(xué)家的研究興趣。1984年以后，陳景潤與黎鑒，王云等人對(duì)此作了大量的貢獻(xiàn)。至今仍有不少數(shù)學(xué)家在研究，很多方法不斷涌現(xiàn)。究其原因，不僅是因?yàn)榈葍绾妥鳛榧?jí)數(shù)求和的典范，更重要的是，它的數(shù)論性質(zhì)對(duì)波文猜想、居家猜想與素?cái)?shù)判別等問題有著非常重要的作用，而且在研究方法上有很強(qiáng)的靈活性，又可為開拓創(chuàng)新思維的寶地，在各國數(shù)學(xué)竟賽中也常常有與此有關(guān)的題目.1993年中國數(shù)學(xué)奧林匹克國家隊(duì)選拔考試的第一題是：對(duì)素?cái)?shù)p 3，定義 （2） 求的值。 其實(shí)解決這個(gè)問題的實(shí)質(zhì)是利用等冪和的整除性，求出對(duì)模的剩余，然后再帶入題目中給定義的式子即可。本文除了解決了數(shù)學(xué)競賽這一問題外，還由此進(jìn)一步將推廣到及 的研究。§2.引理引理 設(shè)m為奇數(shù)，則有： （4）證明； 一方面，由首尾配對(duì)有 （5） 由于m為奇數(shù)，故有，故由（5）式有 另一方面，再由首尾配對(duì)有： （6） 同理 又由 于，故 引理 若p為素?cái)?shù)，m、n，pn，則 （7）證明：設(shè)， 當(dāng)時(shí)，由費(fèi)爾馬小定理有：當(dāng)時(shí)而，故所以同理有 而當(dāng)時(shí)， ，則有 當(dāng)時(shí)，設(shè)為模的一個(gè)原根，則 故 同理，結(jié)合有引理 若m為奇數(shù)，則有 （8） （9） 證明： 由等冪和的定義有 故有這就獲得了（8）式，再在（8）式模即得（9）式。引理4 若m為偶數(shù)，則有 （10）證明：由上式即得：引理5 當(dāng)m、n均為自然數(shù)時(shí)，則有： （11）證明：當(dāng)n時(shí)， 當(dāng)n時(shí)，§3.定理定理1 設(shè)p為奇素?cái)?shù)，m 為奇數(shù)，則有 。 證明：因?yàn)閙為奇數(shù)，則根據(jù)引理1有 故定理2 設(shè)p為奇素?cái)?shù)，m為偶數(shù)，則有 （12） （13）證明： 由引理2有 （14） （15） 定理3 設(shè)p為奇素?cái)?shù)，m為奇數(shù)，若 則有： （16）證明：當(dāng)m=1時(shí)， 則 當(dāng)時(shí)由引理2 有 又由引理3中式 有 故 綜合、可得： 定理 4 設(shè)p>3素?cái)?shù)，定義 （17） 證明： S為無限集。 證明：令 由費(fèi)爾馬小定理有 而故即得S為無限集。§4.數(shù)學(xué)競賽問題的解決 由題可設(shè)對(duì)每一個(gè)素?cái)?shù)p，存在一個(gè)原根g，使得構(gòu)成模p的一個(gè)完全剩余系。根據(jù)定理1有： 若，則 ；若，即，則故§5.結(jié)語 到目前為止很多人都對(duì)等冪和的性質(zhì)我有關(guān)算計(jì)進(jìn)行了大量的研究，并取得了豐碩的成果。本文雖然獲得了一些結(jié)果，但是仍有許多問題沒有改進(jìn)和開發(fā)，尚待繼續(xù)研究。如當(dāng)m為偶數(shù)時(shí)，定理3有何類似結(jié)果？定理5中如果是變?yōu)闀r(shí)能否求出m的的全部解等等。因此我還將繼續(xù)努力，尋找解決的方法。參考文獻(xiàn)：1陳景潤,黎鑒愚關(guān)于冪和問題的進(jìn)一步研究.J科學(xué)通報(bào)，1985,30(17):1381 -13842陳景潤，黎鑒愚關(guān)于等冪和問題.J科學(xué)通報(bào)，1985,30(4):316317.3 陳景潤，黎鑒愚關(guān)于冪和公式的一般性質(zhì).J數(shù)學(xué)研究與評(píng)論，1986,(1):43-50.4王云葵，等幕和與bernoulli數(shù)的通解公式.J.廣西大學(xué)學(xué)報(bào)，1999,24(4):31 8-3205 王云葵.伯努利數(shù)與波文猜想.廣西民族學(xué)院學(xué)報(bào)(自然科學(xué)版). 1999. 5. (3)6 王云葵.等冪和研究及其新進(jìn)展.玉林師專學(xué)報(bào)，1994,15(3):4-107 王云葵.等暴和與居加猜想.數(shù)學(xué)通訊.1992,(11):43-448 王云葵. 等冪和的分解及同余式鏈. 天中學(xué)刊.1999 .14(5):9 王云葵. 等冪和與判別素?cái)?shù)的充要條件.數(shù)學(xué)通報(bào).1996,(6):46-4710 王云葵. 等冪和與波文猜想.廣西教育學(xué)院學(xué)報(bào).1998.(1):104-111一種新的掃描線種子填充算法數(shù)計(jì)學(xué)院 黃小果摘 要：為了解決經(jīng)典掃描線種子填充算法存在的重復(fù)掃描、棧操作頻繁等問題，本文提出一種新的掃描線種子填充算法。新算法取掃描線上每個(gè)填充區(qū)域的中點(diǎn)作為種子入棧，在不增加棧數(shù)據(jù)結(jié)構(gòu)的前提下，通過一定的策略，使得每個(gè)出棧的種子能最大限度地往上和往下進(jìn)行單向填充。新的算法設(shè)計(jì)巧妙，充分利用了區(qū)域連通的性質(zhì)和圖形像素分布的特點(diǎn)，極大地減少重復(fù)掃描的次數(shù)和入棧的種子數(shù)量，從而節(jié)約了資源并使得填充速度得到了很大的提高。關(guān)鍵詞：區(qū)域填充，連通區(qū)域，種子，種子填充算法A New Scan Line Seed Filling AlgorithmHuang XiaoguoGuangxi University for Nationalities College of Mathematics and Computer Science Nanning 530006Email:huangxgiq120Abstract: In order to solve the problem of the classic line scanning seed filling algorithm, such as repeat scan, stack operation frequently, this paper presents a new algorithm. New algorithm pushes the midpoint of the region as a seed into stack, at no additional stack data structure, under the premise through a strategy to make each stack of seed to maximize the bottom-up and down to One-way filled. The design of the new algorithm is very clever, and makes full use of regional connectivity to the nature and characteristics of the distribution of pixel graphics, greatly reducing the number of repeat scan and the number of seeds in the stcak, thus saving resources and making filling speed has been greatly improved.Keywords：regional filling，regional connectivity，Seed，Seed filling algorithm0 引言在圖形學(xué)的應(yīng)用中，常常要在指定的區(qū)域內(nèi)填充上填充顏色或圖案，即區(qū)域填充。如何高效地進(jìn)行填充是填充算法要解決的重要問題。種子填充算法是區(qū)域填充的一種重要方法，在實(shí)際中得到了廣泛地運(yùn)用。種子填充算法的基本思想是從一個(gè)封閉區(qū)域內(nèi)部的一個(gè)已知像素出發(fā)，通過某種方法找到區(qū)域內(nèi)的所有像素，從而進(jìn)行填充。常用的種子填充算法有：簡單種子填充算法和掃描線種子填充算法。簡單種子填充算法可以采用遞歸算法【2】，這種算法的原理和程序都很簡單，但由于多次遞歸和占用大量資源，填充質(zhì)量非常差。為此，可以采用棧結(jié)構(gòu)來實(shí)現(xiàn)簡單的種子填充算法【1】。其基本原理是：種子像素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步驟操作：（1）棧頂像素出棧；（2）將出棧像素置成多邊形色；（3）按左、上、右、下順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界且未置成多邊形色，則把該像素入棧。9653S1111114728圖1 S出棧后，像素4、7、9等出現(xiàn)了重復(fù)入棧。如圖1所示，S出棧后，其間出現(xiàn)了重復(fù)入棧的冗余。并且，這種算法仍然需要很大的存儲(chǔ)空間以實(shí)現(xiàn)棧結(jié)構(gòu)，所花費(fèi)的時(shí)間也較多。經(jīng)典掃描線種子填充算法也是為解決上述問題而提出的一種重要方法。此外，一些專家提出了基于鏈隊(duì)的種子填充算法【3】，有效地解決了重復(fù)入棧的問題，在此不再贅述。這里需要指出的一個(gè)概念是區(qū)域的連通性。區(qū)域的連通性是指從區(qū)域上的一點(diǎn)出發(fā)，通過幾個(gè)方向移動(dòng)的組合，在不超出區(qū)域的前提下，達(dá)到區(qū)域的任意像素。如圖2和圖3所示，區(qū)域可以分為四向連通區(qū)域和八向連通區(qū)域兩種。本文的討論基于四連通區(qū)域，即從區(qū)域上的一點(diǎn)出發(fā)，通過上、下、左、右移動(dòng)的組合，達(dá)到區(qū)域的任何像素。 圖2 四向連通 圖3 八向連通1 經(jīng)典算法的描述與分析1.1經(jīng)典算法描述假定填充區(qū)域邊界像素顏色為boundary_color，區(qū)域要填充的顏色為fill_color。經(jīng)典掃描線種子填充算法的原理是將種子像素入棧，當(dāng)棧非空時(shí)做以下4步操作。步驟1：棧頂像素出棧。步驟2：對(duì)包含出棧像素的整個(gè)區(qū)間進(jìn)行填充。步驟3：上述區(qū)間的最左、右記為xl和xr。步驟4：在區(qū)間檢查與當(dāng)前掃描線相鄰的上下兩條掃描線的有關(guān)像素是否全為邊界像素或已填充的像素，若存在非邊界，未填充的像素，則把每一區(qū)間的最右或最左像素取為種子像素入棧。1.2經(jīng)典算法分析經(jīng)典算法采取的方法是在任意一條掃描線與多邊形的相交區(qū)間（含若干連續(xù)像素）中，只取一個(gè)像素作為種子入棧。顯然，經(jīng)典算法減少了入棧的種子數(shù)量，節(jié)省了存儲(chǔ)空間。但是對(duì)經(jīng)典算法更進(jìn)一步地分析，我們可以發(fā)現(xiàn)經(jīng)典算法存在以下不足：1、重復(fù)掃描。為了對(duì)當(dāng)前線段填色和將上、下線段的種子入棧，需要對(duì)當(dāng)前線段，上下掃描線進(jìn)行掃描。在這個(gè)過程中會(huì)使得某些線段被重復(fù)掃描3次，這降低了程序的效率和運(yùn)行速度。2、出現(xiàn)漏填。由于未遵循經(jīng)典算法，出現(xiàn)了漏填現(xiàn)象。文獻(xiàn)4認(rèn)為經(jīng)典算法會(huì)出現(xiàn)漏填，這是錯(cuò)誤的。3、棧操作頻繁。在對(duì)與當(dāng)前掃描線相鄰的上、下掃描線進(jìn)行種子搜索時(shí)，每搜到一個(gè)填充區(qū)域，就要將種子入棧；同時(shí)每次開始對(duì)另一行搜索時(shí)都要先出棧。這樣則占用了大量的存儲(chǔ)空間，降低了效率。對(duì)于問題1和2的改進(jìn)，專家們提出了許多行之有效的方法。例如文獻(xiàn)5定義了如下新的結(jié)構(gòu)體：typedef struct node int dx,dy,left,right,oldleft,oldright,flag; struct node *next;其中，dx，dy是種子坐標(biāo)；flag為方向標(biāo)志，取值+1和-1。作者根據(jù)flag的值進(jìn)行單向填充，避免了重復(fù)掃描。顯然，文獻(xiàn)5在種子棧中加入了一些變量，使棧結(jié)構(gòu)變得復(fù)雜。此外，棧操作頻繁的問題還沒有解決。2 新掃描線種子填充算法的描述與分析2.1算法的描述假定給定區(qū)域邊界像素顏色為boundary_color，區(qū)域要填充的顏色為fill_color。將種子像素（x,y）入棧，當(dāng)棧非空時(shí)執(zhí)行以下操作：步驟1：棧頂像素出棧。步驟2：對(duì)包含棧頂像素的整個(gè)區(qū)間進(jìn)行填充，并記下區(qū)間的最左、右值xl_old和xr_old，xl=xl_old，xr=xr_old；步驟3：向上填充。判斷棧頂像素的上一個(gè)像素是否為邊界且未填充。若不為邊界且尚未填充，填充包含（x,y+1）的整個(gè)區(qū)間，并并更新xl和xr作為區(qū)間的最左、右值。判斷是否有回溯，若有則回溯，確定種子并將其入棧。將（x,y+1）看成棧頂像素，繼續(xù)執(zhí)行步驟3；否則，尋找下一個(gè)種子入棧，之后轉(zhuǎn)入步驟4。步驟4：向下填充。判斷棧頂像素的下一個(gè)像素是否為邊界且未填充。若不為邊界且尚未填充，填充包含（x,y-1）的整個(gè)區(qū)間，并更新xl和xr作為區(qū)間的最左、右值。判斷是否有回溯，若有則回溯，確定種子并將其入棧。將（x,y-1）看成棧頂像素，繼續(xù)執(zhí)行步驟4；否則，尋找下一個(gè)種子入棧，之后轉(zhuǎn)入步驟5。步驟5：結(jié)束判斷。如果種子棧為空，則算法結(jié)束；否則，轉(zhuǎn)入步驟1。2.2算法的圖示： 圖4 圖5 填充圖示 種子棧圖示 2.3算法的分析：2.3.1種子棧的數(shù)據(jù)結(jié)構(gòu)：class QNode public:QNode();virtual QNode();public:POINT data;QNode *Next;其中，data記錄種子的坐標(biāo)，next為下一個(gè)種子。比起文獻(xiàn)5，新算法種子棧的數(shù)據(jù)結(jié)構(gòu)無須增加變量，更加簡單明了。2.3.2算法的一些細(xì)節(jié)與處理：（1）關(guān)于算法步驟3和4中如何確定下一個(gè)種子：在這里筆者采用的方法是：將填充區(qū)域的中點(diǎn)入棧。代碼如下：if(xl=xr) && p_viewClientDC->GetPixel(xl,y)!=fill_color &&p_viewClientDC->GetPixel(xl,y)!=boundary_color)p.x=int(x+xl)/2);/p.x=xl;p.y=y;stackpush(p);elsep.x=int(x+xl-1)/2);/p.x=xl-1;p.y=y;stackpush(p);其中“p.x=int(x+xl-1)/2);”代碼段就是確定區(qū)域中點(diǎn)。這樣將能使每個(gè)種子能最大限度的往上或者往下填充，大大的減少了入棧的種子數(shù)量和節(jié)省了大量的時(shí)間。（2）回溯問題。 圖6 向上填充時(shí)可能出現(xiàn)回溯的情況向上填充：如圖6所示，同一條掃描線上出現(xiàn)多個(gè)填充區(qū)域時(shí)，可能需要回溯，否則會(huì)出現(xiàn)漏填。假設(shè)xl_old,xr_old為上條掃描線填充區(qū)域，xl,xr為當(dāng)前掃描線的填充區(qū)域。當(dāng)xl<xl_old-2，xr>xr_old+2，xr+2<xr_old，xl-2>xl_old時(shí)，則會(huì)出現(xiàn)回溯。此時(shí)，我們采取的辦法是：取xl,xl_old-2，xr_old+2,xr，xr+2,xr_old，xl_old,xl-2的中點(diǎn)作為種子入棧。向上填充時(shí)，回溯問題的c+語言如下：if(xl<xl_old-1)/if()語句，判斷是否出現(xiàn)“回溯”，若回溯則尋找種子入棧。seek_seed(xl,xl_old-2,y0-1,fill_color,boundary_color);if(xl-1>xl_old)seek_seed(xl_old,xl-2,y0,fill_color,boundary_color);if(xr>xr_old+1)seek_seed(xr_old+2,xr,y0-1,fill_color,boundary_color);if(xr+1<xr_old)seek_seed(xr+2,xr_old,y0,fill_color,boundary_color);同樣，向下填充時(shí)，以下情況會(huì)出現(xiàn)回溯：圖7 向下填充時(shí)可能出現(xiàn)回溯的情況此時(shí)，我們?nèi)l,xl_old-2，xl_old,xl-2，xr_old+2,xr，xr+2,xr_old的中點(diǎn)入棧。解決回溯的C+語言如下：if(xl<xl_old-1)seek_seed(xl,xl_old-2,y0+1,fill_color,boundary_color);if(xl-1>xl_old)seek_seed(xl_old,xl-2,y0,fill_color,boundary_color);if(xr>xr_old+1)seek_seed(xr_old+2,xr,y0+1,fill_color,boundary_color);if(xr+1<xr_old)seek_seed(xr+2,xr_old,y0,fill_color,boundary_color);2.3.3新算法的特點(diǎn)：取掃描線上每個(gè)填充區(qū)域的中點(diǎn)作為種子入棧，每個(gè)出棧的種子都盡可能地往上或往下單向填充；從微觀處了解像素點(diǎn)的分布情況，有效地解決了回溯的問題。2.3.4新算法的優(yōu)點(diǎn)：新的算法大大地減少了種子入棧的數(shù)量和重復(fù)掃描的次數(shù)，從而節(jié)省了資源，提高了效率。2.3.5新算法的不足：新的算法雖然大大地減少了重復(fù)掃描的次數(shù)，但還不能完全消除重復(fù)掃描。除第一個(gè)種子外，其余出棧的種子往上或往下掃描時(shí)，會(huì)出現(xiàn)一次的重復(fù)掃描。如圖4中的S2，當(dāng)它出棧時(shí)還要掃描上面一條掃描線，但上面一條掃描線已經(jīng)掃描過了，所以出現(xiàn)了重復(fù)掃描。3 新算法與經(jīng)典算法的一些數(shù)據(jù)比較：筆者在Visual C+平臺(tái)上對(duì)新的算法與經(jīng)典算法進(jìn)行比較。如圖8所示，填充帶圓形孔(R=100像素)的矩形填充區(qū)域（邊長a=600像素）；如圖9所示，填充帶有任意孔的連通區(qū)域。試驗(yàn)結(jié)果表明新的算法不會(huì)出現(xiàn)漏填、錯(cuò)填等現(xiàn)象。 圖8 帶圓孔的矩形填充區(qū)域 圖9 帶孔的任意連通區(qū)域帶圓孔的矩形填充區(qū)域（圖8）帶任意孔的連通區(qū)域（圖9）填充像素填充時(shí)間入棧像素填充像素填充時(shí)間入棧像素經(jīng)典算法【1,2】32633617s799486283s909新算法3263364s34486281s不大于404 結(jié)束語表面上看，新算法似乎比經(jīng)典算法復(fù)雜。其實(shí)不然，只是新的算法設(shè)計(jì)更巧妙罷了。新算法在沒有增加棧的數(shù)據(jù)結(jié)構(gòu)的情況下，使得每個(gè)出棧的種子都盡可能地往上或往下單向填充，省去了經(jīng)典算法尋找種子，進(jìn)而進(jìn)棧、出棧等繁雜的操作過程，減少了重復(fù)掃描和入棧的種子數(shù)量，從而節(jié)省了大量的運(yùn)算時(shí)間和大量的存儲(chǔ)空間。雖然新的算法沒有完全的消除重復(fù)掃描，但比起經(jīng)典算法，重復(fù)掃描的次數(shù)已經(jīng)大大減少，幾乎可以忽略不計(jì)。大量實(shí)驗(yàn)證明，新算法在填充時(shí)間、入棧像素等方面有了巨大的進(jìn)步，比起經(jīng)典算法具有更大的優(yōu)越性。參考文獻(xiàn)：1孫家廣 等,計(jì)算機(jī)圖形學(xué)(第三版)M.北京：清華大學(xué)出版社,1999.2張曦煌，杜俊俐.計(jì)算機(jī)圖形學(xué)M.北京：北京郵電大學(xué)出版社,2007.3陳元琰，陳洪波.一種基于鏈隊(duì)的種子填充法J,廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,9：3033. 4李桂清，李陶深.掃描線種子填充算法的問題及改進(jìn)J,廣西大學(xué)學(xué)報(bào)(自然科學(xué)版),1998,9：207211.5孫燮華.掃描線種子填充算法的改進(jìn)J.計(jì)算機(jī)工程,2000,12：142143.基于蟻群算法的多目標(biāo)運(yùn)輸問題優(yōu)化算法的研究數(shù)計(jì)學(xué)院 黃富平摘要 蟻群算法是一種嶄新的仿生模擬進(jìn)化算法，該算法在許多領(lǐng)域已經(jīng)得到應(yīng)用。多目標(biāo)運(yùn)輸問題是一類很重要的優(yōu)化問題，優(yōu)化與求解較難。對(duì)此，提出了一種改進(jìn)蟻群算法用于求解多目標(biāo)運(yùn)輸問題，得到一組變量的權(quán)重后，用一定數(shù)量的螞蟻在解空間中首先隨機(jī)搜索，然后模擬螞蟻尋食的方式，通過信息素來指引搜索。關(guān)鍵詞：多目標(biāo)優(yōu)化；運(yùn)輸問題；蟻群算法Research of Multi-Objective Transportation Problem OptimizationAlgorithm Based on Ant Colony AlgorithmAbstract Ant Colony Algorithm is a brand-new bionic simulated evolutionary algorithm, whichhas been applied to many fields. Multi-objective transportation problems are very important optimization problems. Its hard to optimized or solved. An improved Ant Colony Algorithm to solve Multi-objective transportation problems is introduced. After setting up a set of weight for the parameters, the algorithmuses uses some ants search in the solution space first in a stochastic way then stimulate the food searching behavior of real ants to guide the search by the pheromone. Keywords：Multiobjective optimization；Transportation problem；Ant colony algorithm1.引言 隨著運(yùn)輸網(wǎng)絡(luò)的發(fā)展和貨運(yùn)量的增加，運(yùn)輸調(diào)度問題變得越來越復(fù)雜。以總運(yùn)費(fèi)最小為優(yōu)化目標(biāo)的單目標(biāo)優(yōu)化模型得到的解，往往并不是決策者最滿意的解，人們希望得到的是多目標(biāo)的最優(yōu)解。目前，涌現(xiàn)出許多求解多目標(biāo)優(yōu)化問題的算法，如交互式多目標(biāo)優(yōu)化、模糊規(guī)劃法 、遺傳算法、表上作業(yè)法等，但遺傳算法是目前人們用來求解該類問題的主要方法。蟻群算法作為一種新的仿生類進(jìn)化算法是由Dorigo首先提出的, 該算法模仿螞蟻覓食時(shí)的行為, 按照啟發(fā)式思想, 通過信息傳媒 費(fèi)洛(Pheromone) 的誘導(dǎo)作用, 逐步收斂到問題的全局最優(yōu)解。蟻群算法自問世以來表現(xiàn)出了強(qiáng)大的生命力, 較之以往的啟發(fā)式算法不論在搜索效率上, 還是在算法的時(shí)間復(fù)雜度方面都取得了令人滿意的效果。 該算法已被其他領(lǐng)域的專家所接受, 并運(yùn)用到諸如工件排序、圖著色、車輛調(diào)度、大規(guī)模集成電路設(shè)計(jì)、通信網(wǎng)絡(luò)中的負(fù)載平衡問題等許多方面。本文嘗試將蟻群算法用于多目標(biāo)運(yùn)輸問題, 因?yàn)橄伻核惴ň哂凶吭降碾S機(jī)搜索尋優(yōu)能力,而多目標(biāo)運(yùn)輸問題非常適合蟻群算法的適用領(lǐng)域。這兩方面結(jié)合必將在多目標(biāo)運(yùn)輸問題的研究中取得較滿意的結(jié)果。2. 蟻群系統(tǒng)模型介紹 據(jù)昆蟲學(xué)家的觀察和研究發(fā)現(xiàn)，生物世界中的螞蟻有能力在沒有任何可見提示下找出從其窩巢至食物源的最短路徑，并能隨環(huán)境的變化而變化適應(yīng)性地搜索新的路徑，作出新的選擇。作為昆蟲的螞蟻在尋找食物源時(shí)，能在其走過的路徑上釋放一種螞蟻特有的分泌物-信息素，使得一定范圍內(nèi)的其它螞蟻能夠察覺到并由此影響它們以后的行為。當(dāng)一些路徑上通過的螞蟻越來越多時(shí),其留下的信息素軌跡也越來越多，以致信息素強(qiáng)度增大(當(dāng)然隨時(shí)間的推移會(huì)逐漸減弱) ，后來螞蟻選擇該路徑的概率也就越高，從而增加該路徑的自催化行為。由于其原理是一種正反饋機(jī)制,因此，可將蟻群理解成所謂的增強(qiáng)型學(xué)習(xí)系統(tǒng).蟻群算法就是源于這種智能協(xié)作行為的算法。作為一種通用型隨機(jī)優(yōu)化方法，它吸收蟻群中螞蟻的行為特性,通過其內(nèi)在搜索機(jī)制，在一系列困難的組合優(yōu)化問題求解中取得成效。由于在模擬仿真中使用的是人工螞蟻概念，因此有時(shí)亦稱為蟻群系統(tǒng)。 以求解n個(gè)城市TSP的問題為例來說明蟻群系統(tǒng)模型。為了模擬實(shí)際螞蟻的行為，m表示蟻群中螞蟻的數(shù)量，表示城市i和城市j之間距離，表示t時(shí)刻位于城市i的螞蟻個(gè)數(shù)，。表示t時(shí)刻在ij連線上殘留的信息量。在初始時(shí)刻,設(shè)(c是常數(shù)),各條路徑上的信息量相等。螞蟻k()在運(yùn)動(dòng)過程中,根據(jù)各條路徑上的信息量決定移動(dòng)方向。表示在t時(shí)刻螞蟻由位置i轉(zhuǎn)移到位置j的概率:其中,表示螞蟻k下一步允許選擇的城市；、分別表示螞蟻在運(yùn)動(dòng)過程中所積累的信息及啟發(fā)式因子在螞蟻路徑選擇中所起的不同作用。與真實(shí)蟻群系統(tǒng)不同,人工螞蟻系統(tǒng)具有一定的記憶功能。這里用來記錄螞蟻k目前已經(jīng)走過的城市。隨著時(shí)間的推移,以前留下的信息逐漸消逝。用參數(shù)表示信息消逝的程度,經(jīng)過n個(gè)時(shí)刻,螞蟻完成一次循環(huán)。各路徑上的信息量根據(jù)下式作調(diào)整:表示第k只螞蟻在本次循環(huán)中留在路徑ij上的信息量,表示本次循環(huán)中留在路徑ij上的信息量:式中,Q是常數(shù)；是第k只螞蟻在本次循環(huán)中所走過路徑的長度。在初始時(shí)刻,其中, 。表示由城市i轉(zhuǎn)移到城市j的期望 程度,可以根據(jù)某種啟發(fā)算法具體確定。根據(jù)具體算法的不同,及的表達(dá)形式可以不同,要根據(jù)具體情況確定。3.多目標(biāo)運(yùn)輸模型的蟻群算法 3.1多目標(biāo)運(yùn)輸問題其數(shù)學(xué)模型如下 ：(1)其中：表示第i個(gè)產(chǎn)地的產(chǎn)量；表示第j個(gè)銷地的銷量；表示第q個(gè)目標(biāo)函數(shù)的費(fèi)用系數(shù)；為產(chǎn)地i銷往銷地j的銷量；第一個(gè)約束保證由一個(gè)產(chǎn)地運(yùn)出量不能超出該產(chǎn)地的產(chǎn)量；第二個(gè)約束為一個(gè)銷地的需求必須滿足；在上述模型中，稱為產(chǎn)銷平衡運(yùn)輸問題。 3.2多目標(biāo)運(yùn)輸問題轉(zhuǎn)化為單目標(biāo)運(yùn)輸問題本文把多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題來求解,所用的方法是加權(quán)法。假設(shè)多目標(biāo)的各個(gè)函數(shù)所對(duì)應(yīng)的權(quán)重為,，各個(gè)目標(biāo)函數(shù)的權(quán)重根據(jù)問題的需要而定。加權(quán)之后的綜合目標(biāo)為 (2)。3.3用外懲罰函數(shù)法把單目標(biāo)約束問題轉(zhuǎn)化為無約束問題 根據(jù)上述我們把(1)、（2）兩式用外懲罰函數(shù)法轉(zhuǎn)化成如下: Min 3.4蟻群算法求解單目標(biāo)運(yùn)輸問題的基本思路蟻群算法是用大量的螞蟻在搜索空間中做局部并行搜索，反復(fù)地對(duì)路徑上的信息素的高濃度的偏好選擇，用信息素來指導(dǎo)搜索，并引入了信息素的揮發(fā)機(jī)制來防止陷入局部解，加強(qiáng)之后得到全局最優(yōu)解，基于蟻群算法，提出用于多目標(biāo)運(yùn)輸?shù)母倪M(jìn)蟻群算法，用于加權(quán)后的總目標(biāo)優(yōu)化求解： (1)第一步為確定各個(gè)子目標(biāo)函數(shù)權(quán)重,并建立搜索空間。預(yù)處理后得到各個(gè)子目標(biāo)函數(shù)的權(quán)重向量 。然后通過對(duì)各個(gè)約束條件求解，得到搜索空間，一般為一個(gè)維空間中的凸子空間，記為 ，其中 ，的各個(gè)分量滿足，在此空間中的每一個(gè)點(diǎn)對(duì)應(yīng)一個(gè)滿足約束條件的可行解。然后進(jìn)行離散化處理，將各個(gè)分量的搜索范圍等分成離散的點(diǎn)，再進(jìn)行切分。在這里，我們對(duì)各個(gè)分量采用一樣的劃分粒度便于處理。要特別指出的是，在確定各個(gè)子目標(biāo)函數(shù)的權(quán)重時(shí)，使用現(xiàn)成的手段進(jìn)行預(yù)處理。經(jīng)過改進(jìn)的蟻群算法主要是處理權(quán)重確定后的總目標(biāo)函數(shù)的最優(yōu)化求解。(2) 第二步為使用Ant在搜索空間中進(jìn)行搜索。將每個(gè)分量的取值區(qū)間等分成N 個(gè)點(diǎn)，那么就有N 種選擇， 維決策量X 有種選擇組合。將每個(gè)分量的N 個(gè)取值點(diǎn)看作N 個(gè)城市City。先將m 個(gè)螞蟻Ant隨機(jī)地放到 的N中的m個(gè)City上。搜索開始后，首先進(jìn)行隨機(jī)搜索，使整個(gè)搜索空間得到初步的信息素分布，為下一階段的概率搜索打好鋪墊，Ant按照轉(zhuǎn)移概率從的一個(gè)City(i, j,h)移動(dòng)到的一個(gè)City(i,j+1,k)上，顯然 。稱 中的N 個(gè)City組成一個(gè)層 ，一共有個(gè)層，層間的先后順序是可以隨機(jī)的，不影響最后優(yōu)化的結(jié)果。每只Ant從開始，層層轉(zhuǎn)移，一直到達(dá) ， 走過的路徑 對(duì)應(yīng)一個(gè)解，計(jì)算出對(duì)應(yīng)的多目標(biāo)優(yōu)化函數(shù)值。(3) 更新路徑上的信息素，得到當(dāng)前最優(yōu)解。所有螞蟻得出解后，更新City(i, j，h)與City(i,j+1,k)之間路徑 上的信息素為：，其中 為揮發(fā)系數(shù)，可經(jīng)過試驗(yàn)得出經(jīng)驗(yàn)值，一般可取較小的正值， 為m 只螞蟻在路徑上留下的新增信息素的總量，每次路徑走過之后都要按照更新算法更新路徑上的信息素。由于信息素與目標(biāo)優(yōu)化值成反比，當(dāng)所得出的解 所對(duì)應(yīng)的多目標(biāo)優(yōu)化值越小，那么在上留下的信息素越大。這樣就對(duì)搜索做出了指導(dǎo)，通過反復(fù)運(yùn)算之后，最優(yōu)解將逐漸加強(qiáng)，并且保持穩(wěn)定，由于揮發(fā)機(jī)制的作用，弱勢(shì)解將逐漸被弱化，最后導(dǎo)致其被淘汰。同時(shí)，考慮權(quán)重的學(xué)習(xí)與更新，則在一輪搜索后，調(diào)整權(quán)重來調(diào)整加權(quán)后的總目標(biāo)函數(shù)，最優(yōu)解的搜索可以根據(jù)優(yōu)化目標(biāo)的實(shí)際需要而通過權(quán)重的變化而得到指導(dǎo)。讓m只Ant做多次搜索之后得出一個(gè)當(dāng)時(shí)最優(yōu)解，然后將的各個(gè)分量細(xì)化重新建立搜索空間，重復(fù)以上過程，依次得到當(dāng)停機(jī)條件滿足的時(shí)候得到最優(yōu)解并輸出。4.結(jié)束語 蟻群算法作為通用型隨機(jī)優(yōu)化方法是根據(jù)螞蟻覓食時(shí)的行為特性而設(shè)計(jì)的, 該算法能在非常困難的情況下搜索到運(yùn)輸問題的最優(yōu)解。蟻群算法至今仍處于萌芽時(shí)期, 不管是理論還是應(yīng)用都尚未成熟,因此有關(guān)這方面的研究仍需繼續(xù)下去, 而在多目標(biāo)運(yùn)輸中的應(yīng)用也只是其中一例。如果能在參數(shù)設(shè)計(jì)方面取得突破, 相信該算法必能為許多領(lǐng)域的難題提供強(qiáng)有力的解決手段和工具。本文討論了改進(jìn)的ACA算法思想以及在多目標(biāo)運(yùn)輸問題的最優(yōu)解求解中的應(yīng)用，該算法通過隨機(jī)搜索同概率搜索結(jié)合，多個(gè)Ant并行求解，具有快速并能得到多個(gè)全局最優(yōu)解的優(yōu)點(diǎn)，現(xiàn)階段特別針對(duì)加權(quán)后的總目標(biāo)優(yōu)化求解。參考文獻(xiàn):(1) 高 尚 楊靜宇 . 群智能算法及其應(yīng)用 中國水利水電出版社。(2) 張 軍 胡曉敏 羅旭耀 . 蟻群優(yōu)化 清華大學(xué)出版社。(3) 段海濱 蟻群算法原理及其應(yīng)用 科學(xué)出版社。(4) 李士勇 蟻群算法及其應(yīng)用 哈爾濱工業(yè)大學(xué)出版社。(5) 盧開澄 單目標(biāo)、多目標(biāo)與整數(shù)規(guī)劃 清華大學(xué)出版社。南寧信息產(chǎn)業(yè)發(fā)展存在的問題與對(duì)策研究數(shù)計(jì)學(xué)院 黃德智【摘 要】本文通過詳實(shí)的相關(guān)調(diào)查和統(tǒng)計(jì)資料，對(duì)南寧的信息生產(chǎn)業(yè)、傳輸業(yè)、設(shè)備制造業(yè)、服務(wù)業(yè)等方面進(jìn)行分析，得出現(xiàn)階段南寧信息產(chǎn)業(yè)各方面發(fā)展的具體情況。由現(xiàn)狀進(jìn)一步研究南寧信息產(chǎn)業(yè)在區(qū)域經(jīng)濟(jì)發(fā)展中所面臨的形勢(shì)和存在的問題，著重從中國東盟自由貿(mào)易區(qū)、泛北部灣區(qū)域經(jīng)濟(jì)區(qū)、信息產(chǎn)品技術(shù)、信息產(chǎn)業(yè)基礎(chǔ)設(shè)施和人才等七個(gè)方面闡述南寧信息產(chǎn)業(yè)發(fā)展存在的問題。針對(duì)形勢(shì)和問題，從南寧信息產(chǎn)業(yè)發(fā)展方向、區(qū)域經(jīng)濟(jì)發(fā)展、產(chǎn)品特色等五個(gè)方面提出具有可行性的建議和對(duì)策。【關(guān)鍵詞】信息產(chǎn)業(yè)；區(qū)域經(jīng)濟(jì)；面臨形勢(shì)；存在問題；發(fā)展對(duì)策 Nanning development of the information industry and the problems CountermeasuresHuang De Zhi (Dept. of Mathematics and Computer Science, Guangxi Universityfor Nationality Nanning 530006,China)【Abstract】Through detailed investigation and statistical information, this paper analyses the information production industry, transmission industry, equipment manufacturing, and service industry of Nanning, and then obtains the concrete situation of the development of the information industry development of Nanning in different aspects at present days. And then after the study in the situation and current problems that exist in the information industry in Nanning, this paper focuses on China- ASEAN Free Trade Area, pan-Beibu Gulf economic zone, and information technology products, information industry infrastructure and information professional, from which expanding on the existing problems that Nanning has in the development of information industry. In consideration for the situation and problems, from the five aspects such as the direction of the development of information industry in Nanning, the regional economic development, and product characteristics, this paper finally raises the feasibility of the recommendations and countermeasures.【Key words】the information i