کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4945002 1438018 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Networks of splicing processors with evaluation sets as optimization problems solvers
ترجمه فارسی عنوان
شبکه های اسپلایسینگ پردازنده ها با مجموعه های ارزیابی به عنوان حل کننده های بهینه سازی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی
In this paper we consider a new highly parallel and distributed bio-inspired computational model having its underlying structure an undirected graph whose nodes are processors that use the splicing operation on the data they are processing. They communicate with each other via a protocol based on the compatibility between their accepting values with respect to some predefined evaluation sets and the values of the data computed by a valuation mapping. Here we use the valuation mapping from a quantitative perspective, hence this model might be more suitable to solve some specific hard optimization problems in a more efficient and succinct way. In the aim of supporting this possibility, we propose an algorithm based on these networks able to efficiently solve an NP-hard combinatorial problem, namely the 0/1 knapsack problem. We prove that the computation time of the network solving an instance of the problem is linear. Surprisingly enough, the size of the network is very small, only four nodes are sufficient and the topology of the network may be chosen as chain, ring or complete graph. Furthermore, the evaluation sets and the sets of compatible values associated with the nodes as well as the valuation mapping remain unchanged for all instances of the same size. This result suggests that this model is suitable to address optimization problems where quantitative conditions have a relevant role.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 369, 10 November 2016, Pages 457-466
نویسندگان
, , ,