工藝數據管理系統算法研究

黃銘銘

（湖北工業大學計算機學院，湖北 武漢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）.

圖9 整車展開成零件

若需要統計車型零件數量信息（例如統計車型各工藝總工時信息時），則需要在零件展開過程中將零件鏈上每層的裝配系數累計相乘（圖10）.

圖10 零件結構圖

在上圖中，假設零件A為車型，則零件G在車型A上的總裝配數量是2×1×3＝6個，零件F的總裝配數量是2×2＝4個［7－8］.

6 結束語

算法在工藝數據管理系統中占核心地位，如何通過合理高效的算法來模擬現實的業務邏輯、解決業務上的問題，在系統開發中是至關重要的.工藝數據管理系統算法的研究是一個長期的過程，還有待繼續深入研究.

［1］賀方超.兩種算法穩定情形下交叉驗證推廣誤差的界［J］.湖北工業大學學報，2008，23（5）：69－72.

［2］李 平.數據結構［M］.北京：電子工業出版社，1986.

［3］畢廣吉.Java程序設計實例教程［M］.北京：冶金工業出版社，2007.

［4］缺作者.Herbert Schidt.Java參考大全［M］.鄢愛蘭，鹿江春譯.北京：清華大學出版社，2006.

［5］唐煥文，賀明峰.數學模型引論［M］.第二版.北京：高等教育出版社，2002.

［6］蔡鎖章.數學建模原理與方法［M］.北京：海洋出版社，2000.

［7］謝云蓀，張志讓.數學實驗［M］北京：科學出版社，2000.

［8］王惠文.偏最小二乘回歸方法及其應用［M］.北京：國防工業出版社，2000.