طرح یک مسئله NP-Hard مربوط به لینکیج زنجیره باز و ارائه یک رویکرد حریصانه برای آن

سال انتشار: 1395
محل انتشار: کنفرانس بین المللی مهندسی کامپیوتر و فناوری اطلاعات
کد COI اختصاصی: CITCOMP01_208
زبان مقاله: فارسی
تعداد مشاهده: 2406

نویسندگان

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

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

چکیده

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

کلیدواژه ها

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.