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