回溯法在建立測(cè)量標(biāo)準(zhǔn)核查控制極限中的應(yīng)用

張麗梅，張立利

(91388部隊(duì)96分隊(duì)，廣東 湛江 524022)

測(cè)量過(guò)程控制是通過(guò)監(jiān)視和分析測(cè)量過(guò)程中獲得的數(shù)據(jù)，采取必要的糾正措施，使測(cè)量過(guò)程的不確定度連續(xù)保持在規(guī)定的技術(shù)要求之內(nèi)[1]，測(cè)量過(guò)程控制通常采用測(cè)量標(biāo)準(zhǔn)的核查來(lái)實(shí)現(xiàn).按隨機(jī)選擇的時(shí)間對(duì)核查標(biāo)準(zhǔn)進(jìn)行測(cè)量，期間會(huì)產(chǎn)生大量的核查數(shù)據(jù)，若核查數(shù)據(jù)在設(shè)定好的控制極限內(nèi)，表明測(cè)量過(guò)程處于統(tǒng)計(jì)控制狀態(tài)，否則表明測(cè)量過(guò)程失控，必須采取糾正措施直至受控.因此，測(cè)量標(biāo)準(zhǔn)的核查應(yīng)在選取合適的核查標(biāo)準(zhǔn)基礎(chǔ)上建立核查控制極限，通過(guò)控制極限來(lái)判斷核查的結(jié)果.在建立核查控制極限的過(guò)程中可以利用回溯法完成數(shù)據(jù)篩選.

1 建立核查控制極限

標(biāo)準(zhǔn)核查通常采用控制圖法[2]，因此建立核查控制極限也就是建立控制圖的控制極限.確定控制圖的控制極限是通過(guò)建立數(shù)學(xué)模型，采用統(tǒng)計(jì)分析方法完成.有3種常用的控制圖：標(biāo)準(zhǔn)偏差控制圖、極差控制圖、平均值控制圖.通常情況下，平均值控制圖和標(biāo)準(zhǔn)偏差控制圖或極差控制圖同時(shí)使用.

確定控制極限的過(guò)程是一個(gè)繁瑣的測(cè)量和計(jì)算過(guò)程，在確定過(guò)程參數(shù)的基礎(chǔ)上，預(yù)先對(duì)選定的核查標(biāo)準(zhǔn)進(jìn)行m組(m≥20)重復(fù)測(cè)量，組內(nèi)觀測(cè)次數(shù)j(j≥2)，以充分暴露測(cè)量過(guò)程中的各種影響量的變化.當(dāng)每次核查觀測(cè)次數(shù)較少時(shí)，如j為3～5次時(shí)應(yīng)采用極差控制圖，否則應(yīng)采用標(biāo)準(zhǔn)偏差控制圖.由每組觀測(cè)值可得到算術(shù)平均值、極差或標(biāo)準(zhǔn)偏差.從m組數(shù)據(jù)中抽取n組數(shù)據(jù)(m≥n，一般n為8～12)，計(jì)算各組的平均得到，計(jì)算各組的極差平均得到，或計(jì)算各組的標(biāo)準(zhǔn)偏差均方合成后得到合并標(biāo)準(zhǔn)偏差，當(dāng)組內(nèi)測(cè)量次數(shù)j相同時(shí)，則

(1)

根據(jù)國(guó)際標(biāo)準(zhǔn)ISO8258“舒沃特控制圖”規(guī)定的控制極限系數(shù)計(jì)算得出控制圖的控制極限.表1為控制圖的控制極限，其中的系數(shù)A2，A3，D3，D4或B3、B4可查計(jì)算控制極限系數(shù)表得到，如當(dāng)j=5時(shí)采用極差控制圖，A2=0.577，D3=0，D4=2.114；當(dāng)j=12時(shí)采用標(biāo)準(zhǔn)偏差控制圖，A3=0.886，B3=0.354，B4=1.646.[3]

表1 控制圖的控制極限

由抽取的n組數(shù)據(jù)計(jì)算得到控制極限，檢查此n組數(shù)據(jù)的平均值、極差或標(biāo)準(zhǔn)偏差是否均在控制極限內(nèi)，若在則表明抽取的n組數(shù)據(jù)受控，建立了有效的控制極限，否則需要另外抽取n組數(shù)據(jù)重新確定控制極限.要解決從m組數(shù)據(jù)中篩選n組受控?cái)?shù)據(jù)的問題，對(duì)指定的m，n編程可以采用循環(huán)嵌套的方法，但是程序異常繁瑣，當(dāng)m，n不確定時(shí)，使用回溯法可以較好地解決核查數(shù)據(jù)篩選問題.

2 回溯法

2.1 回溯法的概念

回溯法(探索與回溯法)是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)，但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”[4-5].

2.2 回溯法解題的基本步驟[6]

2.2.1 初始定義

利用回溯法解決問題時(shí)，要完成以下3步定義：

1)定義一個(gè)解空間用以描述解的形式，其包含問題的所有或部分解；

2)根據(jù)問題構(gòu)造狀態(tài)空間樹；

3)構(gòu)造約束函數(shù)，用于殺死節(jié)點(diǎn).

2.2.2 回溯步驟

完成初始定義后利用深度優(yōu)先搜索思想進(jìn)行回溯，具體步驟如圖1所示.

