火災、爆炸專項應急預案 - 廣東省安全生產(chǎn)技術中心辦公系統(tǒng)

《火災、爆炸專項應急預案 - 廣東省安全生產(chǎn)技術中心辦公系統(tǒng)》由會員分享，可在線閱讀，更多相關《火災、爆炸專項應急預案 - 廣東省安全生產(chǎn)技術中心辦公系統(tǒng)（212頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、矩陣乘積可換的條件及應用 數(shù)計學院 劉艷萍 摘 要：矩陣的乘法運算一般不滿足交換律，但在特殊的條件下可交換。本文從可交換矩陣和相關定義出發(fā)，對可交換矩陣做了深入的探討，得到了矩陣可交換的一些條件和可交換矩陣的部分性質(zhì)，并且介紹可交換矩陣的應用。 關鍵詞：矩陣乘法；可交換條件；應用 Interchangeable Conditions of the product of matrices and Its Applications Liu Yanping (College of Mathematics and Computer Science, Guangxi Uni

2、versity 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 o

3、f 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; application

4、 1 引言及定義 在高等代數(shù)學習中，矩陣是一個重要內(nèi)容，由矩陣的理論可知，矩陣的乘法不同于復數(shù)的乘法，矩陣的乘法運算一般不滿足交換律，即對兩個方陣，在一般情形下。但在某些特殊情況下，矩陣的乘法也滿足交換律，這時我們稱是可交換矩陣?？山粨Q矩陣有著許多特殊性質(zhì)和作用。 本文從可交換矩陣定義及相關定義出發(fā)，探討矩陣可交換的一些條件和可交換矩陣的部分性質(zhì)，并介紹可交換矩陣的一些應用。為研究矩陣可交換條件，我們先給出下列定義[1]。 定義1 若同階方陣有，則稱方陣與為可交換矩陣. 定義2 階方陣中若元素滿足，稱為階對角陣，記作 . 定義3 　若階方陣滿足，其中為階單位陣，則稱為階正交

5、矩陣. 用表示的轉置矩陣；表示的伴隨矩陣[2]。 2 矩陣乘積可交換的條件及性質(zhì) 2.1 矩陣乘積可交換的條件 定理1 設是的伴隨矩陣，則與乘積可交換. 證明 由即知. 定理2 （1）設，其中,為非零實數(shù)，則,可交換； （2）設，其中為正整數(shù)，為非零實數(shù)，則,可交換. 證明 （1）由可得，即　 ， 得 ， 于是 ， 所以 . （2）由得，故，于是 ，從而. 定理3[3] 設, 均是階可逆矩陣, 若對任意實數(shù)，均有，其中為 階單位矩陣，則,可交換. 定理4 設都是階矩陣，則下列均是可交換的充要條件： (1) ； (2) ； (3)

6、 ； (4) . 證明 (1) 由及即得. (2) 由 可證得； (3) 因，兩端分別取它們的轉置，得，又，故 . 由矩陣運算性質(zhì)及已知條件，即得，兩端分別取它們的轉置，得. (4) 分別由，，兩邊取伴隨可證得. 定理5 （1）設均為階(反)對稱矩陣，則可交換的充要條件是為對稱矩陣； （2）設為階對稱陣，為階反對稱陣，可交換的充要條件是為反對稱陣。 證明 （1）① 若均為階對稱矩陣，則 因 且，故，即為對稱陣。 因又，故，即為可交換矩陣。 ② 若均為反對稱矩陣，則 因且，故，即為對稱陣。 因又，故，即為可交換矩陣。 （2）因，，故，即為反對稱陣。 因

7、為反對稱陣, ，又，故，即可交換。 定理6 設均為對稱正定矩陣，則可交換的充要條件是為對稱正定矩陣. 證明 充分性顯然. 下面證明必要性。 因為對稱正定矩陣，故有可逆矩陣，使，于是 ， 所以為對稱正定矩陣，其特征值全為正數(shù)。而與相似，從而 的特征值也全為正數(shù)，因此為對稱正定矩陣。 定理7 設均為階矩陣，若滿足，則可交換的充要條件是 . 證明 因，故 即. 由于，即,分別用左乘,右乘式 的兩邊，得到，即. 定理8 設是階方陣，則與任一階矩陣可換的充要條件是（數(shù)量矩陣）. 證明 令是第行，第列處的元素為，其余元素為的階方陣，因與任一 階矩陣可換，

8、所以與所有可換，又 (列) 所以由的第行除外其余元素全為,，即除外，其余元素全為，故. 設，則對任意階矩陣，有. 定理9 設矩陣，其中當時，，則可交換的充要條件是為對角矩陣. 定理10 設為準對角矩陣，其中當時，， ，是階單位矩陣，，則可交換的充要條件是為準對角矩陣. 2.2 乘積可交換矩陣的性質(zhì) 性質(zhì)1 　設均為階可交換矩陣，則有 (1),其中都是正整數(shù)； (2) 對任意正整數(shù)， (矩陣二項式定理)； (3) 平方差公式：； (4) 完全平方和（差）公式：； (5) 矩陣積的乘冪公式：（是正整數(shù)）. 證明 （1）先證明對任意正整數(shù)，有，對作數(shù)學歸納法

9、 當時，由已知條件，即當時結論成立；假設當時結論成立，即，則當時， ，故當時結論也成立，由歸納法原理，對一切正整數(shù)，有；再證明， 對作數(shù)學歸納法. 當時，由上面結論知，即當時結論成立；假設當時結論成立，即，則當時，，故當時結論也成立；由歸納法原理，對一切正整數(shù)，有 . (2) 對作數(shù)學歸納法.當時 當時，由，有 即當時結論成立；假設當時結論成立，即 ， 當時，

10、. （倒數(shù)第三式到第二式利用了組合的性質(zhì)：，及，）即當時結論也成立。從而由歸納法原理，對任意正整數(shù)，有= . (3)～(5) 較明顯，證明從略. 性質(zhì)2[4] 設是階復矩陣，，則存在一個階可逆矩陣，使得與同為上三角矩陣. 證明 對的階數(shù)作數(shù)學歸納法。當時，結論顯然成立。假設結論對于階矩陣也成立。當?shù)碾A數(shù)為時，由于，至少有一個公共的特征向量設 將擴充為的一組基(均為列向量). 設 (1) (2) 由得 于是，由歸納法假設，存在階可逆矩陣使得 ， 令，由（1）,（2）兩式得 , 令則 . 3 可交換矩陣

