何廣

摘要：本文介紹如何巧妙地應(yīng)用多智能體網(wǎng)絡(luò)來解釋運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析教學(xué)中有關(guān)圖的一些概念，比如：連通性，度，支撐樹等，從而使得我們的教學(xué)更加生動(dòng)與形象，同時(shí)也使得學(xué)生對這些概念的理解更加深刻。

Abstract： This paper introduces how to use multi-agent networks to explain some concepts related to map graphs such as connectivity， degree， support tree in the teaching of operational research map and networks analysis， which makes our teaching more vivid and image， and also makes students understand these concepts more deeply.

關(guān)鍵詞： 聯(lián)通圖；支撐樹；多智能體

Key words： connected graph；support tree；multi-agent

中圖分類號：TB114.1 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2017）21-0238-02

0 引言

運(yùn)籌學(xué)作為科學(xué)名字最早出現(xiàn)在20世紀(jì)30年代末，那時(shí)候的運(yùn)籌學(xué)可以說就是戰(zhàn)爭的“工具”，當(dāng)時(shí)中英美借助運(yùn)籌學(xué)的思想，強(qiáng)有力的打擊了德意日三國，為二戰(zhàn)的勝利奠定了基礎(chǔ)。二戰(zhàn)勝利后運(yùn)籌學(xué)被廣泛的應(yīng)用到工農(nóng)業(yè)生產(chǎn)的各個(gè)領(lǐng)域，大大的提高了我們的生產(chǎn)效率，這也促使近幾十年運(yùn)籌學(xué)獲得了空前的發(fā)展。圖與網(wǎng)絡(luò)分析作為運(yùn)籌學(xué)的一個(gè)重要分支，現(xiàn)如今已被廣泛的應(yīng)用到物理、化學(xué)、控制論、信息論，科學(xué)管理、電子計(jì)算機(jī)等各個(gè)領(lǐng)域[1]。在實(shí)際生活、生產(chǎn)和科學(xué)研究中，有很多問題可以用圖論的理論和方法來解決。因此在運(yùn)籌學(xué)的教學(xué)中如何能夠使學(xué)生更加深刻的理解圖與網(wǎng)絡(luò)分析就顯得尤為重要。在該章節(jié)的教學(xué)中引用一些更實(shí)際的網(wǎng)絡(luò)的例子來解釋有關(guān)網(wǎng)絡(luò)的概念無疑能夠使教學(xué)更加生動(dòng)易懂。而多智能體網(wǎng)絡(luò)是近20年控制領(lǐng)域的研究熱點(diǎn)[2]，利用多智能體網(wǎng)絡(luò)來解釋圖的有關(guān)概念既能拓廣學(xué)生的視野，又能使學(xué)生更容易理解，從而調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性，進(jìn)而使得我們的教學(xué)效果得到大幅度提高。

1 多智能體網(wǎng)絡(luò)與圖

眾所周知，許多網(wǎng)絡(luò)都可以看成是多智能體網(wǎng)絡(luò)，如無人機(jī)網(wǎng)絡(luò)，移動(dòng)機(jī)器人網(wǎng)絡(luò)，那么這些網(wǎng)絡(luò)和圖有什么關(guān)系呢？當(dāng)我們把無人機(jī)抽象成頂點(diǎn)，兩架無人機(jī)之間如果有信息交流就連一條邊，這樣無人機(jī)網(wǎng)絡(luò)就可以看成一個(gè)圖，如果我們這樣去解釋圖能夠使很多同學(xué)相信原來圖真的可以包含很多復(fù)雜的內(nèi)容，圖真的可以和很多的實(shí)際問題產(chǎn)生密切的聯(lián)系，從而激起同學(xué)學(xué)習(xí)圖論的興趣。

2 有向圖與無向圖

在圖論中為什么要把圖分成有向圖和無向圖呢？他們的區(qū)別的本質(zhì)又在哪里呢？我們可以借助多智能體網(wǎng)絡(luò)跟同學(xué)們這樣解釋：在有些無人機(jī)網(wǎng)絡(luò)中信息的交流是相互的，無人機(jī)甲可以接收到向無人機(jī)已的信息，同時(shí)無人機(jī)已也可以接收到無人機(jī)甲的信息，即信息可以在這兩架無人機(jī)之間共享互通，這樣形成的圖就是無向圖；而在有些無人機(jī)網(wǎng)絡(luò)中信息交流可能是單向的，無人機(jī)甲可以接收無人機(jī)已的信息，而無人機(jī)已卻不能接收無人機(jī)甲的信息，這樣形成的圖就是有向圖，如果我們能這樣去解釋有向圖和無向圖而不在拘泥于“單行線和雙行線”，肯定能夠使同學(xué)們對于有向圖和無向圖的理解更加深刻，也使之能夠明白為什么非要把圖分成有向圖和無向圖來進(jìn)行研究。

3 連通性的概念與意義

所謂圖的連通性是指圖中的任意兩個(gè)頂點(diǎn)都是連通的，也即是任意兩個(gè)頂點(diǎn)之間都存在一條初等鏈。而針對無人機(jī)網(wǎng)絡(luò)，所謂連通性是指任意兩個(gè)無人機(jī)即使兩者之間不能進(jìn)行直接的信息交流也能夠借助其他的無人機(jī)進(jìn)行間接的信息交流，從而實(shí)現(xiàn)信息的共享。

