回溯法在建立测量标准核查控制极限中的应用

张丽梅，张立利

(91388部队96分队，广东 湛江 524022)

测量过程控制是通过监视和分析测量过程中获得的数据，采取必要的纠正措施，使测量过程的不确定度连续保持在规定的技术要求之内[1]，测量过程控制通常采用测量标准的核查来实现.按随机选择的时间对核查标准进行测量，期间会产生大量的核查数据，若核查数据在设定好的控制极限内，表明测量过程处于统计控制状态，否则表明测量过程失控，必须采取纠正措施直至受控.因此，测量标准的核查应在选取合适的核查标准基础上建立核查控制极限，通过控制极限来判断核查的结果.在建立核查控制极限的过程中可以利用回溯法完成数据筛选.

1 建立核查控制极限

标准核查通常采用控制图法[2]，因此建立核查控制极限也就是建立控制图的控制极限.确定控制图的控制极限是通过建立数学模型，采用统计分析方法完成.有3种常用的控制图：标准偏差控制图、极差控制图、平均值控制图.通常情况下，平均值控制图和标准偏差控制图或极差控制图同时使用.

确定控制极限的过程是一个繁琐的测量和计算过程，在确定过程参数的基础上，预先对选定的核查标准进行m组(m≥20)重复测量，组内观测次数j(j≥2)，以充分暴露测量过程中的各种影响量的变化.当每次核查观测次数较少时，如j为3～5次时应采用极差控制图，否则应采用标准偏差控制图.由每组观测值可得到算术平均值、极差或标准偏差.从m组数据中抽取n组数据(m≥n，一般n为8～12)，计算各组的平均得到，计算各组的极差平均得到，或计算各组的标准偏差均方合成后得到合并标准偏差，当组内测量次数j相同时，则

(1)

根据国际标准ISO8258“舒沃特控制图”规定的控制极限系数计算得出控制图的控制极限.表1为控制图的控制极限，其中的系数A2，A3，D3，D4或B3、B4可查计算控制极限系数表得到，如当j=5时采用极差控制图，A2=0.577，D3=0，D4=2.114；当j=12时采用标准偏差控制图，A3=0.886，B3=0.354，B4=1.646.[3]

表1 控制图的控制极限

由抽取的n组数据计算得到控制极限，检查此n组数据的平均值、极差或标准偏差是否均在控制极限内，若在则表明抽取的n组数据受控，建立了有效的控制极限，否则需要另外抽取n组数据重新确定控制极限.要解决从m组数据中筛选n组受控数据的问题，对指定的m，n编程可以采用循环嵌套的方法，但是程序异常繁琐，当m，n不确定时，使用回溯法可以较好地解决核查数据筛选问题.

2 回溯法

2.1 回溯法的概念

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标，但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”[4-5].

2.2 回溯法解题的基本步骤[6]

2.2.1 初始定义

利用回溯法解决问题时，要完成以下3步定义：

1)定义一个解空间用以描述解的形式，其包含问题的所有或部分解；

2)根据问题构造状态空间树；

3)构造约束函数，用于杀死节点.

2.2.2 回溯步骤

完成初始定义后利用深度优先搜索思想进行回溯，具体步骤如图1所示.

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

3 建立控制极限的过程

3.1 描述问题

从m组数据中筛选n组受控数据，其中组内观测次数j,且m≥n>1.确定控制极限只需找到n组受控数据，即只求问题的一个解.

3.2 初始定义

3.2.1 定义解空间及状态空间树

用0,1,2，…，m表示数据组号，采用回溯法找问题的解，将找到的组号按照从小到大的顺序存于数组a[0]，a[1]，…，a[n-1]中，其中元素满足以下性质：

1)后一个数字比前一个大，即a[i+1]>a[i]；

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

数组a是从m中取n的一个解，是状态空间树的一个节点.

3.2.2 定义约束函数

约束函数用于判断核查极限是否有效，由数组a对应的n组数据计算得到控制极限x上限，x下限，R上限，R下限或者S上限，S下限，约束函数为

(2)

3.3 回溯流程

图2为利用回溯法建立核查控制极限的流程图.其中的判断框“验证选中组合数据全部受控吗?”是代入约束函数计算，若验证该组合中的数据满足约束函数，即数据受控，则该节点a为活节点，利用该解计算出的控制极限有效，否则a为死结点.若求出活节点则求解完毕，否则回溯直至a[0]，若回溯到底表明无解，即所有的测量数据均不受控，应采取纠正措施并重新对核查标准进行测量.

定义参数：m—观测组数；j—组内观测次数；n—受控数据组数(计算控制极限必须的)；hcData[m,j]—测量数据数组.返回值：success—结果标志，返回true表示成功，返回false表示失败；a—存放有效数据的组号数组.图2 建立控制极限的回溯流程Fig.2 Backtracking flow chart of the control limit

3.4 应用实例

以建立多功能校准源标准装置的直流电压参数核查控制极限为例，分析回溯法在建立测量标准核查控制中的实际应用.选择直流电压10 V作为核查点，多功能校准源5 700 A在一段时间内对选定的核查标准344 01 A进行20组重复测量，每组观测次数5次，测量数据如表2所示.将测量数据存入观测值数组hcData[m,j]中，代入回溯函数success，其中m=20，n=8，j=5，从20组数据中抽取合格的8组数据计算直流电压参数的核查控制极限.

表2 控制极限的测量数据

4 结论

通过经常性核查能使测量过程处于长期连续的质量控制之中，是计量确认的补充.利用回溯法建立核查控制极限，可避免因操作人员计算不准确等原因造成的错误及由此而产生的错误受控判定，而且大大地减少了工作量，有效保证了标准核查工作地顺利开展.

参 考 文 献:

[1] 国防科工委科技与质量司.计量基础知识[M].北京：原子能出版社,2002:338.

[2] 施昌彦,虞惠霞.测量仪器和计量标准的期间核查[J].中国计量,2008(09):40-42.

[3] 任中平,陶学军.期间核查与舒沃特控制图[J].计量技术,2005(04):47-50.

[4] SHAFFER C A.数据结构与算法分析[M].张铭，刘晓丹，译.北京：电子工业出版社，1998.

[5] 卢开澄.计算机算法导引[M].清华大学出版社,2000:25-29.

[6] 林巧.利用回溯法求解若干问题的探讨[J].计算机时代,2002(08):39-40.