劉 曉 飛

(安慶師范大學(xué)，安徽 安慶 246133)

?

探究網(wǎng)絡(luò)圖的計算機算法和顯示方法

劉 曉 飛

(安慶師范大學(xué)，安徽 安慶 246133)

摘要：信息技術(shù)是人類發(fā)展的重要助推力，人類社會生產(chǎn)實踐中大部分問題的解決都依賴于計算機所構(gòu)建的數(shù)學(xué)模型，尤其是針對離散型結(jié)構(gòu)這一問題的解決，計算機數(shù)字技術(shù)可以充分發(fā)揮作用。本文圍繞網(wǎng)絡(luò)圖的計算機算法與顯示方法展開研究，簡要闡述了網(wǎng)絡(luò)圖的基本概念，著重介紹了網(wǎng)絡(luò)圖的計算機算法、顯示方法的發(fā)展進程，并對其未來發(fā)展方向進行分析和展望，以推動該學(xué)科的發(fā)展。

關(guān)鍵詞：網(wǎng)絡(luò)圖；計算機算法；顯示方法

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.020

網(wǎng)絡(luò)圖是一種圖解模型，主要由作業(yè)、事件、路線組成。隨著信息時代的到來，網(wǎng)絡(luò)圖已在通信網(wǎng)、工序流程以及電路網(wǎng)路等多個領(lǐng)域得到了廣泛應(yīng)用[1]。網(wǎng)絡(luò)圖能夠充分表現(xiàn)項目中各個工序之間相互依賴、相互制約的關(guān)系，同時使它們成為一個整體。具體來說，網(wǎng)絡(luò)圖能夠形象地表現(xiàn)整個工作計劃，在網(wǎng)絡(luò)圖中，可以利用編制程序進行計算，了解到工作的關(guān)鍵，抓住重點矛盾，避免盲目施工。人們可以利用網(wǎng)絡(luò)圖對原始網(wǎng)絡(luò)中的離散結(jié)構(gòu)及關(guān)系等問題進行定量與定性分析，并進一步優(yōu)化處理；同時根據(jù)這些邊與邊的權(quán)值頂點的鄰接關(guān)系來推斷圖的連通性和最短路徑。

在網(wǎng)絡(luò)圖的實際運用中，不同的計算機算法服務(wù)于不同的對象，需要加強對算法的研究，把技術(shù)、計算機理論與網(wǎng)絡(luò)圖控制算法相結(jié)合，應(yīng)用于其他領(lǐng)域，讓網(wǎng)絡(luò)圖真正為人們所用。

1網(wǎng)絡(luò)圖的控制算法

網(wǎng)絡(luò)圖在生活中運用十分廣泛，通過對點符號全控制算法和邊符號控制算法的研究與運用，能夠得出新的網(wǎng)絡(luò)圖系統(tǒng)。

1.1 點符號全控制算法的發(fā)展

點符號基礎(chǔ)理論是與全控制算法相結(jié)合的一種發(fā)展模式。點符號全控制算法融合了符號控制算法這一形式，引入了極限度，并對其最大和最小度進行限定。這種算法在下限過程中，能夠?qū)崿F(xiàn)下界之間的更新過程；在其圖像進行中，從下界問題更新這一角度，能夠保證滿足下界具體的網(wǎng)絡(luò)圖。在網(wǎng)絡(luò)圖全控制算法中，要保證符號具有一定的全面性和完整性。2001年，Zelinka第一次提出符號控制算法的概念。點符號全控制算法作為符號控制算法的一種形式，一直被人們研究、探討。2003年，刑化明等人給出了點符號全控制算法的下界[2-4]。2004年，MichaelAHenning給出了滿足這些下界的具體網(wǎng)絡(luò)圖。2006年，王軍秀對點符號全控制算法下界進行了改進，并給出了優(yōu)于原下界的新下界。2009年，呂新忠等進一步充實了全控制算法的內(nèi)容。改進后的網(wǎng)絡(luò)圖算法越來越受到學(xué)者的關(guān)注，需不斷地完善和改進。

1.2邊符號控制算法的發(fā)展

