基于網(wǎng)絡(luò)圖的計(jì)算機(jī)算法分析

高富

本文從網(wǎng)絡(luò)圖理論中的控制算法理論入手，就網(wǎng)絡(luò)圖的計(jì)算機(jī)算法進(jìn)行了簡(jiǎn)單的闡述。

【關(guān)鍵詞】網(wǎng)絡(luò)圖 計(jì)算機(jī) 算法

自進(jìn)入信息時(shí)代以來，我國科學(xué)技術(shù)水平得到巨大程度的提升，特別是計(jì)算機(jī)的發(fā)展。而隨著人類科學(xué)和計(jì)算機(jī)水平的全面提升，極大地程度上促使了計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)圖圖論之間的緊密結(jié)合，特別是在處理離散型結(jié)構(gòu)問題方面。無論在定量還是定性方面上，網(wǎng)絡(luò)圖理論都可以對(duì)相關(guān)問題進(jìn)行優(yōu)化。因此，基于網(wǎng)絡(luò)圖的計(jì)算機(jī)算法問題已經(jīng)成為網(wǎng)絡(luò)圖理論中一項(xiàng)重要的研究?jī)?nèi)容。

1 繪制網(wǎng)絡(luò)圖遵循的規(guī)則

（1）依據(jù)計(jì)算機(jī)運(yùn)算的流程和順序，按照從左向右的排列順序?qū)ζ溥M(jìn)行施工。

（2）在條件允許的情況下，盡量使用虛工序（不需要人、物力）來表達(dá)相鄰工序之間的相互鏈接關(guān)系。

（3） 網(wǎng)絡(luò)圖中不可以有任何的回路和缺口，無論如何布置，都要確保網(wǎng)絡(luò)圖從始點(diǎn)出發(fā)，經(jīng)過一定的網(wǎng)絡(luò)路線后均可到達(dá)終點(diǎn)。

（4）一個(gè)合理的網(wǎng)絡(luò)圖應(yīng)只包含一個(gè)終點(diǎn)和起點(diǎn)。

（5）網(wǎng)絡(luò)圖布局規(guī)劃。為了使網(wǎng)絡(luò)圖清楚、有序，在對(duì)其進(jìn)行規(guī)劃過程中，首先，要盡可能地將關(guān)鍵的線路布置在網(wǎng)絡(luò)圖的中間（心）位置；其次，要把相互之間具有聯(lián)系關(guān)系的工作布置在一起；最后，要盡量使用一段水平的折現(xiàn)或者水平線來描述網(wǎng)絡(luò)圖的線路。此外，還可以在網(wǎng)絡(luò)圖上附錄時(shí)間進(jìn)度，如果在必要的時(shí)候，還可以按照工序來布置網(wǎng)絡(luò)圖。

2 計(jì)算機(jī)算法設(shè)計(jì)

2.1 整體思路

計(jì)算機(jī)整體算法設(shè)計(jì)所依據(jù)的思路為：通過將具有相互聯(lián)系的工序的節(jié)點(diǎn)設(shè)置成同樣的編號(hào)，并在對(duì)數(shù)據(jù)表進(jìn)行處理操作過程中，將已知的施工工序通過特定的算法使其與相鄰工序的節(jié)點(diǎn)進(jìn)行一一對(duì)應(yīng)，同時(shí)使匯點(diǎn)、源點(diǎn)編號(hào)呈唯一狀態(tài)，并要滿足上述的網(wǎng)絡(luò)圖的繪制規(guī)則；然后將已經(jīng)處理的節(jié)點(diǎn)進(jìn)行恰當(dāng)?shù)胤旨?jí)處理，并將聯(lián)系緊密的節(jié)點(diǎn)轉(zhuǎn)化為緊前緊后關(guān)系，在這兩個(gè)特定的接點(diǎn)處需要用線尾加以標(biāo)識(shí)，在箭線的中間部位標(biāo)出對(duì)應(yīng)工序的代碼；對(duì)于關(guān)鍵的工序需要用紅色來突出顯示。