11、的應用 3.1 利用矩陣可交換性,求矩陣的方冪 例1 計算, 是正整數(shù). 解 設, 由于 , 因為與可交換，所以由二項式定理得 , 即. 例2 計算 , 是正整數(shù). 解 設, 因為 , 又因為與可交換，所以由二項式定理得 即. 例3 計算 是正整數(shù). 解 設, 因為 , 所以當時，，又和是可交換的，所以由二項式定理得， 即. 例4 設 對任意正整數(shù)，求. 解 令 則，又，設 故利用矩陣乘法的結合律得 其中從而，因此 注意到：移項，得

12、 從而有，所以 即的主對角線上的元均為而其余元素均為. 從以上各例的求解過程中，我們可以看到此種類型的題的解法都是把復雜的矩陣變成兩個可交換矩陣的和，再利用二項式定理，求出最后結果。而在將一個矩陣分解成兩個矩陣的和時，這兩個矩陣最好簡單點，它們中至少有一個矩陣的某次冪為零矩陣，這樣再運用二項式定理算矩陣次冪就非常簡單了。 3.2 利用矩陣可交換性,證明某些問題 例5 （2002年浙江大學碩士生入學考試試題）設是階復矩陣，其中是冪零矩陣而且 ，求證：. 證明 由于，由性質(zhì)2，存在階可逆矩陣，使得同為上三角矩陣， 又是冪零矩陣，故其特征值全為零. 于是，有 ， 從而

13、. 故 . 例6 （2001年浙江大學碩士生入學考試試題）設是數(shù)域上階矩陣且，求證： 秩 秩秩秩. 證明 設秩，秩. 由于，由性質(zhì)2，存在階可逆矩陣，使得 與 同為上三角矩陣，即 不妨設則 從而，秩秩秩秩. 參考文獻 [1] 北京大學數(shù)學力學系幾何與代數(shù)教研室代數(shù)小組. 高等代數(shù)[M] . 北京:人民教育出版社,1978. [2] 北京大學數(shù)學系. 高等代數(shù)(第三版) [M]. 高等教育出版社,2003. [3] 韓錦揚. 矩陣乘法AB = BA 成立的兩個充要條件與一個充分條

14、件[J ]. 工科數(shù)學,1995 ,11:169-170. [4] 曾梅蘭. 線性變換及矩陣可交換的性質(zhì)與應用[J]. 孝感學院學報,2006,26:44-46. 306 關于等冪和的一個新性質(zhì) 數(shù)計學院 李彬瑜 摘要：等冪和是一個歷史悠久的古老難題 ，曾有許多人進行了研究，它們在數(shù)論中有著重要的作用，本文運用同余原理和數(shù)論的方法來探討等幕和的一個新的性質(zhì)。證明了p為奇素數(shù)，m為奇數(shù)時，獲得了的值;當p為奇素數(shù),與m奇偶相異時，獲得了，并證明了的解為無限集。 關鍵詞：等冪和 同余 數(shù)學競賽 整除 And so on and the power

15、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 b

16、een 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 di

17、fferences, 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ù)學競賽問題 等冪和 （1） 是一個歷史悠久的古老難題。自從2000年前的希臘數(shù)學家阿基米德開，就吸引了國內(nèi)外數(shù)學家的研究興趣。1984年以后，陳景潤與黎鑒，王云等人對此作了大量

