بخشی از مقاله
مقدمه
يکي از کارهايي که تهيه کنندگان نقشه بهنگام تهيه نقشه انجام مي دهند, برچسب گذاري نقاط نقشه است . بـدين معني که در کنار هر نقطه اطلاعاتي راجع به آن نقطه مي نويسند. اطلاعات بايد به گونه اي برروي نقشه قرارگيرند که اطلاعات نقاط مختلف برروي هم قرار نگيرند. انجام خودکار برچسب گذاري نقشه توسط رايانه باعث سهولت و تسريع در انجام اينکار مي شود. براي رايانه اي کردن اين محاسبه نياز داريم که برچسب گذاري نقشه را بصورت دقيق تر بيـان کنيم .
تعريف ۱. برچسب گذاري معتبر: در يک صفحه n نقطه جدا از هم داده شده اند. مي خواهيم يک مجموعـه n تـايي از مربع ها به طول داشته باشيم بطوريکه هر نقطه کنج يک مربع (و نه بيشتر) قرار گيرد و کليه مربع ها با يکـديگر تداخل نداشته باشند(شکل ۱).
تعريف ۲. برچسب گذاري بهينه : در يک صفحه n نقطه جدا از هم داده شده اند. بـه ازاي کليـه اعـداد حقيقـي مي خواهيم سوپريمم را بنحوي پيدا کنيم که يک برچسب گذاري معتبر داشته باشيم (شکل ۲).
در سال ۹۲، فورمن و واگنر نشان دادند که مساله برچسب گذاري بهينه NP-hard است [۱]. آنها همچنين الگوريتم تقريبي ارائه دادند که برچسب گذاري معتبري به اندازه حداقل نصف اندازه بهينه مي يافت . همچنين آنهـا نشـان دادنـد که اگر آنگاه الگوريتم تقريبي با جواب چندجمله اي وجود ندارد که پاسخ بهتري را تضمين کنـد. پيچيـدگي الگوريتم آنها است . نتيجه مشابهي نيز در [۲] و [۳] گـزارش شـده اسـت . در سـال ۹۵ واگنـر و ولـف الگوريتم جديدي ارائه دادند که زمان اجرا و کيفيت پاسخ الگوريتم قبلي را تضـمين مـي کـرد[۴]. نقطـه قـوت ايـن الگوريتم نسبت به الگوريتم قبلي اين است که الگوريتم [۴] پاسخ هاي نزديکتري به اندازه بهينه برچسب گـذاري (در عمل ) مي دهد.
در اين مقاله ما يک الگوريتم موازي مبتني بر الگـوريتم [۴]، بـراي افـزايش سـرعت اجـراي برچسـب گـذاري ، ارائـه مي دهيم . در بخش ۲ الگوريتم غيرموازي [۴] را بيان مي کنيم . در بخـش ۳ الگـوريتم مـوازي را معرفـي مـي کنـيم و پيچيدگي آنرا حساب مي کنيم و در بخش ۴ هم نتيجه گيري آمده است . اين الگوريتم داراي افزايش سرعت برابـر بـا نسبت به الگوريتم غير موازي است .
۲- الگوريتم غيرموازي برچسب گذاري نقشه ها
الگوريتمي که شرح آن در ادامه مي آيد، الگوريتمي است که توسـط واگنـر و ولـف در سـال ۱۹۹۵ معرفـي شـده است [۴]. ابتدا چند تعريف ، که در ادامه از آنها استفاده خواهيم نمود را بيان مي کنيم .
تعريف ۳: براي هر نقطه مانند p واقع در نقشه ، بيانگر مربعي به طول است که نقطه p در جنوب غربـي ، جنوب شرقي ، شمال غربي يـا شـمال شـرقي آن قـرار دارد. يـک مقـدار حقيقـي اسـت .
همچنين pi را کانديداي iام نقطه p مي ناميم .
تعريف ۴: برچسب گذاري با اندازه برچسب عبارتست از برچسب گذاري معتبري که در آن کانديـداها داراي طـول يکسان و برابر باشند.
۲-۱- ساختار الگوريتم غير موازي
مرحله ۱: پيدا کردن کليه اندازه هاي تداخل با ارزش .
مرحله ۲: انجام جستجوي دودويي برروي اندازه هاي تداخل بدست آمده از مرحله قبل . براي هر اندازه تداخل بررسي مي کنيم که آيا پاسخي براي اين اندازه برچسب وجود دارد يا خير. اينکار را با اعمال سه گام زير انجام مي دهيم .
گام الف : پيش پردازش .
گام ب : حذف کانديداهاي غير ممکن و سپس انجام آزمايش SAT-2 برروي زير مجموعه باقي مانده .
گام ج : براي نقاطي که بيشتر از دو کانديدا دارند، دو کانديـدا را انتخـاب کـرده و سـپس توسـط SAT-2
بررسي مي کنيم که آيا پاسخي وجود دارد يا خير.
۲-۲- پيدا کردن اندازه هاي تداخل با ارزش
روشي که براي پيدا کردن اندازه هاي تداخل توسط ولف و واگنر معرفي شده است مبتني بـر دو قضـيه اسـت کـه آنها را اثبات نموده اند[۴].
قضيه ۱: کليه اندازه هاي تداخل با ارزش کوچکتر از اندازه برچسب بهينه هستند. بعبـارت ديگـر انـدازه هـاي تداخل بي ارزش بزرگتر از اندازه برچسب بهينه هستند.
قضيه ۲: تنها اندازه هاي تداخل بين نقطه p و نزديکترين هشت نقطه همسايه اش در هر يک از چهارسـمت نقطـه pبا ارزش هستند. شکل ۳ نمونه اي از اندازه تداخل بي ارزش را نشان مي دهد.
طبق قضيه ۲، براي بدست آوردن اندازه هاي تداخل نقطه اي مانند p، تنها بايد تعداد ثابتي از نزديکترين همسايه هاي آن نقطه مورد بررسي قرار گيرند. در [۵] الگوريتمي براي پيدا کردن نزديکترين k همسايه n نقطه ارائه شـده اسـت که داراي پيچيدگي زماني است . مرتب سازي اندازه هاي تداخل نيز n log n زمان نياز دارد. بنـابراين بدست آوردن اندازه هاي تداخل و مرتب سازي داراي پيچيدگي زماني (O(n log n خواهد بود.
۲-۳- بدست آوردن اندازه برچسب بهينه
در اين مرحله براي بدست آوردن اندازه برچسب بهينه , در فهرسـت انـدازه هـاي تـداخل بـه جسـتجوي دودويـي مي پردازيم . به ازاي هر اندازه تداخل (که جستجوي دودويي آنرا مشخص مي کند) سه گامي کـه در ادامـه مـي آيـد را انجام مي دهيم .
۲-۳-۱- گام الف : پيش پردازش
براي کليه کانديداهاي مانند pi بررسي مي کنيم ، اگر حاوي يک نقطه ديگر باشـد، آنگـاه کانديـداي pi را حذف مي کنيم در غير اينصورت فهرست جديدي از اطلاعات تداخل بـراي کانديـداي pi مـي سـازيم . ايـن فهرسـت شامل اندازه هاي تداخلي خواهد بود که از اندازه برچسب کوچکتر هستند.
