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 条
  • [1] A polynomial-time DNA computing solution for the Bin-Packing Problem
    Alonso Sanches, Carlos Alberto
    Soma, Nei Yoshihiro
    APPLIED MATHEMATICS AND COMPUTATION, 2009, 215 (06) : 2055 - 2062
  • [2] A DYNAMIC-PROGRAMMING SOLUTION TO THE N-QUEENS PROBLEM
    RIVIN, I
    ZABIH, R
    INFORMATION PROCESSING LETTERS, 1992, 41 (05) : 253 - 256
  • [3] A Linear Time Pattern Based Algorithm for N-Queens Problem
    Karabulut, Bergen
    Erguzen, Atilla
    Unver, Halil Murat
    JOURNAL OF POLYTECHNIC-POLITEKNIK DERGISI, 2022, 25 (02): : 615 - 622
  • [4] Polynomial modular n-queens solutions
    Bell, Jordan
    ACTA ARITHMETICA, 2007, 129 (04) : 335 - 339
  • [5] 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
  • [6] A Linear Time Solution for N-Queens Problem Using Generalized Networks of Evolutionary Polarized Processors
    Arroyo Montoro, Fernando
    Gomez-Canaval, Sandra
    Jimenez Vega, Karina
    Ortega de la Puente, Alfonso
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2020, 31 (01) : 7 - 21
  • [7] The N-queens Problem on a symmetric Toeplitz matrix
    Szaniszlo, Zsuzsanna
    Tomova, Maggy
    Wyels, Cindy
    DISCRETE MATHEMATICS, 2009, 309 (04) : 969 - 974
  • [8] Neural networks for the N-Queens Problem: a review
    Mandziuk, J
    CONTROL AND CYBERNETICS, 2002, 31 (02): : 217 - 248
  • [9] Regular solutions of the n-queens problem on the torus
    Burger, AP
    Mynhardt, CM
    Cockayne, EJ
    UTILITAS MATHEMATICA, 2004, 65 : 219 - 230
  • [10] An improved genetic algorithm for the n-queens problem
    Hynek, J
    IC-AI'2000: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 1-III, 2000, : 517 - 522
12345