18、的貢獻。至今仍有不少數(shù)學家在研究，很多方法不斷涌現(xiàn)。究其原因，不僅是因為等冪和作為級數(shù)求和的典范，更重要的是，它的數(shù)論性質(zhì)對波文猜想、居家猜想與素數(shù)判別等問題有著非常重要的作用，而且在研究方法上有很強的靈活性，又可為開拓創(chuàng)新思維的寶地，在各國數(shù)學竟賽中也常常有與此有關的題目.1993年中國數(shù)學奧林匹克國家隊選拔考試的第一題是：對素數(shù)p 3，定義 （2） 求的值。 其實解決這個問題的實質(zhì)是利用等冪和的整除性，求出對模的剩余，然后再帶入題目中給定義的式子即可。本文除了解決了數(shù)學競賽這一問題

19、外，還由此進一步將推廣到 及 的研究。 §2.引理 引理 設m為奇數(shù)，，則有： （4） 證明； 一方面，由首尾配對有 （5） 由于m為奇數(shù)，故有，故由（5）式有 另一方面，再由首尾配對有： （6） 同理 又由 于，故 引理 若p為素數(shù)，m、n∈Ｎ，p∣n，則 （7） 證

20、明：設， 當時，由費爾馬小定理有：當時 　　　　 而，故　　 所以　　　 同理有 　　　　　　 而當時， ，則有 當時，設為模的一個原根， 則 故 同理，結合有 引理 若m為奇數(shù)，則有 　　　　　　　　　　　　 （8） 　 （9）　　　　　　　　　　　　 證明： 由等冪和的定義有

21、 故有　 這就獲得了（8）式，再在（8）式模即得（9）式。 引理4 若m為偶數(shù)，則有 （10） 證明： 由上式即得： 引理5 當m、n均為自然數(shù)時，則有： 　　　 （11） 證明：　當２?n時， 　　 當２∣n時，　　 　　　　　　　　　 §3.定理 定理1 設p為奇素數(shù)，m 為奇數(shù)，則有 。 證明：因為m為奇數(shù)，則根據(jù)引理1有 故 定理

22、2 設p為奇素數(shù)，m為偶數(shù)，則有 （12） （13） 證明： 由引理2有 （14） （15） 定理3 設p為奇素數(shù)，m為奇數(shù)，若 則有： （16） 證明：當m=1時， 則

23、 當時 由引理2 有 又由引理3中式 　有　 故 綜合、可得?。骸? 　 定理 4 設p>3素數(shù)，定義 （17） 證明： S為無限集。 證明：令 　　　　　　 　 由費爾馬小定理有 而 故 即得S為無限集。 §4.數(shù)學競賽問題的解決 由題可設對每一個素數(shù)p，存在一個原根g，使得構成模p的一個完全剩余

24、系。根據(jù)定理1有： 若，則 ； 若，即，則 故 §5.結語 到目前為止很多人都對等冪和的性質(zhì)我有關算計進行了大量的研究，并取得了豐碩的成果。本文雖然獲得了一些結果，但是仍有許多問題沒有改進和開發(fā)，尚待繼續(xù)研究。如當m為偶數(shù)時，定理3有何類似結果？定理5中如果是變?yōu)闀r能否求出m的的全部解等等。因此我還將繼續(xù)努力，尋找解決的方法。 參考文獻： [1]陳景潤,黎鑒愚關于冪和問題的進一步研究.[J]科學通報，1985,30(17):1381 -1384 [2]陳景潤，黎鑒愚關于等冪和問題.[J]科學通報，1985,30(4):316—317. [3]

25、陳景潤，黎鑒愚關于冪和公式的一般性質(zhì).[J]數(shù)學研究與評論，1986,(1):43-50. [4]王云葵，等幕和與bernoulli數(shù)的通解公式.[J].廣西大學學報，1999,24(4):31 8-320 [5] 王云葵.伯努利數(shù)與波文猜想.廣西民族學院學報(自然科學版). 1999. 5. (3) [6] 王云葵.等冪和研究及其新進展.玉林師專學報，1994,15(3):4-10 [7] 王云葵.等暴和與居加猜想.數(shù)學通訊.1992,(11):43^-44 [8] 王云葵. 等冪和的分解及同余式鏈. 天中學刊.1999 .14(5): [9] 王云葵. 等冪和與判別素數(shù)的充

26、要條件.數(shù)學通報.1996,(6):46-47 [10] 王云葵. 等冪和與波文猜想.廣西教育學院學報.1998.(1):104-111 一種新的掃描線種子填充算法 數(shù)計學院 黃小果 摘 要：為了解決經(jīng)典掃描線種子填充算法存在的重復掃描、棧操作頻繁等問題，本文提出一種新的掃描線種子填充算法。新算法取掃描線上每個填充區(qū)域的中點作為種子入棧，在不增加棧數(shù)據(jù)結構的前提下，通過一定的策略，使得每個出棧的種子能最大限度地往上和往下進行單向填充。新的算法設計巧妙，充分利用了區(qū)域連通的性質(zhì)和圖形像素分布的特點，極大地減少重復掃描的次數(shù)和入棧的種子數(shù)量，從而節(jié)約了資源并使得填充速度得到了很

