Open AccessIntroducing a New NP-Hard Problem Regarding an Open Chain Linkage Using a New Greedy Method
Author(s) -
Ali Nourollah,
Nooshin Behzadpour
Publication year - 2016
Publication title -
bulletin de la société royale des sciences de liège
Language(s) - English
Resource type - Journals
ISSN - 1783-5720
DOI - 10.25518/0037-9565.5649
Subject(s) - greedy algorithm , linkage (software) , computer science , context (archaeology) , reduction (mathematics) , computational complexity theory , computation , mathematical optimization , point (geometry) , algorithm , theoretical computer science , mathematics , paleontology , biochemistry , chemistry , geometry , biology , gene
Linkages exhibit numerous applications especially in modelling robot arms. Until now, NP-Complete and PSPACE-Hard problems have been introduced within the linkage context. The main subject of this paper is to introduce a new NP-Hard problem regarding movement of open chain linkages. The objective of this problem is to minimize the moving components of the linkage and their related movement impact, in a way that the end effector is ultimately placed at the target point. For this purpose, first, the problem is formalized and its NP-Hard condition is proved using reduction of sum of subset problem. A greedy algorithm with the time complexity of O(n2) and space complexity of O(n) is proposed for solving the problem, and computation results from implementing the algorithm are compared with the optimized results. This comparison demonstrates the efficiency and capability of the proposed algorithm.