A parallel algorithm for solving the n-queens problem based on inspired computational model

被引：16

作者：

Wang, Zhaocai ^{[1
]}

Huang, Dongmei ^{[1
]}

Tan, Jian ^{[2
]}

Liu, Taigang ^{[1
]}

Zhao, Kai ^{[3
]}

Li, Lei ^{[4
]}

机构：

[1] Shanghai Ocean Univ, Coll Informat, Shanghai 201306, Peoples R China

[2] Chinese Acad Sci, Ctr Earth Observat & Digital Earth, China Key Lab Digital Earth, Beijing 100094, Peoples R China

[3] Pingdingshan Univ, Acad Affair Off, Pingdingshan 467000, Peoples R China

[4] Xian Univ Architecture & Technol, Dept Civil Engn, Xian 710055, Peoples R China

来源：

BIOSYSTEMS | 2015年 / 131卷

基金：

中国国家自然科学基金; 国家高技术研究发展计划(863计划);

关键词：

DNA computation; The n-queens problem; Adleman-Lipton model; NP-complete problem; MOLECULAR COMPUTATION; DNA SOLUTION; NETWORK;

D O I：

10.1016/j.biosystems.2015.03.004

中图分类号：

Q [生物科学];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

DNA computing provides a promising method to solve the computationally intractable problems. The n-queens problem is a well-known NP-hard problem, which arranges n queens on an n x n board in different rows, columns and diagonals in order to avoid queens attack each other. In this paper, we present a novel parallel DNA algorithm for solving the n-queens problem using DNA molecular operations based on a biologically inspired computational model. For the n-queens problem, we reasonably design flexible length DNA strands representing elements of the allocation matrix, take appropriate biologic manipulations and get the solutions of the n-queens problem in proper length and O(n(2)) time complexity. We extend the application of DNA molecular operations, simultaneity simplify the complexity of the computation and simulate to verify the feasibility of the DNA algorithm. (C) 2015 Elsevier Ireland Ltd. All rights reserved.

引用

页码：22 / 29

页数：8

共 50 条

[31] New Constructions for the n-Queens Problem
Baca, M.
Lopez, S. C.
Muntaner-Batle, F. A.
Semanicova-Fenovcikova, A.
RESULTS IN MATHEMATICS, 2020, 75 (01)
[32] N-Queens Problem Resolution Using the Quantum Computing Model
de Souza, F. J.
de Mello, F. L.
IEEE LATIN AMERICA TRANSACTIONS, 2017, 15 (03) : 534 - 540
[33] Regular solutions of the n-queens problem on the torus
Burger, AP
Mynhardt, CM
Cockayne, EJ
UTILITAS MATHEMATICA, 2004, 65 : 219 - 230
[34] Neural networks for the N-Queens Problem: a review
Mandziuk, J
CONTROL AND CYBERNETICS, 2002, 31 (02): : 217 - 248
[35] The N-queens Problem on a symmetric Toeplitz matrix
Szaniszlo, Zsuzsanna
Tomova, Maggy
Wyels, Cindy
DISCRETE MATHEMATICS, 2009, 309 (04) : 969 - 974
[36] A group-based search for solutions of the n-queens problem
Engelhardt, Matthias R.
DISCRETE MATHEMATICS, 2007, 307 (21) : 2535 - 2551
[37] THE MODULAR N-QUEENS PROBLEM IN HIGHER DIMENSIONS
NUDELMAN, SP
DISCRETE MATHEMATICS, 1995, 146 (1-3) : 159 - 167
[38] Reducing the time complexity of the n-queens problem
El-Qawasmeh, E
Al-Noubani, K
INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS, 2005, 14 (03) : 545 - 557
[39] A Solution to the N-Queens Problem Using Biogeography-Based Optimization
Habiboghli, Ali
Jalali, Tayebeh
INTERNATIONAL JOURNAL OF INTERACTIVE MULTIMEDIA AND ARTIFICIAL INTELLIGENCE, 2017, 4 (04): : 22 - 26
[40] A New Algorithm Using Hopfield Neural Network with CHN for N-Queens Problem
Zhang, Wei
Tang, Zheng
INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND NETWORK SECURITY, 2009, 9 (04): : 36 - 41

← 1 2 3 4 5 →