2001年，徐保根提出了邊符號控制算法的概念，并豐富、完善了網(wǎng)絡(luò)圖控制算法的內(nèi)容。2002年，BohdanZelinkaLiberec給出了界限，緊接著徐保根給出了邊符號控制算法的上界、下界及部分邊符號控制算法數(shù)的確切值，隨后又完善了邊控制算法數(shù)的界限。減控制算法是邊符號控制算法中的一種，但由于減控制算法研究難度大，研究時間短，因此在這方面還沒有太多成果，故研究人員要加強對減控制算法的研究。

1.3點符號、邊符號控制算法的發(fā)展所帶來的影響

點符號和邊符號控制算法的發(fā)展能構(gòu)成了一個網(wǎng)絡(luò)圖顯示和查詢系統(tǒng)，但這種查詢系統(tǒng)不穩(wěn)定，如果對它進行多次修改，很難調(diào)出操作的歷史記錄，同時圖像也會顯得古板、模糊。因此，對點符號控制算法和邊符號控制算法進行改進時要充分發(fā)揮數(shù)據(jù)庫的作用，只有這樣才能有效解決數(shù)據(jù)查詢難度大的問題。

1.4網(wǎng)絡(luò)圖計算機算法的完善

在網(wǎng)絡(luò)時代，人們對計算機算法提出了新的要求。2009年，呂新忠和儀明源獲得了集中類型特殊網(wǎng)絡(luò)圖的符號全控制算法數(shù)，進一步充實了符號全控制算法的內(nèi)容。其實在更早之前，反符號算法已經(jīng)得到了實際應(yīng)用，將反符號算法逐漸發(fā)展成為反符號全控制算法，是未來網(wǎng)絡(luò)圖算法的研究重點，也是目前需要關(guān)注的內(nèi)容。此外，在完善邊符號算法過程中，一些學(xué)者通過研究，獲得了部分特殊網(wǎng)絡(luò)圖符號邊控制算法數(shù)的確切值，得到了一般網(wǎng)絡(luò)圖的界限。根據(jù)現(xiàn)有的理論成果和現(xiàn)實條件，邊上的減控制算法具有一定的難度，通過研究可以得出，下一步研究的重點是減K邊控制算法，應(yīng)該要把減邊控制算法定義中要求滿足“全部邊” 的條件改作“至少有K條邊”，但是該研究同樣具有一定的難度，目前該項研究仍在進一步發(fā)展中。

此外，人們希望通過對最短路徑的研究，在確保算法準(zhǔn)確性的同時縮小算法的搜索空間，減輕機器的負(fù)荷，提高運行效率，使網(wǎng)絡(luò)圖的計算更加容易。最短路徑算法的計算復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的變化而變化。由于網(wǎng)絡(luò)中節(jié)點數(shù)n與連邊數(shù)m的增大具有相關(guān)性，通常利用降階的方式構(gòu)建網(wǎng)絡(luò)層次化模型，簡化網(wǎng)絡(luò)的拓?fù)潢P(guān)系，降低算法的復(fù)雜度。網(wǎng)絡(luò)中包含節(jié)點和邊的數(shù)量隨著網(wǎng)絡(luò)分層等級的升高而減少，通過將搜索切換到高層拓?fù)渲心軌驕p少計算過程中節(jié)點的數(shù)量，達到提高算法運行效率的目的。在最短路徑算法中，搜索的盲目性會造成搜索的極大浪費。利用加速引導(dǎo)技術(shù)減少計算過程中節(jié)點的數(shù)量，降低算法的復(fù)雜度。搜索策略對于最短路徑算法的計算效率和精度的好壞都有重要影響，通過對搜索策略的優(yōu)化能夠獲取最快的路徑響應(yīng)速度，提高路徑計算精度，降低存儲空間的消耗，增強算法的通用性。

2網(wǎng)絡(luò)圖的顯示方法及算法

2.1網(wǎng)絡(luò)圖的計算機顯示理論基礎(chǔ)