2.2 具體算法

為了更好的理解計(jì)算機(jī)的具體算法，在介紹算法之前，首先介紹幾個(gè)基本概念。首先，始點(diǎn)工序主要代表網(wǎng)絡(luò)計(jì)劃中所允許的、不止一個(gè)、最先開工的工序，其具有無緊前工序的特點(diǎn)；其次，所謂的終點(diǎn)工序主要是指在網(wǎng)絡(luò)計(jì)劃當(dāng)中所規(guī)定的最后完工工序，具有無緊后工序的特點(diǎn)。

2.2.1網(wǎng)絡(luò)活動(dòng)邏輯關(guān)系的數(shù)字化

所謂的網(wǎng)絡(luò)活動(dòng)邏輯關(guān)系數(shù)字化主要是指在網(wǎng)絡(luò)圖中各個(gè)工序之間的節(jié)點(diǎn)編號(hào)的關(guān)系。

（1） 確定始點(diǎn)工序的首尾節(jié)點(diǎn)編號(hào)。

（2）確定始點(diǎn)工序的緊后工序的開始節(jié)點(diǎn)編號(hào)。

（3）確定中間工序的節(jié)點(diǎn)編號(hào)。

（4）確定匯點(diǎn)。

2.2.2 節(jié)點(diǎn)排序

在經(jīng)過上述四個(gè)步驟的處理后，待所有工序的節(jié)點(diǎn)都已經(jīng)賦值完成后，但無需定要確保其始發(fā)節(jié)點(diǎn)的號(hào)碼均要小于結(jié)束節(jié)點(diǎn)的編號(hào)。根據(jù)上述的網(wǎng)絡(luò)圖的繪制規(guī)則對(duì)節(jié)點(diǎn)的號(hào)碼編號(hào)進(jìn)行恰當(dāng)?shù)嘏判?。具體的思路為：首先需要找出開始節(jié)點(diǎn)的編號(hào)大于結(jié)束節(jié)點(diǎn)的編號(hào)n，m，并對(duì)所有工序的始發(fā)及結(jié)束節(jié)點(diǎn)進(jìn)行行之有效的判斷，如果其是m則需要將其換為n，而假如其是n則需要將其換為m，重復(fù)該步驟，直至所有存在的工序的節(jié)點(diǎn)編號(hào)均小于結(jié)束節(jié)點(diǎn)的編號(hào)為止。

2.2.3 節(jié)點(diǎn)分級(jí)

節(jié)點(diǎn)的合理布局是網(wǎng)絡(luò)圖繪制好壞的關(guān)鍵。因此，為了確保節(jié)點(diǎn)布局順序的合理性，通常在編制編號(hào)的過程中采取先左后右，自上而下的原則來進(jìn)行編號(hào)處理，此外，還需要對(duì)節(jié)點(diǎn)進(jìn)行適當(dāng)?shù)姆旨?jí)，然后將同級(jí)節(jié)點(diǎn)來進(jìn)行分層布局。雜計(jì)算機(jī)進(jìn)行繪制箭線圖和設(shè)計(jì)的時(shí)候，為了保證工序流程的合理性也需要對(duì)箭線圖中的節(jié)點(diǎn)進(jìn)行適當(dāng)?shù)姆旨?jí)。

2.2.4 網(wǎng)絡(luò)圖繪制

首先，需要確定原點(diǎn)的坐標(biāo)，然后選取一個(gè)適當(dāng)?shù)妮d體來繪制出若干個(gè)大小相等的圓，其次在用箭線將所繪制出的圓進(jìn)行串聯(lián)起來，并要在箭線上面標(biāo)志出特定的信息，但是要確保所有繪制的圓均是按照特定的規(guī)則來進(jìn)行布局的。