27、大的提高。 關鍵詞：區(qū)域填充，連通區(qū)域，種子，種子填充算法 A New Scan Line Seed Filling Algorithm Huang Xiaoguo Guangxi University for Nationalities College of Mathematics and Computer Science Nanning 530006 Email:huangxgiq120@ Abstract: In order to solve the problem of the classic line scanning seed filling algori

28、thm, 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 t

29、o 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 fil

30、ling speed has been greatly improved. Keywords：regional filling，regional connectivity，Seed，Seed filling algorithm 0 引言 在圖形學的應用中，常常要在指定的區(qū)域內(nèi)填充上填充顏色或圖案，即區(qū)域填充。如何高效地進行填充是填充算法要解決的重要問題。種子填充算法是區(qū)域填充的一種重要方法，在實際中得到了廣泛地運用。 種子填充算法的基本思想是從一個封閉區(qū)域內(nèi)部的一個已知像素出發(fā)，通過某種方法找到區(qū)域內(nèi)的所有像素，從而進行填充。常用的種子填充算法有：簡單種子填充算法和掃描線種子填充

31、算法。簡單種子填充算法可以采用遞歸算法【2】，這種算法的原理和程序都很簡單，但由于多次遞歸和占用大量資源，填充質(zhì)量非常差。為此，可以采用棧結構來實現(xiàn)簡單的種子填充算法【1】。其基本原理是：種子像素入棧；當棧非空時重復執(zhí)行如下三步驟操作： （1）棧頂像素出棧； （2）將出棧像素置成多邊形色； （3）按左、上、右、下順序檢查與出棧像素相鄰的四個像素，若其中某個像素不在邊界且未置成多邊形色，則把該像素入棧。 9 6 5 3 S111111 4 7 2 8 圖1 S出棧后，像素4、7、9等出現(xiàn)了重復入棧。 如圖1所示，S出棧后，其間出現(xiàn)了重復入棧的冗余。并且

32、，這種算法仍然需要很大的存儲空間以實現(xiàn)棧結構，所花費的時間也較多。 經(jīng)典掃描線種子填充算法也是為解決上述問題而提出的一種重要方法。此外，一些專家提出了基于鏈隊的種子填充算法【3】，有效地解決了重復入棧的問題，在此不再贅述。 這里需要指出的一個概念是區(qū)域的連通性。區(qū)域的連通性是指從區(qū)域上的一點出發(fā)，通過幾個方向移動的組合，在不超出區(qū)域的前提下，達到區(qū)域的任意像素。如圖2和圖3所示，區(qū)域可以分為四向連通區(qū)域和八向連通區(qū)域兩種。本文的討論基于四連通區(qū)域，即從區(qū)域上的一點出發(fā)，通過上、下、左、右移動的組合，達到區(qū)域的任何像素。 圖2 四向連通

33、 圖3 八向連通 1 經(jīng)典算法的描述與分析 1.1經(jīng)典算法描述 假定填充區(qū)域邊界像素顏色為boundary_color，區(qū)域要填充的顏色為fill_color。經(jīng)典掃描線種子填充算法的原理是將種子像素入棧，當棧非空時做以下4步操作。 步驟1：棧頂像素出棧。 步驟2：對包含出棧像素的整個區(qū)間進行填充。 步驟3：上述區(qū)間的最左、右記為xl和xr。 步驟4：在區(qū)間檢查與當前掃描線相鄰的上下兩條掃描線的有關像素是否全為邊界像素或已填充的像素，若存在非邊界，未填充的像素，則把每一區(qū)間的最右或最左像素取為種子像素入棧。 1.2經(jīng)典算法分析 經(jīng)典算法采取的方法是在任意一條掃描線與

34、多邊形的相交區(qū)間（含若干連續(xù)像素）中，只取一個像素作為種子入棧。顯然，經(jīng)典算法減少了入棧的種子數(shù)量，節(jié)省了存儲空間。 但是對經(jīng)典算法更進一步地分析，我們可以發(fā)現(xiàn)經(jīng)典算法存在以下不足： 1、重復掃描。為了對當前線段填色和將上、下線段的種子入棧，需要對當前線段，上下掃描線進行掃描。在這個過程中會使得某些線段被重復掃描3次，這降低了程序的效率和運行速度。 2、出現(xiàn)漏填。由于未遵循經(jīng)典算法，出現(xiàn)了漏填現(xiàn)象。文獻[4]認為經(jīng)典算法會出現(xiàn)漏填，這是錯誤的。 3、棧操作頻繁。在對與當前掃描線相鄰的上、下掃描線進行種子搜索時，每搜到一個填充區(qū)域，就要將種子入棧；同時每次開始對另一行搜索時都要先出棧。這

