کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875434 1441953 2018 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving the N-Queens problem using dP systems with active membranes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Solving the N-Queens problem using dP systems with active membranes
چکیده انگلیسی
The N-Queens problem consists of placing N queens on an N×N chessboard such that no two queens threaten each other (i.e. same row, column, or diagonal). P systems solutions to the N-Queens problem and related problems (e.g. SAT) are often in a nondistributed way, i.e. the complete input to the problem enters the system through a single input membrane and the problem is solved. dP systems involve using more than one P system to solve problems in a distributed way, i.e. the problem input is partitioned and each partition enters the system using distinct components (which are also P systems). In this work, we solve the N-Queens problem using dP systems where the components are P systems with active membranes. Our 2-component and 3-component solutions partition the elements of the input multiset based on the clauses they represent. Compared to the nondistributed solution, our 2-component and 3-component solutions reduce the computation time by a half and by a third, respectively. Besides the analysis of the computation time, we also analyze communication costs. ComN, indicating the number of computation steps where communication occurred, is constant for both solutions. ComR, the number of intercomponent communication rules used, and ComW, the number of object communicated, are in terms of S, where S is the number of solutions to the problem instance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 736, 6 August 2018, Pages 1-14
نویسندگان
, , , ,