工藝數(shù)據(jù)管理系統(tǒng)算法研究

黃銘銘

（湖北工業(yè)大學(xué)計算機(jī)學(xué)院，湖北 武漢430068）

工藝數(shù)據(jù)管理系統(tǒng)中廣泛采用了樹形結(jié)構(gòu)和樹形的遍歷算法，其目的是為了描述整車與零件、零件與零件之間的關(guān)系，并對某個層級上的對象進(jìn)行展開或回歸.本文對于系統(tǒng)中用到的零件展開與回歸算法、LCDV與ECDV的匹配算法和整車展開到所有的零件算法結(jié)合樹形算法進(jìn)行了分析和設(shè)計.

1 工藝數(shù)據(jù)管理系統(tǒng)中樹形結(jié)構(gòu)的應(yīng)用

在工藝數(shù)據(jù)管理系統(tǒng)中，以物料清單BOM（Bill of Material）為例，它表達(dá)了產(chǎn)品的配置關(guān)系，即一個產(chǎn)品包含了零部件的種類和數(shù)量以及它們之間的裝配關(guān)系，它是聯(lián)系銷售系統(tǒng)、采購系統(tǒng)、制造系統(tǒng)、庫存系統(tǒng) 和財務(wù)系統(tǒng)的信息紐帶.在工藝數(shù)據(jù)管理系統(tǒng)中零件與零件之間的關(guān)系通常被描述成圖1所示結(jié)構(gòu)，不難看出，物料清單是一個樹形的結(jié)構(gòu).在實際BOM運算中需對某個零件進(jìn)行展開或回歸，要用到樹型的遍歷.

圖1 物料結(jié)構(gòu)

關(guān)于樹形的遍歷算法，目前業(yè)內(nèi)已有許多研究，但在工藝數(shù)據(jù)管理系統(tǒng)的應(yīng)用中，對于不同的業(yè)務(wù)需求，需要結(jié)合實際情況，有針對性地做出具體的分析和優(yōu)化.

2 樹的遍歷算法模型優(yōu)化

對普通樹的遍歷，可分為深度優(yōu)先、寬度優(yōu)先兩種遍歷方式，深度優(yōu)先又可以分為先序和后序兩種；對于二叉樹，相較于普通的樹形還會多出一種中序遍歷的方式［1］［2］.

表面上，樹的遍歷是一種遞歸算法，計算流程見圖2（以先序遍歷為例）.

圖2 通樹的先序遍歷流程圖

然而，在實際的系統(tǒng)應(yīng)用中，程序經(jīng)常會因為遞歸次數(shù)過多而造成棧溢出，導(dǎo)致異常終止.這是因為，在遞歸調(diào)用的過程當(dāng)中，系統(tǒng)為每一層的返回點、局部量等都會開辟相應(yīng)的棧來存儲，對內(nèi)存具有較大的消耗，當(dāng)遍歷的層次過深時，就會造成棧溢出［3］，在處理海量的工藝數(shù)據(jù)時無法滿足性能指標(biāo).

因此，需要改進(jìn)這一算法，通過某種方式取代系統(tǒng)的棧，將遞歸算法變成非遞歸算法，以此來解決性能的瓶頸.

筆者設(shè)計出了不使用棧的非遞歸遍歷算法，將棧對于算法性能的影響從算法中完全剝離，將由存儲方式造成的性能影響降到最低.主要的思路是通過在每個節(jié)點都保存它的父節(jié)點指針的方式，形成一個“不使用棧的非遞歸遍歷算法”，算法流程見圖3.

此方法解決了遞歸算法存在的棧的性能瓶頸，排除了棧溢出的問題，形成了系統(tǒng)中相關(guān)算法的基礎(chǔ)模型，基于上面的結(jié)論，即可具體分析和設(shè)計零件展開與回歸算法、LCDV與ECDV的匹配算法.

圖3 不使用棧的普通樹的非遞歸遍歷流程圖

3 零件展開與回歸算法的設(shè)計

由零件多級展開的基本算法（圖4）得出最終的多級展開結(jié)果［4］.圖5是零件多級展開的處理流程.

圖4 零件展開算法

特別說明：零件展開中假設(shè)零件的最大深度為50層，所以定義一個SIZE為50的數(shù)組，用來保存深度遍歷的層次零件號，以便當(dāng)返回到上一層時能查詢其兄弟零件信息與零件多級展開相反，零件回歸的基本算法是將從“鏈表”中讀取和檢查條件由“父零件代碼”轉(zhuǎn)變成“子零件代碼”，而“子零件代碼”轉(zhuǎn)變成“父零件代碼”.樹的遍歷算法中我們建議采用深度優(yōu)先算法，即先對子節(jié)點的下層進(jìn)行展開，再展開節(jié)點兄弟的所有子節(jié)點［5］.零件回歸處理流程見圖6.

上面的展開和回歸都是采用深度算法實現(xiàn)，這種方式適合于在線查看零件展開信息，但對于車型零件匯總，建議采用寬度優(yōu)先的方式做展開，這樣的展開效率要高一些.

4 LCDV與ECDV的匹配算法設(shè)計

LCDV是一種整車定義公共語言，由構(gòu)成整車的所有“標(biāo)志”建立的編碼體系構(gòu)成LCDV的“標(biāo)志字典”，編碼表達(dá)式按15個基礎(chǔ)標(biāo)志，隨后是個性標(biāo)志、描述標(biāo)志、管理標(biāo)志和技術(shù)標(biāo)志的順序排列的.標(biāo)志是對一輛汽車的一個或一組主要特性的一般表述，由5位字符組成的編碼.

ECDV是整車定義通用元素，ECDV是一種由標(biāo)志和邏輯操作符（與、或、非）組成的一種邏輯表達(dá)式，它定義了所有可生產(chǎn)車型集合中的一個子集，是LCDV中5位字符編碼的簡化版.如：UW.1DN2（DL4）FN10＊，表示裝備有與 ABS液壓單元合裝的比例閥的非加長型ZX車.

LCDV與ECDV的匹配算法中，可采用建立LCDV與ECDV匹配數(shù)組或表，其中主要內(nèi)容有：LCDV標(biāo)志碼、ECDV標(biāo)志碼［6］.其流程見圖7.

5 整車展開到所有的零件算法的設(shè)計

在整車零件展開應(yīng)用中，通常輸入24位的車型碼，將接收的24位的車型碼轉(zhuǎn)交到BCV系統(tǒng)進(jìn)行換算，將換算得到的LCDV碼通過LCDV與ECDV的匹配算法取得對應(yīng)ECDV錨，根據(jù)ECDV錨讀取零件－ECDV鏈表，依次對ECDV進(jìn)行樹形展開，按照前述樹形展開算法，對車型零件進(jìn)行展開.最后把展開結(jié)果進(jìn)行分類、匯總，形成報表（圖9）.

圖9 整車展開成零件

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

圖10 零件結(jié)構(gòu)圖

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

6 結(jié)束語

算法在工藝數(shù)據(jù)管理系統(tǒng)中占核心地位，如何通過合理高效的算法來模擬現(xiàn)實的業(yè)務(wù)邏輯、解決業(yè)務(wù)上的問題，在系統(tǒng)開發(fā)中是至關(guān)重要的.工藝數(shù)據(jù)管理系統(tǒng)算法的研究是一個長期的過程，還有待繼續(xù)深入研究.

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

［2］李 平.數(shù)據(jù)結(jié)構(gòu)［M］.北京：電子工業(yè)出版社，1986.

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

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

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

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

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

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