带有行限制的覆盖阵列的研究

An approach to testing the hardware or software efficiently is to use covering arrays (CAs) which are generated from combinatorial designs. This approach involves identifying parameters that define the space of possible test scenarios, then selecting test scenarios in such a way as to cover all the t–wise interactions between these parameters and their values. Since this method has lower costs and higher quality, it has attracted more and more interests. Covering arrays with row limit, CARLs, are a new family of combinatorial objects which are introduced as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. Although we have two upper bound of CARLs, we do not know if it is optimal, or if these bounds can be further strengthened..Our research is focus on the bound and the constructions of CARLs. Originally, Wilson’s construction is used for group diveisible designs. Its generalizations are applicable for construction of CARLs of any strength. There are probably other constructions, in particular constructions of t-designs, that can be generalized and used in the context of CARLs..The Deterministic Density Algorithm, DDA, is a polynomial time algorithm for the construction of covering arrays. However, it is based on ‘filling in one cell at a time’, a method which cannot be generalized due to the reason that we have a row limit.We have a greedy, possibly exponential time algorithm for construction of CARLs, which are also large in size. Another direction of further study is to find a polynomial time algorithm for construction of CARLs.

覆盖阵列CA可以对大型软硬件系统进行高质量和高效率的测试，用少量的测试次数，保证了对任意t个不同因素进行交叉测试。由于覆盖阵列的重要作用，引起大量学者对其进行研究。当有些测试受设备或其他一些客观因素制约时，要对每一次参加测试的类进行限制，这就需要一种特殊的覆盖阵列--带有行限制的覆盖阵列CARL。尽管已经得到CARL(N;t,k,v:w)的两个上界UB_0和UB_1，在已经得到的构造中，一些结果的阶数明显小于已知界，意味着上界仍有很大的改进空间。.本项目就带有行限制的覆盖阵列CARL的界及其构造两方面展开研究。由于CA可以看做是特殊参数的CARL，课题首先考虑推广覆盖阵列CA的组合构造方法，用来构造一些参数的CARL；由于CA构造中基于“一次填充一个元素”的算法不能应用于行有限制的情况，构造CARL的时间复杂度可能达到指数级，本课题拟寻找多项式时间算法的构造。

本项目对覆盖阵列, 尤其是有行限制的覆盖阵列, 光正交码, 差集, 控制集等几类问题进行了研究, 这些问题都是组合设计及图论界关注的应用性热点问题, 并取得了一定成果. .项目组重点研究了以下问题: (1) 研究了覆盖阵列的界和组合构造, 推广相关方法应用于带有行限制的覆盖阵列, 得到了一些新的结果. (2) 研究了光正交码的在线引导变异进化算法, 可以解决较大参数的光正交码的构造, 计算效率高. (3) 研究了分圆理论与部分差集, 强正则图的关系, 构造了新的部分差集, 并得到了分圆数的一个新性质. (4) 推广了PageRank算法, 基于矩阵变换和蒙特卡罗方法, 分别给出了在静态和动态带权网络中个性化PageRank算法, 并从理论上分析了算法的性能. (5) 用图的控制集理论分析社交网络, 通过改进的进化算法求解, 结构简单, 运行效率较高. (6) 研究了多通道卫星图像无损压缩方法, 得到2倍以上的平均压缩比, 比现有方法节省一半以上的存储空间..本项目目前为止已发表的期刊论文3篇(其中SCI二区1篇), 审稿中的论文1篇, 在整理中的论文1篇. 授权发明专利3项, 实用新型专利2项, 完成《离散数学》教材一本, 已于科学出版社出版..