35、樣則占用了大量的存儲空間，降低了效率。 對于問題1和2的改進，專家們提出了許多行之有效的方法。例如文獻[5]定義了如下新的結構體： typedef struct node { int dx,dy,left,right,oldleft,oldright,flag; struct node *next; }; 其中，dx，dy是種子坐標；flag為方向標志，取值+1和-1。作者根據(jù)flag的值進行單向填充，避免了重復掃描。顯然，文獻[5]在種子棧中加入了一些變量，使棧結構變得復雜。此外，棧操作頻繁的問題還沒有解決。 2 新掃描線種子填充算法的描述與分析 2.1算

36、法的描述 假定給定區(qū)域邊界像素顏色為boundary_color，區(qū)域要填充的顏色為fill_color。將種子像素（x,y）入棧，當棧非空時執(zhí)行以下操作： 步驟1：棧頂像素出棧。 步驟2：對包含棧頂像素的整個區(qū)間進行填充，并記下區(qū)間的最左、右值xl_old和xr_old，xl=xl_old，xr=xr_old； 步驟3：向上填充。判斷棧頂像素的上一個像素是否為邊界且未填充。若不為邊界且尚未填充，填充包含（x,y+1）的整個區(qū)間，并并更新xl和xr作為區(qū)間的最左、右值。判斷是否有回溯，若有則回溯，確定種子并將其入棧。將（x,y+1）看成棧頂像素，繼續(xù)執(zhí)行步驟3；否則，尋找下一個種子入棧

37、，之后轉入步驟4。 步驟4：向下填充。判斷棧頂像素的下一個像素是否為邊界且未填充。若不為邊界且尚未填充，填充包含（x,y-1）的整個區(qū)間，并更新xl和xr作為區(qū)間的最左、右值。判斷是否有回溯，若有則回溯，確定種子并將其入棧。將（x,y-1）看成棧頂像素，繼續(xù)執(zhí)行步驟4；否則，尋找下一個種子入棧，之后轉入步驟5。 步驟5：結束判斷。如果種子棧為空，則算法結束；否則，轉入步驟1。 2.2算法的圖示： 圖4 圖5 填充圖示

38、 種子棧圖示 2.3算法的分析： 2.3.1種子棧的數(shù)據(jù)結構： class QNode { public: QNode(); virtual ~QNode(); public: POINT data; QNode *Next; }; 其中，data記錄種子的坐標，next為下一個種子。比起文獻[5]，新算法種子棧的數(shù)據(jù)結構無須增加變量，更加簡單明了。 2.3.2算法的一些細節(jié)與處理： （1）關于算法步驟3和4中如何確定下一個種子： 在這里筆者采用的方法是：將填充區(qū)域的中點入棧。代碼如下： i

