工艺数据管理系统算法研究

2012-09-15黄铭铭

湖北工业大学学报 2012年4期

黄铭铭

（湖北工业大学计算机学院，湖北武汉430068）

工艺数据管理系统中广泛采用了树形结构和树形的遍历算法，其目的是为了描述整车与零件、零件与零件之间的关系，并对某个层级上的对象进行展开或回归.本文对于系统中用到的零件展开与回归算法、LCDV与ECDV的匹配算法和整车展开到所有的零件算法结合树形算法进行了分析和设计.

1 工艺数据管理系统中树形结构的应用

在工艺数据管理系统中，以物料清单BOM（Bill of Material）为例，它表达了产品的配置关系，即一个产品包含了零部件的种类和数量以及它们之间的装配关系，它是联系销售系统、采购系统、制造系统、库存系统和财务系统的信息纽带.在工艺数据管理系统中零件与零件之间的关系通常被描述成图1所示结构，不难看出，物料清单是一个树形的结构.在实际BOM运算中需对某个零件进行展开或回归，要用到树型的遍历.

图1 物料结构

关于树形的遍历算法，目前业内已有许多研究，但在工艺数据管理系统的应用中，对于不同的业务需求，需要结合实际情况，有针对性地做出具体的分析和优化.

2 树的遍历算法模型优化

对普通树的遍历，可分为深度优先、宽度优先两种遍历方式，深度优先又可以分为先序和后序两种；对于二叉树，相较于普通的树形还会多出一种中序遍历的方式［1］［2］.

表面上，树的遍历是一种递归算法，计算流程见图2（以先序遍历为例）.

图2 通树的先序遍历流程图

然而，在实际的系统应用中，程序经常会因为递归次数过多而造成栈溢出，导致异常终止.这是因为，在递归调用的过程当中，系统为每一层的返回点、局部量等都会开辟相应的栈来存储，对内存具有较大的消耗，当遍历的层次过深时，就会造成栈溢出［3］，在处理海量的工艺数据时无法满足性能指标.

因此，需要改进这一算法，通过某种方式取代系统的栈，将递归算法变成非递归算法，以此来解决性能的瓶颈.

笔者设计出了不使用栈的非递归遍历算法，将栈对于算法性能的影响从算法中完全剥离，将由存储方式造成的性能影响降到最低.主要的思路是通过在每个节点都保存它的父节点指针的方式，形成一个“不使用栈的非递归遍历算法”，算法流程见图3.

此方法解决了递归算法存在的栈的性能瓶颈，排除了栈溢出的问题，形成了系统中相关算法的基础模型，基于上面的结论，即可具体分析和设计零件展开与回归算法、LCDV与ECDV的匹配算法.

图3 不使用栈的普通树的非递归遍历流程图

3 零件展开与回归算法的设计

由零件多级展开的基本算法（图4）得出最终的多级展开结果［4］.图5是零件多级展开的处理流程.

图4 零件展开算法

特别说明：零件展开中假设零件的最大深度为50层，所以定义一个SIZE为50的数组，用来保存深度遍历的层次零件号，以便当返回到上一层时能查询其兄弟零件信息与零件多级展开相反，零件回归的基本算法是将从“链表”中读取和检查条件由“父零件代码”转变成“子零件代码”，而“子零件代码”转变成“父零件代码”.树的遍历算法中我们建议采用深度优先算法，即先对子节点的下层进行展开，再展开节点兄弟的所有子节点［5］.零件回归处理流程见图6.

上面的展开和回归都是采用深度算法实现，这种方式适合于在线查看零件展开信息，但对于车型零件汇总，建议采用宽度优先的方式做展开，这样的展开效率要高一些.

4 LCDV与ECDV的匹配算法设计

LCDV是一种整车定义公共语言，由构成整车的所有“标志”建立的编码体系构成LCDV的“标志字典”，编码表达式按15个基础标志，随后是个性标志、描述标志、管理标志和技术标志的顺序排列的.标志是对一辆汽车的一个或一组主要特性的一般表述，由5位字符组成的编码.

ECDV是整车定义通用元素，ECDV是一种由标志和逻辑操作符（与、或、非）组成的一种逻辑表达式，它定义了所有可生产车型集合中的一个子集，是LCDV中5位字符编码的简化版.如：UW.1DN2（DL4）FN10＊，表示装备有与 ABS液压单元合装的比例阀的非加长型ZX车.

LCDV与ECDV的匹配算法中，可采用建立LCDV与ECDV匹配数组或表，其中主要内容有：LCDV标志码、ECDV标志码［6］.其流程见图7.

5 整车展开到所有的零件算法的设计

在整车零件展开应用中，通常输入24位的车型码，将接收的24位的车型码转交到BCV系统进行换算，将换算得到的LCDV码通过LCDV与ECDV的匹配算法取得对应ECDV锚，根据ECDV锚读取零件－ECDV链表，依次对ECDV进行树形展开，按照前述树形展开算法，对车型零件进行展开.最后把展开结果进行分类、汇总，形成报表（图9）.