یک الگوریتم تقریبی بهبود یافته برای مسئله تاکردن خط کش
- سال انتشار: 1383
- محل انتشار: دهمین کنفرانس سالانه انجمن کامپیوتر ایران
- کد COI اختصاصی: ACCSI10_213
- زبان مقاله: فارسی
- تعداد مشاهده: 1884
نویسندگان
آزمایشگاه تحقیق و توسعه نرم افزار دانشگاه صنعتی امیرکبیر
چکیده
مسئله تاکردن خط کش یکی از مسائل معروف هندسه محاسباتی محسوب می شود که جزو مسائل NP-complete می باشد هدف این مسئله تاکردن یک زنجیره باز n قسمتی می باشد به قسمیکه طول افقی زنجیره تا شده به کمترین مقدار خود برسد ما دراین مقاله یک الگوریتم تقریبی با پیچیدگی زمانی O(n.log n برای تاک ردن زنجیره ارایه کرده ایم که طول زنجیره تا شده را به حدی می رساند که نسبت به الگوریتمهای قبلی بسیار بهتر است با یک نمونه گیری آماری نشان داده شده است که در بیش از 95% از موارد می توان این الگوریتم را طوری تغییر داد که پیچیدگی زمانی آن به O(n کاهش یابد بطوریکه به همان خوبی عمل کند. توسط یک نمونه گیری آماری نشان داده شده است که اگر طول قطعات زنجیره تصادفی انتخاب شود آنگاه در 62% مواقع حد بالای الگوریتم مورد نظر بهتر از روش تقریبی قبلی می باشد و در بقیه موارد نیز با آن برابر است.کلیدواژه ها
تاکردن خط کش، بازوهای روبات، زنجیره باز و الگوریتمهای تقریبیمقالات مرتبط جدید
- سیستم تشخیص نفوذ در محیط رایانش ابری با استفاده از یادگیری ویژ گی
- کاهش هزینه تعمیراتی ماشین های سنگین از طریق بهبود الگوریتم درخت تصمیم با الگوریتم های انتخاب ویژگی Information Gain ،Correlation و SVM
- پردازش کوانتومی تصاویر پزشکی و تشخیص لبه آن با استفاده از الگوریتم QHED
- بررسی و مقایسه روشهای تشخیص اکانت های جعلی در شبکه های اجتماعی
- مکان یابی و مقدار بهینه منابع تولید پراکنده به منظورکاهش تلفات و بهبود انحراف ولتاژ شبکه نامتعادل توزیع
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.