（1）根據(jù)上述節(jié)點(diǎn)分級(jí)的原則進(jìn)行分級(jí)后，為了方便將來的運(yùn)算，就可以確定各種不同的層次供以畫圓，并將每一級(jí)的節(jié)點(diǎn)數(shù)目統(tǒng)計(jì)到相應(yīng)的容器當(dāng)中。

（2）在每一級(jí)上進(jìn)行圓圈繪制過程中，為了確保圓圈分布的均勻性，需要使每個(gè)圓圈之間均相隔一定的距離，即使在同一級(jí)上面也需要間隔固定的距離，但是如果每級(jí)上面節(jié)點(diǎn)的數(shù)目不同，則他們之間的距離也各不相同。

（3）為了確定每一級(jí)上的圓的間隔，需要根據(jù)該級(jí)上面節(jié)點(diǎn)的數(shù)目來進(jìn)行綜合確定。假如該級(jí)上面只有一個(gè)節(jié)點(diǎn)，則需要將其放置在載體的中間，但是如果某一級(jí)上的節(jié)點(diǎn)數(shù)目呈現(xiàn)出偶數(shù)，則需要在縱軸方向（Y方向）上下兩方進(jìn)行布置，反之，如果節(jié)點(diǎn)的數(shù)目為奇數(shù)狀態(tài)，則需要讓它們的縱坐標(biāo)的本身及其兩側(cè)呈現(xiàn)出均勻性的分布狀態(tài)。

（4）確定節(jié)點(diǎn)坐標(biāo)。鑒于匯點(diǎn)、源點(diǎn)的唯一性，在確定源點(diǎn)的坐標(biāo)時(shí)候，首先需要將橫坐標(biāo)（X）取一個(gè)固定的數(shù)值，縱坐標(biāo)Y方向上選取載體高度的一半，然后再確定級(jí)次之間的間距N，最后所得到的級(jí)次節(jié)點(diǎn)的橫坐標(biāo)即為：X+幾次*N，而縱坐標(biāo)的確定則想見步驟c。

（5）在確定節(jié)點(diǎn)坐標(biāo)后，則開始進(jìn)行圓圈的繪制，在繪制圓圈的時(shí)候需要寫上該節(jié)點(diǎn)的編號(hào)。

（6）待上述的五個(gè)步驟全部完成后，一張沒有箭頭標(biāo)志的網(wǎng)絡(luò)草圖已經(jīng)基本成型。余下的就需要根據(jù)節(jié)點(diǎn)及其緊前和緊后節(jié)點(diǎn)之間的相互關(guān)系來進(jìn)行箭頭的繪制，以表示工序的流向。

（7）為了使網(wǎng)絡(luò)圖更具有實(shí)用性，以更便于用戶審讀網(wǎng)絡(luò)圖，在箭線上還需要標(biāo)識(shí)出工序的有關(guān)信息。

3 總結(jié)

網(wǎng)絡(luò)圖的理論掀起了濃厚的研究高潮，新的理論成果如雨后春筍不斷涌現(xiàn)，作為控制算法理論研究的先驅(qū)者，我們不僅要在基于網(wǎng)絡(luò)圖的計(jì)算機(jī)算法理論上進(jìn)行研究，還應(yīng)引領(lǐng)那些年輕的學(xué)者在浩瀚的研究大海中尋找方向和明確目標(biāo)。

參考文獻(xiàn)

[1] 張彩慶，王婷.網(wǎng)絡(luò)圖自動(dòng)生成算法研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013，（12）：45-46.

[2] 畢義明，楊軍等.網(wǎng)絡(luò)圖的自動(dòng)生成算法及其系統(tǒng)實(shí)現(xiàn)[J].雜技教育，2012，（1）：70-71.

[3] 付欣.網(wǎng)絡(luò)圖的計(jì)算機(jī)算法和顯示方法的研究[J].電腦知識(shí)與技術(shù)，2013，（3）：109-109.

作者單位

江蘇省沭陽中等專業(yè)學(xué)校 江蘇省宿遷市 223600endprint