圖1 回溯法流程Fig.1 Flow chart of backtracking method

3 建立控制極限的過(guò)程

3.1 描述問題

從m組數(shù)據(jù)中篩選n組受控?cái)?shù)據(jù)，其中組內(nèi)觀測(cè)次數(shù)j,且m≥n>1.確定控制極限只需找到n組受控?cái)?shù)據(jù)，即只求問題的一個(gè)解.

3.2 初始定義

3.2.1 定義解空間及狀態(tài)空間樹

用0,1,2，…，m表示數(shù)據(jù)組號(hào)，采用回溯法找問題的解，將找到的組號(hào)按照從小到大的順序存于數(shù)組a[0]，a[1]，…，a[n-1]中，其中元素滿足以下性質(zhì)：

1)后一個(gè)數(shù)字比前一個(gè)大，即a[i+1]>a[i]；

2)a[i]-i<=m-(n-1).

數(shù)組a是從m中取n的一個(gè)解，是狀態(tài)空間樹的一個(gè)節(jié)點(diǎn).

3.2.2 定義約束函數(shù)

約束函數(shù)用于判斷核查極限是否有效，由數(shù)組a對(duì)應(yīng)的n組數(shù)據(jù)計(jì)算得到控制極限x上限，x下限，R上限，R下限或者S上限，S下限，約束函數(shù)為

(2)

3.3 回溯流程

圖2為利用回溯法建立核查控制極限的流程圖.其中的判斷框“驗(yàn)證選中組合數(shù)據(jù)全部受控嗎?”是代入約束函數(shù)計(jì)算，若驗(yàn)證該組合中的數(shù)據(jù)滿足約束函數(shù)，即數(shù)據(jù)受控，則該節(jié)點(diǎn)a為活節(jié)點(diǎn)，利用該解計(jì)算出的控制極限有效，否則a為死結(jié)點(diǎn).若求出活節(jié)點(diǎn)則求解完畢，否則回溯直至a[0]，若回溯到底表明無(wú)解，即所有的測(cè)量數(shù)據(jù)均不受控，應(yīng)采取糾正措施并重新對(duì)核查標(biāo)準(zhǔn)進(jìn)行測(cè)量.

定義參數(shù)：m—觀測(cè)組數(shù)；j—組內(nèi)觀測(cè)次數(shù)；n—受控?cái)?shù)據(jù)組數(shù)(計(jì)算控制極限必須的)；hcData[m,j]—測(cè)量數(shù)據(jù)數(shù)組.返回值：success—結(jié)果標(biāo)志，返回true表示成功，返回false表示失敗；a—存放有效數(shù)據(jù)的組號(hào)數(shù)組.圖2 建立控制極限的回溯流程Fig.2 Backtracking flow chart of the control limit

3.4 應(yīng)用實(shí)例

以建立多功能校準(zhǔn)源標(biāo)準(zhǔn)裝置的直流電壓參數(shù)核查控制極限為例，分析回溯法在建立測(cè)量標(biāo)準(zhǔn)核查控制中的實(shí)際應(yīng)用.選擇直流電壓10 V作為核查點(diǎn)，多功能校準(zhǔn)源5 700 A在一段時(shí)間內(nèi)對(duì)選定的核查標(biāo)準(zhǔn)344 01 A進(jìn)行20組重復(fù)測(cè)量，每組觀測(cè)次數(shù)5次，測(cè)量數(shù)據(jù)如表2所示.將測(cè)量數(shù)據(jù)存入觀測(cè)值數(shù)組hcData[m,j]中，代入回溯函數(shù)success，其中m=20，n=8，j=5，從20組數(shù)據(jù)中抽取合格的8組數(shù)據(jù)計(jì)算直流電壓參數(shù)的核查控制極限.

表2 控制極限的測(cè)量數(shù)據(jù)

4 結(jié)論

通過(guò)經(jīng)常性核查能使測(cè)量過(guò)程處于長(zhǎng)期連續(xù)的質(zhì)量控制之中，是計(jì)量確認(rèn)的補(bǔ)充.利用回溯法建立核查控制極限，可避免因操作人員計(jì)算不準(zhǔn)確等原因造成的錯(cuò)誤及由此而產(chǎn)生的錯(cuò)誤受控判定，而且大大地減少了工作量，有效保證了標(biāo)準(zhǔn)核查工作地順利開展.

參 考 文 獻(xiàn):

[1] 國(guó)防科工委科技與質(zhì)量司.計(jì)量基礎(chǔ)知識(shí)[M].北京：原子能出版社,2002:338.

[2] 施昌彥,虞惠霞.測(cè)量?jī)x器和計(jì)量標(biāo)準(zhǔn)的期間核查[J].中國(guó)計(jì)量,2008(09):40-42.

[3] 任中平,陶學(xué)軍.期間核查與舒沃特控制圖[J].計(jì)量技術(shù),2005(04):47-50.

[4] SHAFFER C A.數(shù)據(jù)結(jié)構(gòu)與算法分析[M].張銘，劉曉丹，譯.北京：電子工業(yè)出版社，1998.

[5] 盧開澄.計(jì)算機(jī)算法導(dǎo)引[M].清華大學(xué)出版社,2000:25-29.

[6] 林巧.利用回溯法求解若干問題的探討[J].計(jì)算機(jī)時(shí)代,2002(08):39-40.