علی نوراله - استادیار، دانشکده ی مهندسی کامپیوتر، دانشگاه تربیت دبیرشهیدرجایی، تهران
نوشین بهزادپور - دانشجوی کارشناسی ارشد، دانشکده ی مهندسی کامپیوتر، دانشگاه تربیت دبیرشهیدرجایی، تهران

لینکیج ها کاربردهای فراوانی به ویژه در مدل کردن بازوی روبات دارند. تا به حال مسائل NP-Complete و PSPACE-Hard بسیاری درحوزه لینکیج ها مطرح گشته است. موضوع اصلی در این مقاله طرح یک مسأله NP-Hard جدید در زمینه حرکت لینکیج زنجیره باز است. هدف این مسأله، کمینه سازی اجزای متحرک لینکیج و تأثیر حرکت هر یک از این اجزا است، به نحوی که منجر به قرارگیری مجری نهایی در نقطه مقصد گردد. برای این منظور ابتدا به تعریف رسمی مسأله مورد بحث پرداخته و NP-Hard بودن آن با استفاده از کاهش پذیری به مسأله جمع زیرمجموعه ها اثبات می شود. سپس یک الگوریتم حریصانه با مرتبه زمانی ((O(n(2 و مصرف حافظه (O(n برای حل این مسأله ارائه می شود و نتایج محاسباتی حاصل از پیاده سازی الگوریتم با نتایج بهینه مقایسه می گردد. این مقایسه حاکی از کارایی و توانمندی الگوریتم پیشنهادی است.

لینکیج زنجیره باز،NP-Hard ، مسأله پیکربندی مجدد، مسأله دسترسی پذیری، الگوریتم حریصانه