کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952430 1442031 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The approximation algorithms for a class of multiple-choice problem
ترجمه فارسی عنوان
الگوریتم‌های تقریبی برای دسته‌ای از مسئله چندگزینه‌ای
کلمات کلیدی
اشیای پوشای رنگی، هندسه محاسباتی، الگوریتم تقریبی، کوچکترین مسئله محیطی
فهرست مطالب مقاله
چکیده

کلمات کلیدی

1.مقدمه

2. مقدمات و تعاریف

1.2 مجموعه پوشای رنگی

2.2 مقدمات

3. الگوریتم‌هایی برای SECSC و MDCS بدون FCVD

1.3 یک روش برای ساخت مجموعه‌های پوشای رنگی

شکل 1. دایره‌های رنگین کمانی برای هر pj.  

شکل 2. مورد 1.

2.3 الگوریتم تقریبی برای مسئله SECSC بدون FCVD

3.3 کران بالا  و کران پایین مسئله SECSC

شکل3. مورد 2.

4.3 الگوریتم تقریبی 2 عاملی SECSC

شکل 4. مورد 3

5.3 الگوریتم تقریبی برای مسئله MDCS بدون FCVD

4. الگوریتم تقریبی برای مسئله PSPCHCS

1.4 مسئله PSPCHCS

شکل 5. گام‌های الگوریتم برای PSPCHCS

2.4 الگوریتم و عملکرد آن

شکل 6. اثبات الگوریتم برای PSPCHCS

5. مثالی از مسئله SECSC 2 مرکزی

1.5 مسئله SECSC دو مرکزی

2.5 یک مثال از مسئله SECSC دو مکرزی با m=5



 
ترجمه چکیده
مجموعه‌ای از n نقطه را در نظر بگیرید، که مجموعه واحد از m مجموعه رنگی است، ما روی کمترین دایره‌ای مطالعه می‌کنیم که حداقل یکی از هر مجموعه رنگی را پوشش دهد. در این مقاله، ما روی برخی از مسائل بهینه‌سازی برخی از ویژگی‌های مجموعه پوشای رنگی مطالعه می‌کنیم. در ابتدا، ما یک راه را برای پیدا کردن مجموعه پوشای رنگی برای هر نقطه نشان می‌دهیم و اتحادی از مجموعه‌های پوشای رنگی بدون FCVD (دیاگرام ورونوی دورترین رنگ ) را تشکیل می‌دهیم. روش برای پیدا کردن هر مجموعه پوشای رنگی براساس نزدیکترین نقطه‌های همسایه است که دارای رنگ‌های مختلف هستند. برای هر مجموعه پوشای رنگی، ما می‌توانیم یک دایره محیطی پیدا کنیم تا همه نقاط هر مجموعه پوشای رنگی را پوشش ‌دهد، که یک تقریب خوبی برای مسئله MDCS ( مجموعه پوشای رنگی با کمترین قطر ) است. ما یک الگوریتم تقریبی را برای مسئله SECSC ( کوچکترین دایره پوشای رنگی) با نتیجه تقریبی دو عاملی پیشنهاد می‌دهیم. برای |P|=n و |Q|=m ، بدترین زمان اجرای الگوریتم ما از مرتبه O(n2) است. اگرچه این نتایج به خوبی نتایج قبلی با FCVD نیست، عملکرد الگوریتم‌های ما در Rd خیلی بهتر از سایرین است. بعلاوه، الگوریتم تقریبی می‌تواند مسئله کمترین محیط مجموعه پوشای رنگی را سریعتر از زمان O(n2+nmlogn) و نسبت حل کند. این نتیجه، نسبت را فقط با هزینه کمی از پیچیدگی زمانی بهبود می‌بخشد. در نهایت، ما یک مثالی برای مسئله SECSC 2 مرکزی می‌دهیم. یک محاسبه سریع دایره محیطی 2 مرکزی با زمان O(n2) را پیشنهاد می‌دهیم، اما نسبت بستگی به شکاف بین نزدیکترین فاصله رنگی متمایز دارد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم‌های تقریبی برای دسته‌ای از مسئله چندگزینه‌ای
چکیده انگلیسی
Given a set of n points, which is a unit set of m colored sets, we study the minimum circle to cover one of each colored set at least. In this paper, we study some problems of optimizing some properties of color-spanning set. Firstly, we show a way to find a color-spanning set for each point and constitute a union of color-spanning sets without FCVD (The Farthest Color Voronoi Diagram). The approach to find each color-spanning set is based on the nearest neighbor points which have different colors. For every color-spanning set, we can find a enclosing circle to cover all points of each color-spanning set, which is a good approximate for MDCS (The Minimum Diameter Color-Spanning Set) problem. We propose an approximation algorithm for the SECSC (The Smallest Color-Spanning Circle) problem with 2-factor approximation result. For |P|=n and |Q|=m, the worst running time of our algorithm is O(n2). Although these results are not as good as previous results with FCVD, the performance of our algorithms in Rd is much better than others. Moreover, an approximation algorithm can solve problem of minimum perimeter of the color-spanning set faster with time of O(n2+nmlog⁡n) and ratio 6. This result improved the ratio with only a little cost of time complexity. At last, we give an example for the 2-center SECSC problem. A fast computation of 2-center enclosing circle is proposed with time of O(n2), but the ratio depends on the gap between the nearest distinct colored distance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 164-174
نویسندگان
, ,