基于量子衍生算法的8-puzzle问题分析

J4 ›› 2015, Vol. 32 ›› Issue (4): 459-465.

基于量子衍生算法的8-puzzle问题分析

许精明,阮越

1 安徽工业大学计算机科学与技术学院, 安徽马鞍山 243002;
2.东南大学计算科学与工程学院, 江苏南京 210096

收稿日期:2014-08-18 修回日期:2015-01-16 出版日期:2015-07-28 发布日期:2015-08-04
通讯作者: 许精明(1963－)副教授,研究领域为量子计算和人工智能. E-mail:xujingming518@126.com.
基金资助:
国家自然科学基金(61003311); 安徽省自然科学基金(1308085QF113)

Analysis on Quantum-Inspired Computing and Algorithm for 8-puzzle

XU Jingming, RUAN Yue

1. School of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243002, China;
2. School of Computer Science and Engineering, Southeast University, Nanjing 210096, China

Received:2014-08-18 Revised:2015-01-16 Published:2015-07-28 Online:2015-08-04

摘要/Abstract

摘要：

阐述了量子编码形式的多样性,概述了8-puzzle启发式搜索问题的量子衍生算法与计算策略;通过设置扩展深度界限,运用量子计数器和酉变换操作进行8-puzzle问题的量子计算.讨论了量子衍生算法与经典算法的比较．对启发式智能搜索在量子计算机上的实现方式作了进一步的讨论．

关键词: 8-puzzle, 量子衍生算法, 启发函数, 智能搜索

Abstract:

Heuristic function in quantum-inspired computing for 8-puzzle was analyzed．The diversity of quantum coding was expounded．A quantum-inspired algorithm and computing strategies based on heuristic function was presented．Quantum counter and unitary transformation operation are used to complete quantum computing for 8-puzzle problem, and quantum counter is set to maximum extension depth value．It is discussed that quantum-inspired algorithm is compared with the classical algorithm．Finally, how to implement a quantum computer for the heuristic intelligent search is discussed further．

Key words: 8-puzzle, quantum-inspired algorithm, heuristic function, intelligent search

中图分类号:

O413.1

许精明阮越. 基于量子衍生算法的8-puzzle问题分析[J]. J4, 2015, 32(4): 459-465.

XU Jingming, RUAN Yue . Analysis on Quantum-Inspired Computing and Algorithm for 8-puzzle[J]. J4, 2015, 32(4): 459-465.

参考文献

[1] Luis Domingues Tome Jardim Tarrataca.The quantum production system[D]. Universidade de Lisboa, Instituto Superior Tecnico,2013.http://web.ist.utl.pt/ luis.tarrataca/. [2] Mao Andrew, Ariel D. Procaccia, Chen Yiling. Better human computation through principled voting[C]. Proceedings of the 27th AAAI Conference on Artificial Intelligence,2013, Bellevue, Washington, USA. [3] Kevin Igwe, Nelishia Pillay, Christopher Rae.Solving the 8-Puzzle Problem Using Genetic Programming[C]. SAICSIT '13, October 07 - 09 2013, East London, South Africa. [4]Cai Zixing, Xu Guangyou. Artificial intelligence: principles & applications[M](the fourth edition)(人工智能及其应用(第四版)). Beijing: Tsinghua University Press, 2010,73-75(in Chinese). [5] Xu Jingming. Choice of heuristic function and analysis of heuristic power in intelligent search[J].Journal of Kunming University of Science and Technology(Science and Technology),2007,32(5):31-34(in Chinese). 许精明.智能搜索中启发函数的选择及启发能力分析[J].昆明理工大学学报(理工版),2007,32(5):31-34. [6] He Guangping. Quantum information made easy[M](通俗量子信息学).Beijing: Science Press,2012,15-18(in Chinese). [7] (Japanese)Zuo Chuan Hongxing,Ji Tian Xuanzhang.Song Heshan,Song Tian translated.Quantum information theory[M](量子信息论). Dalian: Dalian University of Technology Press, 2007(in Chinese). [8](America) A.Michael Nielsen, L.Isaac.Chuang.Zhao Qianchuan translated.Quantum computation and quantum information[M](量子计算和量子信息(一)、(二)). Beijing: Tsinghua University Press,2004(in Chinese). [9]Li Shiyong,Li Panchi.Quantum computation and quantum optimization algorithms[M](量子计算与量子优化算法).Harbin: Harbin Institute of Technology Press, 2009(in Chinese). [10]Liang Changyong,Bai Hua,Cai Meiju,et al.Advances in quantum genetic algorithm[J].Application Research of Computers,2012,29(7):2401-2405(in Chinese). 梁昌勇,柏桦,蔡美菊等.量子遗传算法研究进展[J].计算机应用研究,2012,29(7):2401-2405. [11]Meng Xiangping, Pi Yuzhen, Zhao Liang.A novel artifical neural network training method based on quantum computational multi-agent[J].Computer Simulation,2011,28(11):161-184(in Chinese). 孟祥萍,皮玉珍,赵亮.基于量子计算多Agent的人工神经网络训练方法[J].计算机仿真, 2011,28(11):161-184. [12] K. Aoki, Y. Yamanashi, and N. Yoshikawa. Multiplexing Techniques of Single Flux Quantum Circuit Based Readout Circuit for a Multi-Channel Sensing System. IEEE Transactions on Applied Superconductivity, 2013,23(3). [13] Yang Shuyuan, Liu Fang, Jiao Licheng. Quantum evolutionary strategies[J].Acta Electronica Sinica,2001, 29(12A):1873-1877(in Chinese). 杨淑媛,刘芳,焦李成.量子进化策略[J].电子学报,2001, 29(12A):1873-1877. [14] Jeremy Hsu. Scientists Confirm D-Wave's Computer Chips Compute Using Quantum Mechanics[OL]. http://spectrum.ieee.org/tech-talk/computing/hardware/scientists-confirm-dwave-computer-chips-compute-using- quantum-mechanics. [15] Sandip Dey, Indrajit Saha and Ujjwal Maulik, Siddhartha Bhattacharyya. New Quantum Inspired Meta-heuristic Methods for Multi-level Thresholding. International Conference on Advances in Computing, Communications and Informatics(ICACCI), Myore,India,2013. [16]Tie Han and Pieter Jonker. On Quantum Computing with Macroscopic Josephson Qubits.Proceedings of the 2002 2nd IEEE Conference on Nanotechnology (Cat. No.02TH8630),305-308.