کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875434 | 1441953 | 2018 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving the N-Queens problem using dP systems with active membranes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Solving the N-Queens problem using dP systems with active membranes Solving the N-Queens problem using dP systems with active membranes](/preview/png/6875434.png)
چکیده انگلیسی
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
Journal: Theoretical Computer Science - Volume 736, 6 August 2018, Pages 1-14
نویسندگان
Kelvin C. Buño, Francis George C. Cabarle, Marj Darrel Calabia, Henry N. Adorna,