39、f((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); } else { p.x=int((x+xl-1)/2); //p.x=xl-1; p.y=y; stackpush(p); } 其中“p.x=in

40、t((x+xl-1)/2);”代碼段就是確定區(qū)域中點。這樣將能使每個種子能最大限度的往上或者往下填充，大大的減少了入棧的種子數(shù)量和節(jié)省了大量的時間。 （2）回溯問題。 圖6 向上填充時可能出現(xiàn)回溯的情況 向上填充：如圖6所示，同一條掃描線上出現(xiàn)多個填充區(qū)域時，可能需要回溯，否則會出現(xiàn)漏填。假設[xl_old,xr_old]為上條掃描線填充區(qū)域，[xl,xr]為當前掃描線的填充區(qū)域。當xlxr_old+2，xr+2xl_old時，則會出現(xiàn)回溯。此時，我們采取的辦法是：取[xl,

41、xl_old-2]，[xr_old+2,xr]，[xr+2,xr_old]，[xl_old,xl-2]的中點作為種子入棧。 向上填充時，回溯問題的c++語言如下： if(xlxl_old) { seek_seed(xl_old,xl-2,y0,fill_color,boundary_color); } if(xr>xr_old+1)

42、{ seek_seed(xr_old+2,xr,y0-1,fill_color,boundary_color); } if(xr+1

43、k_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

44、 } 2.3.3新算法的特點： 取掃描線上每個填充區(qū)域的中點作為種子入棧，每個出棧的種子都盡可能地往上或往下單向填充；從微觀處了解像素點的分布情況，有效地解決了回溯的問題。 2.3.4新算法的優(yōu)點： 新的算法大大地減少了種子入棧的數(shù)量和重復掃描的次數(shù)，從而節(jié)省了資源，提高了效率。 2.3.5新算法的不足： 新的算法雖然大大地減少了重復掃描的次數(shù)，但還不能完全消除重復掃描。除第一個種子外，其余出棧的種子往上或往下掃描時，會出現(xiàn)一次的重復掃描。如圖4中的S2，當它出棧時還要掃描上面一條掃描線，但上面一條掃描線已經(jīng)掃描過了，所以出現(xiàn)了重復掃描。 3 新算法與經(jīng)典算法的一些

45、數(shù)據(jù)比較： 筆者在Visual C++平臺上對新的算法與經(jīng)典算法進行比較。如圖8所示，填充帶圓形孔(R=100像素)的矩形填充區(qū)域（邊長a=600像素）；如圖9所示，填充帶有任意孔的連通區(qū)域。試驗結果表明新的算法不會出現(xiàn)漏填、錯填等現(xiàn)象。 圖8 帶圓孔的矩形填充區(qū)域 圖9 帶孔的任意連通區(qū)域 帶圓孔的矩形填充區(qū)域（圖8） 帶任意孔的連通區(qū)域（圖9） 填充像素 填充時間 入棧像素 填充像素 填充時間 入棧像素 經(jīng)典算法【1,2】 326336 17s 799 48628 3s 909 新算法 326336 4s

46、 3~4 48628 1s 不大于40 4 結束語 表面上看，新算法似乎比經(jīng)典算法復雜。其實不然，只是新的算法設計更巧妙罷了。新算法在沒有增加棧的數(shù)據(jù)結構的情況下，使得每個出棧的種子都盡可能地往上或往下單向填充，省去了經(jīng)典算法尋找種子，進而進棧、出棧等繁雜的操作過程，減少了重復掃描和入棧的種子數(shù)量，從而節(jié)省了大量的運算時間和大量的存儲空間。雖然新的算法沒有完全的消除重復掃描，但比起經(jīng)典算法，重復掃描的次數(shù)已經(jīng)大大減少，幾乎可以忽略不計。 大量實驗證明，新算法在填充時間、入棧像素等方面有了巨大的進步，比起經(jīng)典算法具有更大的優(yōu)越性。 參考文獻： [1]孫家廣 等,

47、計算機圖形學(第三版)[M].北京：清華大學出版社,1999. [2]張曦煌，杜俊俐.計算機圖形學[M].北京：北京郵電大學出版社,2007. [3]陳元琰，陳洪波.一種基于鏈隊的種子填充法[J],廣西師范大學學報(自然科學版),2003,9：30—33. [4]李桂清，李陶深.掃描線種子填充算法的問題及改進[J],廣西大學學報(自然科學版),1998,9：207—211. [5]孫燮華.掃描線種子填充算法的改進[J].計算機工程,2000,12：142—143. 基于蟻群算法的多目標運輸問題優(yōu)化算法的研究 數(shù)計學院 黃富平 摘要 蟻群算法是一種嶄新的仿生模擬進化

48、算法，該算法在許多領域已經(jīng)得到應用。多目標運輸問題是一類很重要的優(yōu)化問題，優(yōu)化與求解較難。對此，提出了一種改進蟻群算法用于求解多目標運輸問題，得到一組變量的權重后，用一定數(shù)量的螞蟻在解空間中首先隨機搜索，然后模擬螞蟻尋食的方式，通過信息素來指引搜索。 關鍵詞：多目標優(yōu)化；運輸問題；蟻群算法 Research of Multi-Objective Transportation Problem Optimization Algorithm Based on Ant Colony Algorithm Abstract Ant Colony Algorithm is a brand-new

49、 bionic simulated evolutionary algorithm, which has been applied to many fields. Multi-objective transportation problems are very important optimization problems. It’s hard to optimized or solved. An improved Ant Colony Algorithm to solve Multi-objective transportation problems is introduced. After

50、 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 colo

51、ny algorithm 1.引言 隨著運輸網(wǎng)絡的發(fā)展和貨運量的增加，運輸調(diào)度問題變得越來越復雜。以總運費最小為優(yōu)化目標的單目標優(yōu)化模型得到的解，往往并不是決策者最滿意的解，人們希望得到的是多目標的最優(yōu)解。目前，涌現(xiàn)出許多求解多目標優(yōu)化問題的算法，如交互式多目標優(yōu)化、模糊規(guī)劃法 、遺傳算法、表上作業(yè)法等，但遺傳算法是目前人們用來求解該類問題的主要方法。 蟻群算法作為一種新的仿生類進化算法是由Dorigo首先提出的, 該算法模仿螞蟻覓食時的行為, 按照啟發(fā)式思想, 通過信息傳媒—— 費洛(Pheromone) 的誘導作用, 逐步收斂到問題的全局最優(yōu)解。蟻群算法自問世以來表現(xiàn)出了強大的

52、生命力, 較之以往的啟發(fā)式算法不論在搜索效率上, 還是在算法的時間復雜度方面都取得了令人滿意的效果。 該算法已被其他領域的專家所接受, 并運用到諸如工件排序、圖著色、車輛調(diào)度、大規(guī)模集成電路設計、通信網(wǎng)絡中的負載平衡問題等許多方面。本文嘗試將蟻群算法用于多目標運輸問題, 因為蟻群算法具有卓越的隨機搜索尋優(yōu)能力,而多目標運輸問題非常適合蟻群算法的適用領域。這兩方面結合必將在多目標運輸問題的研究中取得較滿意的結果。 2. 蟻群系統(tǒng)模型介紹 據(jù)昆蟲學家的觀察和研究發(fā)現(xiàn)，生物世界中的螞蟻有能力在沒有任何可見提示下找出從其窩巢至食物源的最短路徑，并能隨環(huán)境的變化而變化適應性地搜索新的路徑，

53、作出新的選擇。作為昆蟲的螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物---信息素，使得一定范圍內(nèi)的其它螞蟻能夠察覺到并由此影響它們以后的行為。當一些路徑上通過的螞蟻越來越多時,其留下的信息素軌跡也越來越多，以致信息素強度增大(當然隨時間的推移會逐漸減弱) ，后來螞蟻選擇該路徑的概率也就越高，從而增加該路徑的自催化行為。由于其原理是一種正反饋機制,因此，可將蟻群理解成所謂的增強型學習系統(tǒng).蟻群算法就是源于這種智能協(xié)作行為的算法。作為一種通用型隨機優(yōu)化方法，它吸收蟻群中螞蟻的行為特性,通過其內(nèi)在搜索機制，在一系列困難的組合優(yōu)化問題求解中取得成效。由于在模擬仿真中使用的是人工螞蟻概

54、念，因此有時亦稱為蟻群系統(tǒng)。 以求解n個城市TSP的問題為例來說明蟻群系統(tǒng)模型。為了模擬實際螞蟻的行為，m表示蟻群中螞蟻的數(shù)量，表示城市i和城市j之間距離，表示t時刻位于城市i的螞蟻個數(shù)，。表示t時刻在ij連線上殘留的信息量。在初始時刻,設(c是常數(shù)),各條路徑上的信息量相等。螞蟻k()在運動過程中,根據(jù)各條路徑上的信息量決定移動方向。表示在t時刻螞蟻由位置i轉移到位置j的概率: 其中,表示螞蟻k下一步允許選擇的城市； α、β分別表示螞蟻在運動過程中所積累的信息及啟發(fā)式因子在螞蟻路徑選擇中所起的不同作用。與真實蟻群系統(tǒng)不同,人工螞蟻系統(tǒng)具有一定的記憶功能。這里用來記錄螞蟻k目前

55、已經(jīng)走過的城市。隨著時間的推移,以前留下的信息逐漸消逝。用參數(shù)表示信息消逝的程度,經(jīng)過n個時刻,螞蟻完成一次循環(huán)。各路徑上的信息量根據(jù)下式作調(diào)整: 表示第k只螞蟻在本次循環(huán)中留在路徑ij上的信息量,表示本次循環(huán)中留在路徑ij上的信息量: 式中,Q是常數(shù)；是第k只螞蟻在本次循環(huán)中所走過路徑的長度。在初始時刻,,,其中, 。表示由城市i轉移到城市j的期望 程度,可以根據(jù)某種啟發(fā)算法具體確定。根據(jù)具體算法的不同,,及的表達形式可以不同,要根據(jù)具體情況確定。 3.多目標運輸模型的蟻群算法 3.1多目標運輸問題 其數(shù)學模型如下 ： (1) 其中：表示第i個產(chǎn)地的產(chǎn)量；表示

56、第j個銷地的銷量；表示第q個目標函數(shù)的費用系數(shù)；為產(chǎn)地i銷往銷地j的銷量；第一個約束保證由一個產(chǎn)地運出量不能超出該產(chǎn)地的產(chǎn)量；第二個約束為一個銷地的需求必須滿足；在上述模型中，稱為產(chǎn)銷平衡運輸問題。 3.2多目標運輸問題轉化為單目標運輸問題 本文把多目標問題轉化為單目標問題來求解,所用的方法是加權法。假設多目標的各個函數(shù)所對應的權重為,，各個目標函數(shù)的權重根據(jù)問題的需要而定。加權之后的綜合目標為 (2)。 3.3用外懲罰函數(shù)法把單目標約束問題轉化為無約束問題 根據(jù)上述我們把(1)、（2）兩式用外懲罰函數(shù)法轉化成如下: Min 3.4蟻群

57、算法求解單目標運輸問題的基本思路 蟻群算法是用大量的螞蟻在搜索空間中做局部并行搜索，反復地對路徑上的信息素的高濃度的偏好選擇，用信息素來指導搜索，并引入了信息素的揮發(fā)機制來防止陷入局部解，加強之后得到全局最優(yōu)解，基于蟻群算法，提出用于多目標運輸?shù)母倪M蟻群算法，用于加權后的總目標優(yōu)化求解： (1)第一步為確定各個子目標函數(shù)權重,并建立搜索空間。 預處理后得到各個子目標函數(shù)的權重向量 。然后通過對各個約束條件求解，得到搜索空間，一般為一個維空間中的凸子空間，記為 ，其中 ，的各個分量滿足 ，在此空間中的每一個點對應一個滿足約束條件的可行解。然后進行離散化處理，將各個分量的搜索范圍等

