الگوریتم زمان خطی برایتاکردن زنجیره باز در فضای یک بعدی

سال انتشار: 1384
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,313

فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ACCSI11_004

تاریخ نمایه سازی: 5 آذر 1390

چکیده مقاله:

یکی از مسائل معروف درهندسه محاسباتی مسئله تا کردن خط کش است که بخاطرNP-Completeبودن ارائه یک الگوریتم تقریبی برای آن از اهمیت زیادی برخوردا راست دراین مسئله یک زنجیره باز n قسمتی به عنوان ورودی مفروض است و هدف یافتن کمترین طول ممکن برای تاک ردن زنجیره در فضای یک بعدی می باشد ما دراین مقاله یک الگوریتم تقریبی با زمان خطی و حافظه مصرفی O(1) برای تاکردن زنجیره ارائه کرده ایم که طول زنجیره تا شده را به حدی می رساند که نسبت به الگوریتم های قبلی از حد بالای کمتری برخوردار است این الگوریتم در نوع خود بهترین الگوریتم گزارش شده تقریبی با زمان خطی برای مسئله تاکردن خط کش می باشد.

کلیدواژه ها:

مسئله تاکردن خط کش ، زنجیره باز

نویسندگان

علی نوراله

آزمایشگاه تحقیق وتوسعه نرم افزار دانشکده مهندسی کامپیوتر و فناوری ا

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • J. Hopcroft, D. Joseph and S. Whitesides, "On the movement ...
  • _ Kantabutra, "Reaching a point with an unanchored , International ...
  • R. Connelly, E. D. Demaine and G. Rote, "Straightening polygonal ...
  • T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, ...
  • T. Biedl, A. Lubiw and J. Sun, _ Can a ...
  • A. Mohades and M. R. Razzazi, "Reachability _ _ Region ...
  • S. Whitesides, "Algorithmic issues in the geometry of planar linkage ...
  • W. J. Lenhart and , H. Whitesides, "Reconfiguring Closed Polygonal ...
  • Nourollah A. and Razza. M., "An Improved Approximation Algorithm for ...
  • G. Calinescu and A. Dumitrescu, "The carpenter's ruler folding problem", ...
  • نمایش کامل مراجع