A Polynomial-Time DNA Computing Solution for the N-Queens Problem

被引：5

作者：

Maazallahi, Ramin ^{[1
]}

Niknafs, Aliakbar ^{[1
]}

Arabkhedri, Paria ^{[1
]}

机构：

[1] Shahid Bahonar Univ Kerman, Dept Comp Engn, Kerman, Iran

来源：

2ND WORLD CONFERENCE ON EDUCATIONAL TECHNOLOGY RESEARCH | 2013年 / 83卷

关键词：

DNA computing; Adleman-Lipton Model; N-queens problem; NP-Complete; ALGORITHMS;

D O I：

10.1016/j.sbspro.2013.06.118

中图分类号：

G40 [教育学];

学科分类号：

040101 ; 120403 ;

摘要：

The N-queens problem is a classic combinatorial problem that there is no polynomial time solution for it in silicon based computers. It belongs to the set of NP-Complete problems and needs a plenty of calculations. On the other hand, it has been evidenced that DNA computing is able to solve such complex problems efficiently. In this paper we propose a method based on Adleman-Lipton model, a model of DNA computing, which is able to solve the N-queens problem in a polynomial time complexity. It provides all the solutions and runs in O(N-2). (C) 2013 The Authors. Published by Elsevier Ltd.

引用

页码：622 / 628

页数：7

共 50 条

[21] Exhaustive Study of Essential Constraint Satisfaction Problem Techniques based on N-Queens Problem
Ayub, Md Ahsan
Kalpoma, Kazi A.
Proma, Humaira Tasnim
Kabir, Syed Mehrab
Chowdhury, Rakib Ibna Hamid
2017 20TH INTERNATIONAL CONFERENCE OF COMPUTER AND INFORMATION TECHNOLOGY (ICCIT), 2017,
[22] An Orbit-based Search Algorithm to Solve N-Queens Problem
Zhang, Jun
Zhang, Zili
MECHANICAL ENGINEERING AND INTELLIGENT SYSTEMS, PTS 1 AND 2, 2012, 195-196 : 1049 - +
[23] n-Rooks and n-queens problem on planar and modular chessboards with hexagonal cells
Taganap, Eduard C.
Almuete, Rainier D.
NOTES ON NUMBER THEORY AND DISCRETE MATHEMATICS, 2023, 29 (04) : 774 - 788
[24] Polynomial-Time Solvability of the Maximum Clique Problem
Tomita, Etsuji
Nakanishi, Hiroaki
COMPUTING AND COMPUTATIONAL INTELLIGENCE, PROCEEDINGS, 2009, : 203 - +
[25] Efficiency of parallel genetic algorithm for solving N-queens problem on multicomputer platform
Lazarova, Milena
ADVANCED TOPICS ON EVOLUTIONARY COMPUTING, 2008, : 51 - 56
[26] Accelerated execution of P systems with active membranes to solve the N-queens problem
Maroosi, Ali
Muniyandi, Ravie Chandren
THEORETICAL COMPUTER SCIENCE, 2014, 551 : 39 - 54
[27] A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem
Draa, Amer
Meshoul, Souham
Talbi, Hichem
Batouche, Mohamed
INTERNATIONAL ARAB JOURNAL OF INFORMATION TECHNOLOGY, 2010, 7 (01) : 21 - 27
[28] Solving the n-Queens Problem Using a Tuned Hybrid Imperialist Competitive Algorithm
Masehian, Ellips
Akbaripour, Hossein
Mohabbati-Kalejahi, Nasrin
INTERNATIONAL ARAB JOURNAL OF INFORMATION TECHNOLOGY, 2014, 11 (06) : 550 - 559
[29] LOCAL SEARCH WITH CONFLICT MINIMIZATION - A CASE-STUDY OF THE N-QUEENS PROBLEM
SOSIC, R
GU, J
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1994, 6 (05) : 661 - 668
[30] A parallel algorithm for solving the n-queens problem based on inspired computational model
Wang, Zhaocai
Huang, Dongmei
Tan, Jian
Liu, Taigang
Zhao, Kai
Li, Lei
BIOSYSTEMS, 2015, 131 : 22 - 29

← 1 2 3 4 5 →