58、分成離散的點，再進行切分。在這里，我們對各個分量采用一樣的劃分粒度便于處理。要特別指出的是，在確定各個子目標函數(shù)的權重時，使用現(xiàn)成的手段進行預處理。經(jīng)過改進的蟻群算法主要是處理權重確定后的總目標函數(shù)的最優(yōu)化求解。 (2) 第二步為使用Ant在搜索空間中進行搜索。 將每個分量的取值區(qū)間等分成N 個點，那么就有N 種選擇， 維決策量X 有種選擇組合。將每個分量的N 個取值點看作N 個城市City。先將m 個螞蟻Ant隨機地放到 的N中的m個City上。搜索開始后，首先進行隨機搜索，使整個搜索空間得到初步的信息素分布，為下一階段的概率搜索打好鋪墊，Ant按照轉移概率從的一個City(i, j,h

59、)移動到的一個City(i,j+1,k)上，顯然 。稱 中的N 個City組成一個層 ，一共有個層，層間的先后順序是可以隨機的，不影響最后優(yōu)化的結果。每只Ant從開始，層層轉移，一直到達 ， 走過的路徑 對應一個解，計算出對應的多目標優(yōu)化函數(shù)值。 (3) 更新路徑上的信息素，得到當前最優(yōu)解。所有螞蟻得出解后，更新City(i, j，h)與City(i,j+1,k)之間路徑 上的信息素為：，其中 為揮發(fā)系數(shù)，可經(jīng)過試驗得出經(jīng)驗值，一般可取較小的正值， 為m 只螞蟻在路徑上留下的新增信息素的總量，每次路徑走過之后都要按照更新算法更新路徑上的信息素。由于信息素與目標優(yōu)化值成反比，當所得出的解 所

