基于二叉樹的糧食筒倉工藝流程選擇算法的實現及應用

魏鵬飛　蘇亞洲

摘 要：隨著控制系統規模的擴大，流程選擇的復雜程度倍增，傳統的流程矩陣選擇算法已不能處理上述問題。本文基于計算機的成熟二叉樹理論及其遍歷算法，通過對筒倉工藝流程的設備上下游關系進行特殊處理，得到基于二叉樹的糧食筒倉工藝流程選擇算法。該算法為大規模的筒倉工藝流程選擇提供了新的的思路。

關鍵詞：流程矩陣;二叉樹;遍歷算法;流程選擇

Abstract：With the expansion of control system scale and the complexity of process selection， the traditional process matrix selection algorithm cant deal with the above problems. Based on the mature binary tree theory of computer and its traversal algorithm， the process selection algorithm of grain silo is obtained by special processing of the relationship between the upstream and downstream equipments of the silo process. This algorithm provides a new and feasible way for large-scale silo process selection and control.

Key words：Process matrix; Binary tree; Traversal algorithm; Process selection

中圖分類號：TP311.1

近年來，隨著國際糧食物流貿易的蓬勃發展和國家對糧食倉儲投資力度的增加，糧食倉儲企業的業務范圍不斷擴大，企業擁有的倉容也逐年擴大，筒倉生產控制系統的規模伴隨著受控設備的增多而越來越龐大，流程選擇的復雜程度更是成倍增加。當項目分期建設時，為保證分期項目工藝流程的整體性，需將多期項目整體考慮，這樣工藝流程選擇成為控制人員的最大障礙。

1 筒倉控制系統的現狀與問題

對小型的筒倉控制系統（工藝流程條數≤300條），采用流程矩陣進行流程的選擇與控制，這種方法目前已在多個項目中成功應用。隨著控制系統規模的擴大，流程矩陣算法弊端日益顯露，主要表現在隨著設備受控數量成倍的擴大，流程條數指數級的增多，矩陣的規模指數級擴大，使流程選擇的復雜度急劇增加[1-2]。流程矩陣的選擇算法顯然已經不適于處理上述復雜的問題。因此，迫切需要一種全新的流程選擇算法，用來解決上述問題。

2 理論基礎

基于成熟的二叉樹理論和遍歷算法，同時通過對筒倉工藝流程中的設備關系進行特殊處理，轉化為標準的二叉樹結構，得到了基于二叉樹的糧食筒倉工藝流程選擇算法[3-4]。

3 算法設計與實現

3.1 預處理

①根據糧食筒倉進出倉工藝流程，梳理設備的上下游邏輯關系。②按照工藝流程的類型可以得到多個樹結構，這里以其中一個樹結構為例進行討論，見圖1。③需將圖1的樹結構轉化為標準的二叉樹結構，可方便的使用成熟的二叉樹理論及其遍歷算法來研究工藝流程中設備之間的上下游關系。顯然，二叉樹結點間的父子關系與工藝流程中設備的上下游關系高度一致。見圖2（將A結點進行處理，V結點為新增的虛擬結點）。④從根結點到任意一個葉子結點所經歷的所有結點形成的路徑即構成了一條工藝流程。

3.2 核心算法流程圖

以預處理后的二叉樹結構為研究對象進行后續討論。考慮到算法的通用性，我們選取任意兩個結點，B和H（見圖3）進行B到H結點路徑算法的實現。算法的核心是分別從B和H結點出發，依次找尋B結點和H結點的祖先結點，由此分別得到A-B和A-B-E-H兩條路徑，進而得到從B結點出發到H結點的路徑為B-E-H。

3.3 算法實現

本文采用java語言，實現了單個二叉樹任意兩個結點之間的路徑。核心的算法程序如下。

3.3.1 結點實體類實現

public class Node {

String data;

Node parentNode;

Node leftNode;

Node rightNode;

public String getData（） {

return data;

}

Node（String v） {

data = v;

parentNode = null;

leftNode = null;

rightNode = null;

}

//省略類的get和set方法

}

3.3.2 任意兩個結點路徑函數實現

public static void printLeavesPath（Node leaf1， Node leaf2） {

String leaf1Data = leaf1.getData（）;

String leaf2Data = leaf2.getData（）;

Dequeleaf1Path=new LinkedList（）;

Dequeleaf2Path=new LinkedList（）;

while （true） {

leaf1Path.offerFirst（leaf1.getData（））;

leaf1 = leaf1.getParentNode（）;

if （leaf1 == null） {

break;

}

}

while （true） {

leaf2Path.offerFirst（leaf2.getData（））;

leaf2 = leaf2.getParentNode（）;

if （leaf2 == null） {

break;

}

}

String temp = “”;

// 比較兩個葉子結點的路徑。從根結點開始往下查找，若發現結點不同，則說明兩條路徑從此結點分叉。

while （leaf1Path.peekFirst（） == leaf2Path.peekFirst（）） {

temp = leaf1Path.pollFirst（）;

leaf2Path.pollFirst（）;

}

Iterator leaf1Iter = leaf1Path.iterator（）;

Iterator leaf2Iter = leaf2Path.descendingIterator（）;

StringBuffer result = new StringBuffer（）;

while （leaf2Iter.hasNext（）） {

result.append（leaf2Iter.next（） + seperator）;

}

StringBuffer result = new StringBuffer（）;

result.append（temp + seperator）;

while （leaf1Iter.hasNext（）） {

result.append（leaf1Iter.next（） + seperator）;

}

}

4 結語

顯然，想要得到根結點和葉子結點之間的路徑只是上述算法的特例。通過選擇根結點和葉子結點，即可確定從根結點到該葉子結點所需遍歷的所有結點，由這些結點可獲得從根結點到該葉子結點的路徑。恢復根結點和葉子結點的原始含義，可得到工藝流程與路徑的一一對應關系。綜上所述，可用二叉樹任意兩結點的路徑算法來處理糧食筒倉控制系統工藝流程的選擇。

與傳統的流程矩陣選擇算法相比，該算法具有以下優點：①兩個結點即可確定一條工藝流程，減少了結點數量的選擇。②通過增加葉子結點的不同權重，可篩選出滿足不同權重的工藝流程，對企業的節能有一定的參考價值。③可尋找任意兩個結點之間的路徑，對流程控制更有意義。在使用該算法時，需注意對設備的上下游關系進行人為的拆分，增加虛擬設備，進而得到標準的二叉樹結構。

應用上述算法，對某港務有限公司控制系統二期續建工程進行實際應用，成功的完成了對一期控制系統的升級和融合。通過選擇首尾設備或者倉，即可完成一條流程的選擇，簡單快捷、效果良好。

參考文獻：

[1]孫宏偉.ControlLogix在大型順序控制系統中的應用[J].電氣時代，2004（5）：74-76.

[2]季英業，李 威，陳智偉，等.糧食中轉碼頭作業流程節能技術研究[J].中國水運（下半月），2013，13（8）：54-55.

[3]霍羅維茲 著，朱仲濤 譯.數據結構基礎：（C語言版）（第2版）[M].北京：清華大學出版社，2009.

[4]葛一鳴.Java程序性能優化[M].北京：清華大學出版社，2012.