-
摘要: 粗糙集的核属性求解问题在经典计算中是一个NP问题.现有的方法中最优的时间复杂度也需要${\rm O}$$ \left(|C||U|\right)$($U$为论域、$C$为属性列数).由于量子计算的并行性特点, 本文致力于采用量子计算的方法来求解粗糙集的核属性, 拟提出了一种基于量子计算的粗糙集核属性求解算法.经过仿真实验, 在任何情况下, 该算法都能以1的总概率得到目标分量; 且通过理论分析证明了算法的时间复杂度不会高于${\rm O}$$\left(|\frac{{\rm{ \mathsf{ π}}}}{2\arcsin\sqrt {\frac{M}{C}}}+1||U|\right)$.Abstract: The computation of core in rough set is an NP-hard problem in classic computing. The best time complexity of the existing algorithms is ${\rm O}$$\left(|C||U|\right)$ ($U$ stands for Universe, $C$ stands for the number of attributes). Due to its ability to compute in parallel, quantum computing, is adopted to find the core in rough set in this research. Thus, a quantum algorithm of the computation of core in rough set is proposed. Based on simulation experiment, the proposed algorithm is able to get one target out of the target set with the probability of 1. And the time complexity of the new algorithm is proved to be no more than ${\rm O}$$ \left(|\frac{{\rm{ \mathsf{ π}}}}{2\arcsin\sqrt {\frac{M}{C}}}+1||U|\right)$ by theoretical analysis.
-
Key words:
- Quantum computing /
- rough set /
- core /
- algorithm design
1) 本文责任编委 张敏灵 -
表 1 UCI数据集实验结果
Table 1 The test result of UCI sets
数据集 算法 迭代次数 概率 Iris数据集 Grover算法 失效 失效 Iris数据集 文献[15]算法 2 0.9686 Iris数据集 文献[16]算法 1 1.0000 Iris数据集 $\textbf{本文算法}$ $\textbf{1}$ $\textbf{1.0000}$ Soybean数据集 Grover算法 1 0.8815 Soybean数据集 文献[15]算法 3 0.9723 Soybean数据集 文献[16]算法 2 0.9766 Soybean数据集 $\textbf{本文算法}$ $\textbf{2}$ $\textbf{1.0000}$ Dermatology数据集 Grover算法 6 0.9983 Dermatology数据集 文献[15]算法 12 1.0000 Dermatology数据集 文献[16]算法 8 0.9978 Dermatology数据集 $\textbf{本文算法}$ $\textbf{6}$ $\textbf{1.0000}$ Balloons数据集 Grover算法 失效 失效 Balloons数据集 文献[15]算法 2 0.9686 Balloons数据集 文献[16]算法 1 1.0000 Balloons数据集 $\textbf{本文算法}$ $\textbf{1}$ $\textbf{1.0000}$ Breast Cancer数据集 Grover算法 1 1.0000 Breast Cancer数据集 文献[15]算法 3 0.9688 Breast Cancer数据集 文献[16]算法 2 0.9451 Breast Cancer数据集 $\textbf{本文算法}$ $\textbf{1}$ $\textbf{1.0000}$ -
[1] Pawlak Z. Rough sets. International Journal of Computer & Information Sciences, 1982, 11(5): 341-356 [2] 黎明, 张化光.基于粗糙集的神经网络建模方法研究.自动化学报, 2002, 28(1): 27-33 http://www.aas.net.cn/article/id/16371Li Ming, Zhang Hua-Guang. Research on the method of neural network modeling based on rough sets theory. Acta Automatica Sinica, 2002, 28(1): 27-33 http://www.aas.net.cn/article/id/16371 [3] 张迎春, 郭禾.基于粗糙集和新能量公式的水平集图像分割.自动化学报, 2015, 41(11): 1913-1925 doi: 10.16383/j.aas.2015.c140823Zhang Ying-Chun, Guo He. Level set image segmentation based on rough set and new energy formula. Acta Automatica Sinica, 2015, 41(11): 1913-1925 doi: 10.16383/j.aas.2015.c140823 [4] Hu X H, Cercone N. Learning in relational databases: A rough set approach. Computational Intelligence, 1995, 11(2): 323-338 doi: 10.1111/j.1467-8640.1995.tb00035.x [5] 叶东毅, 陈昭炯.一个新的差别矩阵及其求核方法.电子学报, 2002, 30(7): 1086-1088 doi: 10.3321/j.issn:0372-2112.2002.07.040Ye Dong-Yi, Chen Zhao-Jiong. A new discernibility matrix and the computation of a core. Acta Electronica Sinica, 2002, 30(7): 1086-1088 doi: 10.3321/j.issn:0372-2112.2002.07.040 [6] 王国胤.决策表核属性的计算方法.计算机学报, 2003, 26(5): 611-615 doi: 10.3321/j.issn:0254-4164.2003.05.013Wang Guo-Yin. Calculation methods for core attributes of decision table. Chinese Journal of Computers, 2003, 26(5): 611-615 doi: 10.3321/j.issn:0254-4164.2003.05.013 [7] 徐章艳, 杨炳儒, 蔡卫东, 崔巍, 谷冬元.一个基于正区域的快速求核算法.系统工程与电子技术, 2006, 28(12): 1902-1905, 1931 doi: 10.3321/j.issn:1001-506X.2006.12.032Xu Zhang-Yan, Yang Bing-Ru, Cai Wei-Dong, Cui Wei, Gu Dong-Yuan. Quick algorithm for computing core based on the positive region. Systems Engineering and Electronics, 2006, 28(12): 1902-1905, 1931 doi: 10.3321/j.issn:1001-506X.2006.12.032 [8] 周江卫, 冯博琴, 刘洋.一种新的快速求核算法.西安交通大学学报, 2007, 41(6): 688-691 doi: 10.3321/j.issn:0253-987X.2007.06.013Zhou Jiang-Wei, Feng Bo-Qin, Liu Yang. New algorithm for quick computing core. Journal of Xi'an Jiaotong University, 2007, 41(6): 688-691 doi: 10.3321/j.issn:0253-987X.2007.06.013 [9] 尹林子, 阳春华, 王晓丽, 桂卫华.基于标记可辨识矩阵的增量式属性约简算法.自动化学报, 2014, 40(3): 397-404 doi: 10.3724/SP.J.1004.2014.00397Yin Lin-Zi, Yang Chun-Hua, Wang Xiao-Li, Gui Wei-Hua. An incremental algorithm for attribute reduction based on labeled discernibility matrix. Acta Automatica Sinica, 2014, 40(3): 397-404 doi: 10.3724/SP.J.1004.2014.00397 [10] 张靖, 李春文, 吴热冰.开放环境下多比特量子计算机的相干控制模型.自动化学报, 2005, 31(5): 759-764 http://www.aas.net.cn/article/id/15967Zhang Jing, Li Chun-Wen, Wu Re-Bing. Coherent control modeling of quantum computers in open environments. Acta Automatica Sinica, 2005, 31(5): 759-764 http://www.aas.net.cn/article/id/15967 [11] Deutsch D. Quantum theory, the church-turing principle and the universal quantum computer. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 1985, 400(1818): 97-117 [12] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997, 26(5): 1484-1509 doi: 10.1137/S0097539795293172 [13] Grover L. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. New York, USA: IEEE, 1996. 212-219 [14] 孙国栋, 苏胜辉, 徐茂智.求根问题的量子计算算法.北京工业大学学报, 2015, 41(3): 366-371 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=bjgydxxb201503007Sun Guo-Dong, Su Sheng-Hui, Xu Mao-Zhi. Quantum mechanical algorithms for solving root finding problem. Journal of Beijing University of Technology, 2015, 41(3): 366-371 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=bjgydxxb201503007 [15] Tulsi T, Grover L K, Patel A. A new algorithm for fixed point quantum search. Quantum Information & Computation, 2006, 6(6): 483-494 http://www.researchgate.net/publication/2195367_A_new_algorithm_for_fixed_point_quantum_search [16] 张煜东, 韦耿, 吴乐南.一种改进的Grover量子搜索算法.信号处理, 2009, 25(2): 256-259 doi: 10.3969/j.issn.1003-0530.2009.02.017Zhang Yu-Dong, Wei Geng, Wu Le-Nan. An improved Grover quantum searching algorithm. Signal Processing, 2009, 25(2): 256-259 doi: 10.3969/j.issn.1003-0530.2009.02.017 [17] 李盼池, 李士勇.基于自适应相位旋转的Grover量子搜索算法.系统仿真学报, 2009, 21(12): 3557-3560 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtfzxb200912014Li Pan-Chi, Li Shi-Yong. Grover$'$s quantum search algorithm based on adaptive phase rotation. Journal of System Simulation, 2009, 21(12): 3557-3560 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtfzxb200912014 [18] 朱皖宁, 陈汉武.迭代次数自适应的Grover算法.电子学报, 2016, 44(12): 2975-2980 doi: 10.3969/j.issn.0372-2112.2016.12.023Zhu Wan-Ning, Chen Han-Wu. Grover auto-control searching algorithm. Acta Electronica Sinica, 2016, 44(12): 2975-2980 doi: 10.3969/j.issn.0372-2112.2016.12.023 [19] Brassard C H, Hoyer P, Tapp A. Quantum counting. In: Proceedings of the 25th International Colloquium Automata Language and Programming. Berlin, Germany: Springer-Verlag, 1998. 820-831