黃銘銘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 零件展開算法

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

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

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

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

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

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

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

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

圖9 整車展開成零件

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

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

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

6 結(jié)束語

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

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

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

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

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

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

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

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

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