高富

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

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

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

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

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

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

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

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

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

2 計算機算法設(shè)計

2.1 整體思路

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

2.2 具體算法

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

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

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

（1） 確定始點工序的首尾節(jié)點編號。

（2）確定始點工序的緊后工序的開始節(jié)點編號。

（3）確定中間工序的節(jié)點編號。

（4）確定匯點。

2.2.2 節(jié)點排序

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

2.2.3 節(jié)點分級

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

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

參考文獻(xiàn)

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

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

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

作者單位

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