網(wǎng)絡(luò)圖的計算機顯示理論基礎(chǔ)是利用C語言實現(xiàn)網(wǎng)絡(luò)圖的繪制，主要是基于兩點原因：一是C語言簡潔、功能較大適宜在屏幕上作圖；二是利用C語言編寫程序所占用的內(nèi)存相對較少、執(zhí)行率高[5-6]。在網(wǎng)絡(luò)圖的點連線分析中，常常存在著錯綜復(fù)雜的頂點與邊的關(guān)系。通常研究人員對網(wǎng)絡(luò)圖進行繪制時會先畫出各頂點，接著將各頂點用線連接起來。工作人員在用C語言作圖時，采用的是物理坐標(biāo)，水平方向是X軸，向右為正，向左為負(fù)；垂直方向是Y軸，向下為正，向上為負(fù)。工作人員在利用坐標(biāo)(X，Y)表示各點時，X，Y必須是整數(shù)且有一定的取值范圍。

圖形繪制出來后為了讓圖形的大小、位置適宜，所以需對圖形進行縮放、平移、旋轉(zhuǎn)等操作。在完成圖的顯示算法過程中，常常會控制網(wǎng)絡(luò)圖，添加或刪除若干條邊、若干個頂點，并在歷史查詢中詳細(xì)記錄時間。

2.2完成圖的顯示算法所需的步驟

(1)研究人員通過用戶信息在屏幕上繪制出完整的圖形。

(2)在輸入用戶的信息后，根據(jù)信息繪制出相應(yīng)的圖像，同時要用不同顏色對新添加的邊進行描繪。

(3)通過用戶新添加的點構(gòu)成連通圖，用戶新添加的信息包括邊的信息，最后繪制出圖像，要用不同顏色對新添加的頂點和邊進行描繪。

(4)在繪制相應(yīng)的圖像時，同時要刪除邊，邊刪除后不能有孤立的頂點。

(5)繪制相應(yīng)的圖像時，同時要刪除相應(yīng)的頂點，與頂點相關(guān)聯(lián)的邊也要去掉。

(6)對于每次操作都要做好記錄，以便日后查詢。

(7)對于每次操作都要觀測操作的時間。

(8)在構(gòu)建網(wǎng)絡(luò)圖顯示和查詢系統(tǒng)時，要考慮圖的連通性查詢和最短路徑查詢。

2.3網(wǎng)絡(luò)圖顯示圖中需注意的問題

工作人員在使用網(wǎng)絡(luò)圖時要注意在輸入數(shù)據(jù)、添加邊和添加點時的細(xì)節(jié)性問題。在輸入數(shù)據(jù)時，首先要輸入指令，接著輸入相關(guān)信息。信息中一般包含了頂點的個數(shù)和編號、邊的數(shù)目和編號、頂點的坐標(biāo)，最后創(chuàng)建鄰接多重表時要將數(shù)據(jù)輸入其中。在輸入添加邊和頂點時，首先要輸入指令，接著輸入相關(guān)數(shù)目，相關(guān)數(shù)目中包括邊的起點與終點個數(shù)和新添加頂點的個數(shù)，同時要對添加邊頂點進行編號， 要對鄰接多重表進行修改，最后完成對網(wǎng)絡(luò)圖的繪制。在輸入對邊和頂點的過程中，要同時進行邊與定點的指令添加，輸入新添加數(shù)目。添加新頂點的過程往往具有孤立性特點，在網(wǎng)絡(luò)不完整連通情況下，常常要結(jié)合基礎(chǔ)性環(huán)節(jié)，對網(wǎng)絡(luò)圖進行基本控制[7-8]。因而，在網(wǎng)絡(luò)圖的計算機算法與實際顯示中，是將點符號全控制算法與邊符號全控制算法作為基礎(chǔ)的，在網(wǎng)絡(luò)圖的實際控制算法應(yīng)用過程中，要進一步完善網(wǎng)絡(luò)圖的設(shè)計，提高計算機算法及顯示系統(tǒng)的工作效率[9-10]。

3結(jié)語