60、對應的多目標優(yōu)化值越小，那么在上留下的信息素越大。這樣就對搜索做出了指導，通過反復運算之后，最優(yōu)解將逐漸加強，并且保持穩(wěn)定，由于揮發(fā)機制的作用，弱勢解將逐漸被弱化，最后導致其被淘汰。同時，考慮權重的學習與更新，則在一輪搜索后，調(diào)整權重來調(diào)整加權后的總目標函數(shù)，最優(yōu)解的搜索可以根據(jù)優(yōu)化目標的實際需要而通過權重的變化而得到指導。讓m只Ant做多次搜索之后得出一個當時最優(yōu)解，然后將的各個分量細化重新建立搜索空間，重復以上過程，依次得到當停機條件滿足的時候得到最優(yōu)解并輸出。 4.結束語 蟻群算法作為通用型隨機優(yōu)化方法是根據(jù)螞蟻覓食時的行為特性而設計的, 該算法能在非常困難的情況下搜索到運輸

61、問題的最優(yōu)解。蟻群算法至今仍處于萌芽時期, 不管是理論還是應用都尚未成熟,因此有關這方面的研究仍需繼續(xù)下去, 而在多目標運輸中的應用也只是其中一例。如果能在參數(shù)設計方面取得突破, 相信該算法必能為許多領域的難題提供強有力的解決手段和工具。本文討論了改進的ACA算法思想以及在多目標運輸問題的最優(yōu)解求解中的應用，該算法通過隨機搜索同概率搜索結合，多個Ant并行求解，具有快速并能得到多個全局最優(yōu)解的優(yōu)點，現(xiàn)階段特別針對加權后的總目標優(yōu)化求解。 參考文獻: (1) 高 尚 楊靜宇 . 群智能算法及其應用 中國水利水電出版社。 (2) 張 軍 胡曉敏 羅旭耀 . 蟻群優(yōu)化 清

62、華大學出版社。 (3) 段海濱 蟻群算法原理及其應用 科學出版社。 (4) 李士勇 蟻群算法及其應用 哈爾濱工業(yè)大學出版社。 (5) 盧開澄 單目標、多目標與整數(shù)規(guī)劃 清華大學出版社。 南寧信息產(chǎn)業(yè)發(fā)展存在的問題與對策研究 數(shù)計學院 黃德智 【摘 要】本文通過詳實的相關調(diào)查和統(tǒng)計資料，對南寧的信息生產(chǎn)業(yè)、傳輸業(yè)、設備制造業(yè)、服務業(yè)等方面進行分析，得出現(xiàn)階段南寧信息產(chǎn)業(yè)各方面發(fā)展的具體情況。由現(xiàn)狀進一步研究南寧信息產(chǎn)業(yè)在區(qū)域經(jīng)濟發(fā)展中所面臨的形勢和存在的問題，著重從中國—東盟自由貿(mào)易區(qū)、泛北部灣區(qū)域經(jīng)濟區(qū)、信息產(chǎn)品技術、信息產(chǎn)業(yè)基礎設施和人才等七個方面

63、闡述南寧信息產(chǎn)業(yè)發(fā)展存在的問題。針對形勢和問題，從南寧信息產(chǎn)業(yè)發(fā)展方向、區(qū)域經(jīng)濟發(fā)展、產(chǎn)品特色等五個方面提出具有可行性的建議和對策。 【關鍵詞】信息產(chǎn)業(yè)；區(qū)域經(jīng)濟；面臨形勢；存在問題；發(fā)展對策 Nanning development of the information industry and the problems Countermeasures Huang De Zhi (Dept. of Mathematics and Computer Science, Guangxi University for Nationality Nanning 530006,China)

64、 【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 dev

65、elopment 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, informati

66、on 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