عنوان پایان‌نامه
تقریب مسئله رنگ آمیزی دودویی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 99..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 78530;کتابخانه پردیس یک فنی شماره ثبت: 99..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 78530
- تاریخ دفاع
- ۱۵ شهریور ۱۳۹۵
- دانشجو
- فاطمه نعیمی
- استاد راهنما
- دارا معظمی
- چکیده
- مجموعه‌ای از سفارشات ماشین‌ها به صورت دنباله‌ای از حروف در قالب یک کلمه داده شده است. هدف، تخمین و ارائه رنگ آمیزی از این دنباله به گونه‌ای است که تعداد تغییرات رنگ در طول مراحل تولید مینیمم شود.انگیزه ایجاد یک برنامه و روش کاربردی در صنعت خودروسازی منجر به ارائه مسئله رنگ آمیزی کلمات شد. برای اولین بار این مسئله در سال 2004 توسط ایپینگ، هاجست تاتلر و اورتل مطرح شد و در همان مقاله نشان داده شد که این مسئله NP-کامل است. پس از آن با اعمال محدودیت هایی بر روی مسئله اصلی، مسئله پرکاربرد رنگ آمیزی دودویی عنوان شد که به قرار زیر است: m ماشین را در دنباله ای به طول 2m در اختیار داریم. هر ماشین در این دنباله دو مرتبه ظاهر خواهد شد و هر ماشین باید دقیقاً با دو رنگ، یکبار به رنگ آبی و بار دیگر به رنگ قرمز رنگ آمیزی شود. هدف، رنگ آمیزی این دنباله از ماشین‌ها به گونه‌ای است که تعداد تغییرات رنگ کلی مینیمم شود. در این پایان نامه نشان خواهیم داد که مسئله رنگ آمیزی دودویی معادل مسئله نابرش مینیمم در گرافها است، و از طریق این معادل سازی نتیجه خواهیم گرفت که این مسئله یک مسئله NP- سخت است. برای حل آن فاکتور تقریبی را پیشنهاد می‌کنیم و نشان خواهیم داد که این فاکتور ثابت نیست و بهترین تقریبی که برای آن می‌توان در نظر گرفت از مرتبه خواهد بود.
- Abstract
- Motivated by an application in the automobile industry, we present results and conjectures in a paintshop problem for words: Given a set of orders and represent a sequence of car body type by a word w , we must determine a sequence that minimizes the number of color change during production. This version were proposed and studied for the first time in 2004 by Epping, Hochstattler and Oertel. if we bound the number of colors or the size of the alphabet it has shown that this problem is NP-Complete. After that we focus on restricted instance of paintshop problem as Binary paintshop problem: we are given a 2m length sequence containing m cars, where each car appears twice. Each car need to be colored with two colors. The goal is to choose for each car, which of its occurrences receives either color, so as to minimize the total number of color changes in the sequence. In this thesis, we show that the binary paint shop problem is equivalent to the minimum uncunt problem and will result that this problem is NP-Hard to approximate within any constant factor and the approximation rate of that is from Min uncut problem.
