基于二叉树的粮食筒仓工艺流程选择算法的实现及应用
2019-10-21魏鹏飞苏亚洲
魏鹏飞 苏亚洲
摘 要：随着控制系统规模的扩大，流程选择的复杂程度倍增，传统的流程矩阵选择算法已不能处理上述问题。本文基于计算机的成熟二叉树理论及其遍历算法，通过对筒仓工艺流程的设备上下游关系进行特殊处理，得到基于二叉树的粮食筒仓工艺流程选择算法。该算法为大规模的筒仓工艺流程选择提供了新的的思路。
关键词：流程矩阵;二叉树;遍历算法;流程选择
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（）;
Deque
Deque
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
Iterator
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.