隨著科技的進步，網(wǎng)絡(luò)圖理論也有了較快的發(fā)展。網(wǎng)絡(luò)圖理論能夠有效地離散事物結(jié)構(gòu)和關(guān)系，有助于優(yōu)化定性或定量層面的問題，同時實現(xiàn)問題的數(shù)學(xué)化和嚴(yán)謹(jǐn)化。利用點和線來解決、分析問題，把很多解決實際問題的方法回歸到建立數(shù)學(xué)模型中。但是，目前我國工控系統(tǒng)正朝著開放化與智能化方向發(fā)展，這在給用戶帶來巨大便利的同時，也存在一定的安全隱患，例如PLC未對外來數(shù)據(jù)進行驗證、工業(yè)以太網(wǎng)有安全漏洞等，如何在完善系統(tǒng)功能、優(yōu)化操作流程的基礎(chǔ)上提高計算機算法的準(zhǔn)確性，進而保證工控系統(tǒng)安全，成為一個需要長期探索和研究的課題。計算機技術(shù)迅速發(fā)展促進了算法理論的控制和發(fā)展。未來要加強網(wǎng)絡(luò)圖在計算機網(wǎng)絡(luò)、拓?fù)浣Y(jié)構(gòu)和編碼理論等領(lǐng)域中的運用，讓網(wǎng)絡(luò)圖更好地為人們服務(wù)。

參考文獻:

[1] 高富.基于網(wǎng)絡(luò)圖的計算機算法分析[J].電子技術(shù)與軟件工程,2014,54(21):20.

[2] 徐瑾.網(wǎng)絡(luò)圖的計算機算法和顯示方法的研究[J].文理導(dǎo)航,2015,45(5)(下旬):6.

[3] 王凌燕.網(wǎng)絡(luò)圖的計算機算法和顯示方法的研究[J].電子技術(shù)與軟件工程,2015,89(1):189-190.

[4] 王莉.網(wǎng)絡(luò)圖的計算機算法和顯示方法研究[J].山東農(nóng)業(yè)工程學(xué)院學(xué)報,2015,56(3):42-43, 46.

[5] 付欣.網(wǎng)絡(luò)圖的計算機算法和顯示方法的研究[J].電腦知識與技術(shù),2013,68(35):7946-7947.

[6] 劉乃維.論網(wǎng)絡(luò)圖的計算機算法[J].計算機光盤軟件與應(yīng)用,2014,89(13):95-96.

[7] 吳凱,李鵬,何永強.控制算法理論及網(wǎng)絡(luò)圖計算機算法顯示研究[J].現(xiàn)代電子技術(shù),2015,17: 151-152, 157.

[8] 張宏國,王強.CPM網(wǎng)絡(luò)圖計算機自動繪制算法設(shè)計[J].信息技術(shù),2001,8:14-16.

[9] 趙建齊.基于并行化的網(wǎng)絡(luò)圖壓縮表示算法的研究[D].北京: 北京交通大學(xué), 2014.

[10] 李添捷.生物醫(yī)學(xué)圖像融合顯示方法的研究[D].上海: 復(fù)旦大學(xué),2012.

ComputerAlgorithmandDisplayMethodofNetworkGraph

LIUXiao-fei

(SchoolofComputerandInformation,AnqingNormalUniversity,Anqing,Anhui246133,China)

Abstract:Informationtechnologyisanimportantboostofhumandevelopment.Tosolvethemostproblemsoftheproductionpracticeinhumansocietydependsonthecomputertobuildmathematicalmodel,especiallyfordiscretestructure.Thecomputerdigitaltechnologycanplayavitalroleinsolvingthisproblem.Thispaperfocusesonthecomputeralgorithmofnetworkdiagramanddisplaymethod,brieflyexpoundsthebasicconceptofnetworkdiagram,emphaticallyintroducesthenetworkgraphofcomputeralgorithm,displaysthemethodofthedevelopmentprocess,analyzesandoutlooksitsfuturedevelopmentdirection,whichcanpromotethedevelopmentofthediscipline.

Keywords:Networkdiagram;computeralgorithms;displaymethod

* 收稿日期：2015-09-17

作者簡介：劉曉飛，男，山東泰安人，碩士，安慶師范大學(xué)副教授，研究方向為計算機軟件及相關(guān)。E-mail: flyine@vip.qq.com

中圖分類號：TP338.8

文獻標(biāo)識碼：A

文章編號：1007-4260(2016)02-0086-03

網(wǎng)絡(luò)出版時間：2016-06-08 12:57網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.020.html