انطباق نقاط دو رنگ و همرنگ با مستطیل ها
- سال انتشار: 1395
- محل انتشار: اولین کنفرانس ملی مهندسی کامپیوتر، علوم کامپیوتر و فناوری اطلاعات
- کد COI اختصاصی: NCRC01_092
- زبان مقاله: فارسی
- تعداد مشاهده: 749
نویسندگان
دانشگاه یزد
چکیده
فرض کنید S مجموعه ای از نقاط در صفحه باشد به طوریکه هر عنصر آن دارای رنگ یا قرمز یا آبی است. یک انطباق از S با مستطیل یک مجموعه از جفت مستطیل های هم تراز مجزاست به طوریکه هر مستطیل شامل دقیقاً دو نقطه از S است. چنین انطباقی را همرنگ گوییم اگر هر مستطیل شامل نقاط همرنگ باشد، و دورنگ است اگر شامل نقاط با رنگ متفاوت باشد. در این مقاله دو مسأله زیر را دنبال می کنیم : 1) یافتن بزرگترین انطباق همرنگ از S با مستطیل ها. 2) یافتن بزرگترین انطباق دو رنگ از S با مستطیل ها. برای هر مسأله ما یک الگوریتم تقریبی با زمان چند جمله ای فراهم می کنیم به طوریکه یک انطباق با حداقل 1/4 تعداد مستطیل های انطباق بهینه را بسازد. نشان می دهیم که مسأله ی اول ان - پی سخت است اگر که یا مستطیل های منطبق با پاره - خط های هم تراز از محصور شده باشد یا آنکه S در موقعیت کلی باشد، یعنی هیچ دو نقطه از S دارای مختصات x,y یکسانی نباشد. در جلوتر نشان خواهیم داد مسأله ی دوم هم ان - پی سخت است اگر که S در موقعیت کلی باشد. این نتایج ان - پی سختی با نشان دادن تصمیم گیری درباره ان - پی کامل بودن انطباق کاملی که در هر حالت وجود دارد به دست می آید. نتاج تقریبی براساس ارتباط بین مسأله ی ما با مسأله ی پیدا کردن بزرگترین مجموعه ی مستقل در بین مجموعه ای از مستطیل های هم تراز است. در این مقاله یک انطباق نقاط تک رنگ با مستطیل ها و مربع ها و انطباق نقاط دو رنگ با پاره خط ها را توسعه می دهیم. در ادامه از تکنیکمان استفاده کرده و ثابت می کنیم تصمیم گیری درباره انطباق کامل با مستطیل ها در حالتی که نقاط همرنگ باشند ان - پی کامل است.کلیدواژه ها
الگوریتم های تقریبی - انطباق همرنگ - انطباق دورنگ - مسائل ان، پی سخت و ان، پی کاملمقالات مرتبط جدید
- سودآوری مشتریان در خردهفروشی قطعات یدکی ماشین آلات راهسازی با رویکرد یادگیری ماشین
- ارائه روشی کارآمد جهت شناسایی کودکان نیازمند به پیوند مغز استخوان با استفاده از ترکیب طبقه بند ماشین بردار پشتیبان و الگوریتم بهینه سازی فاخته
- استخراج بهینه پارامترهای تاثیر گذار الگوریتم بهینه سازی بوفالوی آفریقایی با هدف استخراج ویژگی های مهم به منظور افزایش کارایی طبقه بندی داده ها
- ارائه روشی کارآمد برای بهبود عملکرد الگوریتم بهینه سازی کلاغ سیاه به منظور افزایش صحت خوشه بندی داده ها
- استفاده از الگوریتم باور بیزین در لایه کاملا متصل شبکه عصبی کانولوشن با هدف افزایش دقت تشخیص تصاویر
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.