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

劉 曉 飛

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

?

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

劉 曉 飛

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

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

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

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

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

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

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

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

1.1 點(diǎn)符號(hào)全控制算法的發(fā)展

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

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

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

1.3點(diǎn)符號(hào)、邊符號(hào)控制算法的發(fā)展所帶來的影響

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

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

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

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

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

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

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

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

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

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

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

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

(4)在繪制相應(yīng)的圖像時(shí)，同時(shí)要?jiǎng)h除邊，邊刪除后不能有孤立的頂點(diǎn)。

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

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

(7)對(duì)于每次操作都要觀測(cè)操作的時(shí)間。

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

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

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

3結(jié)語

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

參考文獻(xiàn):

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

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

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

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

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

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

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

[8] 張宏國(guó),王強(qiáng).CPM網(wǎng)絡(luò)圖計(jì)算機(jī)自動(dòng)繪制算法設(shè)計(jì)[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

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

中圖分類號(hào)：TP338.8

文獻(xiàn)標(biāo)識(shí)碼：A

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

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