如圖1的無人機(jī)網(wǎng)絡(luò)就是一個(gè)聯(lián)通圖，而圖2的無人機(jī)網(wǎng)絡(luò)已就是不聯(lián)通的。對于無人機(jī)網(wǎng)絡(luò)來說連通性意味著什么呢？這意味著這個(gè)無人機(jī)網(wǎng)絡(luò)可以實(shí)現(xiàn)網(wǎng)絡(luò)一致性[3]，所謂網(wǎng)絡(luò)一致性是指網(wǎng)絡(luò)的一種集體行為，即每一個(gè)無人機(jī)的狀態(tài)（或者說行為）可以趨近于一致，而多智能體網(wǎng)絡(luò)的一致性問題是當(dāng)今控制論領(lǐng)域研究的一個(gè)熱點(diǎn)問題，這個(gè)時(shí)候?qū)W生會(huì)明白原來連通性背后隱藏著這么大的意義??！同時(shí)也進(jìn)一步的拓廣了同學(xué)們的視野，使他們明白了圖與網(wǎng)絡(luò)分析在當(dāng)今科學(xué)研究的前沿中起到了多么重要的作用，從而激起他們對圖論學(xué)習(xí)的積極性。這時(shí)候我們可以誘導(dǎo)學(xué)生思考這樣一個(gè)問題：在一個(gè)無人機(jī)網(wǎng)絡(luò)中，整個(gè)網(wǎng)絡(luò)時(shí)時(shí)刻刻都不是聯(lián)通的，那么這個(gè)時(shí)候整個(gè)網(wǎng)絡(luò)還能實(shí)現(xiàn)一致性嗎？

比如整個(gè)網(wǎng)絡(luò)可能在圖3和圖4兩個(gè)網(wǎng)絡(luò)中進(jìn)行著隨機(jī)切換，這兩個(gè)網(wǎng)絡(luò)都不是聯(lián)通的，那么這個(gè)時(shí)候網(wǎng)絡(luò)能實(shí)現(xiàn)一致性嗎？

回答是肯定的。最新的研究結(jié)果表明，只要整個(gè)網(wǎng)絡(luò)是“聯(lián)合聯(lián)通”的，網(wǎng)絡(luò)就能夠?qū)崿F(xiàn)一致性[3，4]，而圖3和圖4的并就是圖1，而圖1是聯(lián)通圖，因此多智能體網(wǎng)絡(luò)在圖3和圖4之間相互切換時(shí)，整個(gè)網(wǎng)絡(luò)是可以實(shí)現(xiàn)一致性的。從而我們能夠引入一個(gè)新的概念“聯(lián)合聯(lián)通”，所謂聯(lián)合聯(lián)通是指當(dāng)整個(gè)網(wǎng)絡(luò)在若干個(gè)拓?fù)浣Y(jié)構(gòu)上切換時(shí)，如果這些拓?fù)浣Y(jié)構(gòu)的并是一個(gè)聯(lián)通網(wǎng)絡(luò)，這時(shí)候就稱隨時(shí)間演化的網(wǎng)絡(luò)是聯(lián)合聯(lián)通的。而“聯(lián)合聯(lián)通”這個(gè)概念在現(xiàn)在的大多數(shù)的運(yùn)籌性的教科書中都沒有出現(xiàn)，從而能夠進(jìn)一步的擴(kuò)大學(xué)生的知識面。

4 支撐樹的概念與意義

在講到支撐樹的概念的時(shí)候我們可以先讓同學(xué)們比較兩個(gè)無人機(jī)網(wǎng)絡(luò)圖5和圖6，問問同學(xué)們，這兩個(gè)網(wǎng)絡(luò)哪個(gè)網(wǎng)絡(luò)可能更能夠節(jié)約通信成本。從而我們能夠引入樹與支撐樹的概念。使得學(xué)生能夠明白要想實(shí)現(xiàn)網(wǎng)絡(luò)一致性在聯(lián)通性的基礎(chǔ)上網(wǎng)絡(luò)還可以進(jìn)一步的簡化，即網(wǎng)絡(luò)圖只要存在支撐樹多智能體網(wǎng)絡(luò)就能夠?qū)崿F(xiàn)一致性，從而求一個(gè)聯(lián)通圖的最小生成樹就顯得尤為重要，因?yàn)閷τ诙嘀悄荏w網(wǎng)絡(luò)來說求一個(gè)聯(lián)通圖的最小支撐樹問題就是節(jié)約通信成本的問題，在當(dāng)今資源緊缺的情況下節(jié)約成本的意義是顯而易見的。

實(shí)際上，在圖論中的很多概念的講解都可以借組多智能體網(wǎng)絡(luò)，比如：度與連接矩陣的概念等，在這里就不一一敘述了。

5 結(jié)論

圖與網(wǎng)絡(luò)分析中的很多概念的講解都可以借助多智能體這個(gè)實(shí)際網(wǎng)絡(luò)，這樣做不僅能夠使問題變的通俗易懂，使學(xué)生對于概念的理解更加深刻，同時(shí)也拓廣了學(xué)生的知識面，從而極大地提高教學(xué)效果。

參考文獻(xiàn)：

[1] 錢頌迪，《運(yùn)籌學(xué)》，清華大學(xué)出版社，1981.09.

[2]Georg S. Seyboth， Dimos V. Dimarogonas， Karl H. Johansson， Event based broadcasting for multi-agent average consensus， Automatica， 49：245-252，2013.

[3]Ali Jadbabaie， Jie Li， A. Stephen Morse， Coordination of groups of mobile autonomous agents using nearest neighbor rules， IEEE Transactions on Automatic Control， 48（6）：988-1000，2003.

[4]Wei Ren， Randal W. Beard， Consensus seeking in multiagent systems under dynamically changing interaction topologies， IEEE Transactions on Automatic Control， 50（5）：655-661，2005.