عنوان :

مقاله یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح

تعداد صفحات : ۳۳

نوع فایل : ورد و قابل ویرایش

چکیده

در این مقاله یک الگوریتم ساده برای مسئله‌ی کوتاهترین مسیر تک-منبع در یک گراف مسطح با یالهای با وزن غیر‌منفی ارائه خواهیم داد. الگوریتم مزبور در زمان  و با انجام ، ، عمل بر روی مدل EREW PRAM اجرا می‌شود. بطور کلی دو روش اصلی برای حل مسایل کوتاهترین مسیر بطور موازی وجود دارد. یکی بر اساس ناحیه بندی گراف به ناحیه‌ها استوار است و دیگری بر اساس عملیات ماتریسی بر روی گراف ورودی عمل میکند. در این مقاله ما مساله‌ی کوتاهترین مسیر تک-منبع را بر روی گراف با وزن یالهای غیرمنفی را با استفاده از روش ناحیه‌بندی گراف بر روی  را بر روی گراف با وزن یالهای غیرمنفی را با استفاده از روش ناحیه‌بندی گراف بر روی EREW PRAM حل کردیم. زمان الگوریتم ما کمتر از زمان خطی است،  ، ، اما به نظر می‌رسد رسیدن به میزان کار کمتر از زمان خطی بسیار مشکل باشد . حد پایین الگوریتمها تابعی از مدل PRAM است. مساله‌های که در کلاس پیچیدگی NC قرار دارند می‌توانند بر روی PRAM در زمان چندجمله‌ای لگاریتمی با استفاده از تعداد پروسسورهایی از درجه‌ی چندجمله‌ای لگاریتمی حل شوند. مساله‌ی کوتاهترین مسیر به عنوان یک مساله‌ی قابل حل در NC شناخته می‌شود .

مهمترین ویژگی الگوریتم داده شده سادگی آن است که پیاده سازی آن را راحت می‌کند. می‌توان این الگوریتم را به سادگی در مدل MPI پیاده سازی کرد. تنها تفاوتی که در مدل MPI وجود دارد اینست که هزینه‌ی ارسال پیام را نمی‌توانیم همسنگ با سایر مراحل اجرای الگوریتم در نظر بگیریم چرا که ارسال پیام از یک پروسسور به دیگری خیلی بیشتر از هزینه اعمال محاسباتی زمان می‌برد. لذا در پیاده‌سازی این مساله بر روی مدل MPI باید تغییراتی در  آن بعمل آوریم.

واژه های کلیدی: مسئله‌ی کوتاهترین مسیر، الگوریتم،  ناحیه‌بندی گراف ، الگوریتم سریال Liption-Tarjan، الگوریتم موازی Gazit-Miller

فهرست مطالب

چکیده    ۱
۱- مقدمه    ۲
۲- مقدمات اولیه    ۴
۳- الگوریتم کوتاهترین مسیر    ۸
۴- بدست آوردن ناحیه‌بندی گراف بصورت موازی    ۱۸
۴-۱ الگوریتم سریال Lipton-Tarjan برای یافتن جداساز در گراف    ۱۹
۴-۲ الگوریتم موازی Gazit-Miller برای یافتن جداساز در گراف    ۲۰
الگوریتم: Gazit-Miller    ۲۱
۴-۳ الگوریتم موازی برای ناحیه‌بندی گراف    ۲۴
۵- پیاده‌سازی بر روی MPI    ۲۶
۶- جمع‌بندی و نتیجه‌گیری    ۲۹
۷- منابع و مآخذ    ۳۰

 منابع و مآخذ

J. L. Träff, C. D. Zaroliagis,  A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs , Journal of Parallel and Distributed Computing 60, 1103-1124 (2000).

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introuduction to Algorithms (second edition), chapter 24, McGraw-Hill Book Company.

G. N. Fredrickson, Fast algorithms for shortest path in planar graphs with applications, SIAM J. Comput. 16, 6 (1987), 1004-1022.

R. j. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36, 2 (1979), 177-189.

H. Gazit and G. L. Miller, An optimal parallel algorithm for a separator for planar graphs, Unpublished manuscript, 1987.

۱- مقدمه

مساله‌ی کوتاهترین مسیر یک مساله‌ی زیربنایی و مهم در بهینه‌سازی ترکیبیاتی است که از ارزش عملی و تئوری زیادی برخوردار است. برای یک گراف جهت‌دار که شامل n راس و m یال است، مساله‌ی کوتاهترین مسیر عبارت است از پیدا کردن یک مسیر با کمترین وزن بین هر دو راس u و v که در مجموعه‌ی راسها وجود دارند. وزن مسیر u-v برابر مجموع وزن یالهای بین آنهاست. وزن کوتاهترین مسیر بین u-v ، فاصله از u تا v نامیده می‌شود. مساله‌ی کوتاهترین مسیر، بر حسب جفت راسهای u و v و نحوه‌ی وزن‌گذاری یالهای گراف به گونه‌های مختلفی تقسیم می‌شود.

اگرچه الگوریتم‌های سریال کارا[۱] برای بیشتر این گونه مسایل وجود دارند اما هنوز فقدان یک الگوریتم موازی کارا برای آن احساس می‌شود؛ الگورتیم کارا ، یعنی الگوریتمی که میزان کار[۲] انجام شده توسط آن برای حل مساله معادل یا نزدیک به تعداد کاری باشد که توسط بهترین الگوریتم سریال لازم است (منظور از کار، مجموع تمام کارهایی است که توسط پروسسورها انجام می‌شود). طراحی یک الگوریتم کارا برای مساله‌ی کوتاهترین مسیر ، یک مساله‌ی حل نشده‌ی مهم را در پردازش موازی تشکیل می‌دهد. یکی از دلایل ممکن برای نبود چنان الگوریتمی می‌تواند این باشد که بیشتر تاکیدها بر روی به دست آودردن یک الگوریتم خیلی سریع (یعنی NC) قرار گرفته است. به هر حال در اغلب موقعیتهای عملی، که تعداد پروسسورهای موجود ثابت و خیلی کوچکتر از اندازه‌ی مساله‌ای است که در دست داریم ، هدف اصلی و ابتدایی ما اینست که یک الگوریتم work-efficient (به‌جای الگوریتم خیلی سریع) داشته باشیم؛ چرا که در چنان مواردی زمان اجرا بر کاری که بین پروسسورها تقسیم می‌شود غالب است. اگر چنان الگوریتمی سایر پارامترهای خاص مانند سادگی و پیاده‌سازی راحت را داشته باشد از اهمیت ویژه‌ای برخوردار خواهد بود.

یکی از گونه‌های مهم مساله‌ی کوتاهترین مسیر ، مساله‌ی کوتاهترین مسیر تک-منبع یا درخت کوتاهترین مسیر است : با داشتن یک گراف جهت‌دار که شامل n راس و m یال و یک راس مشخص که منبع نامیده می‌شود، است، مساله‌ی ما عبارت است از پیدا کردن کوتاهترین مسیر از s به تمام راسهای دیگر در G . مساله‌ی کوتاهترین مسیر تک-منبع یک راه حل سریال کارا دارد مخصوصا وقتی که G هیچ راس منفی نداشته باشد. در این مورد مساله می‌تواند توسط الگوریتم دایسترا در زمان با استفاده از هیپ فیبوناچی[۳] یا یک ساختار داده‌ی صف اولویت با زمان حدی مشابه، حل شود[۲] .

در این مقاله ما برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی یک گراف مسطح G با وزن یال حقیقی و غیرمنفی ، یک الگوریتم ساده ارایه می‌دهیم که پیاده‌سازی آن راحت است. با مصالحه‌ای بر زمان اجرا ، الگوریتمی (قطعی) ارایه می‌دهیم که از لحاظ work-efficiency بهبودی بر الگوریتمهای قبل از آن باشد. این الگوریتم که با جزییات کامل و اثبات در [۱] ارایه شده است. در اینجا ما آن الگوریتم را با توضیحات بیشتر توضیح می‌دهیم.  به‌طور دقیقتر الگوریتم مزبور بر روی EREW PRAM در زمان  و با انجام  عمل ، اجرا می‌شود که  .

مانند الگوریتمهای کوتاهترین مسیر تک-منبع قبلی ، الگوریتم حاضر بر اساس ناحیه‌بندی گراف و تبدیل مساله به یک دسته از مسایل کوتاهترین مسیر بر روی ناحیه‌ها، عمل می‌کند. عملکرد الگوریتم ما به این صورت است که با داشتن یک ناحیه‌بندی[۴] از گراف، ما برای هر ناحیه الگوریتم دایسترا  را بکار می‌بریم و در پایان ، الگوریتم دایسترا را بر روی گراف کمکی که با استفاده از اطلاعات کوتاهترین مسیر در نواحی ساخته شده ، اجرا می‌کنیم. جزییات این الگوریتم در بخشهای بعدی آمده است. با تولید کپی‌های مناسب و کافی از یالهای گراف ، از خواندن و نوشتن همزمان  پروسسورها در حافظه جلوگیری می‌شود. همانطور که گفتیم ما در الگوریتم خود نیازمند یک ناحیه‌بندی از گراف ورودی هستیم که برای محاسبه‌ی این ناحیه‌بندی ، ما یک پیاده‌سازی EREW PRAM از الگوریتم ارائه شده در [۳] را ارایه می‌دهیم. این پیاده‌سازی خاص، یک ناحیه‌بندی از گراف مطابق با نیاز الگوریتم ما را محاسبه می‌کند. در این الگوریتم هم فرض می‌شود که گراف ورودی مسطح است.

مهمترین امتیاز الگوریتم ما سادگی آن است که پیاده‌سازی آنرا راحت می‌کند، طوری که پیاده‌سازی آن بر اساس روتینهای زیربنایی و قابل فهم ، همانطور که در ادامه گفته خواهد شد، استوار است که می‌توان آنها را در همه‌ی کتابخانه‌های الگوریتمهای موازی یافت. می‌توان این الگوریتم را با انجام تغییراتی بر روی مدل برنامه نویسی MPI به راحتی پیاده کرد. ذکر این نکته حایز اهمیت است که برای ماشینی که اجازه‌ی خواندن و نوشتن همزمان را می‌دهد، الگوریتم ما می‌تواند به‌طرز قابل توجهی ساده‌تر شود؛ بخاطر اینکه دیگر ایجاد کپی‌های فراوان از گراف ورودی برای خواندن همروند لازم نیست.

ما در بخش بعدی ، تعاریف را ارایه می‌دهیم و برخی از نکات ابتدایی در مورد جداساز‌ها (separator) و ناحیه‌بندی گراف مسطح را بیان می‌کنیم. الگوریتم ما در بخش ۳ ارایه شده است. در بخش ۴ هم جزییات مربوط به پیاده‌سازی بدست آوردن یک ناحیه‌بندی از گراف را توضیح می‌دهیم. در بخش ۵ در مورد پیاده‌سازی الگوریتم بر روی MPI صحبت می‌کنیم. نتیجه‌گیری و جمع‌بندی هم در بخش ۶ ارایه شده است.

۲- مقدمات اولیه

در ادامه‌ی این مقاله فرض کنید یک گراف جهت دار مسطح با وزن یالهای حقیقی و غیر منفی است که  راس و یال دارد (گراف را مسطح در نظر گرفتیم). در ادامه وقتی ما در مورد خصوصیات جداساز گراف G صحبت می‌کنیم، ما به گراف غیرجهت‌دار G اشاره داریم که با حذف جهت از یالهای آن به‌دست می‌آید (یعنی جداساز را بر روی گراف غیرجهت‌دار پیدا می‌کنیم). اما وقتی ما در مورد کوتاهترین مسیر صحبت می‌کنیم، به‌هر حال ما جهت یالها را به حساب می‌آوریم.

تعریف ۱ جداسازِ یک گراف ، برابر است با زیر مجموعه‌ای مانند C از ، که بخشهای حذف‌شده از را به دو زیر مجموعه‌ی جدا از هم A و B تقسیم می‌کند، بطوری‌که هر مسیر از یک راس در A به یک راس در B ، حداقل شامل یک راس از C باشد.

به هر کدام از راسهای گراف یک عدد نسبت می‌دهیم و به آن  ارزش[۵] راس می‌گوییم. ارزش هر راس را برابر در نظر می‌گیریم که n  برابر تعداد راسهای گراف است. این برای آن است که هنگام تقسیم گراف به بخش‌های جدا از هم آنرا بصورت متوازن تقسیم کنیم. فرض کنید ، نشان دهنده‌ی ارزش راس باشد. آنگاه ارزش زیرمجموعه‌ی ، بصورت نشان داده خواهد شد .

در شکل ۱ یک جداساز نمونه برای گراف نشان داده شده است.

Lipton  و Tarjan در قضیه‌ی زیر ، [۴] ، نشان دادند که اندازه‌ی جداساز گراف می‌تواند کوچک باشد.

قضیه ۱ (قضیه‌ی جداساز مسطح) فرض کنید یک گراف n راسی مسطح است با ارزش‌های غیرمنفی بر روی راسهای آن که مجموع آنها برابر ۱ است؛ آنگاه یک جداساز S  برای G وجود دارد که V را به دو مجموعه‌ی  و تقسیم می‌کند ، به طوری که و هر کدام از و ، حداکثر مجموع ارزش را دارند.

[۱] efficient

[۲] work

[۳] Fibonacci heap

[۴] region decomposition

[۵] cost

جهت دریافت و خرید متن کامل مقاله و تحقیق و پایان نامه مربوطه بر روی گزینه خرید انتهای هر تحقیق و پروژه کلیک نمائید و پس از وارد نمودن مشخصات خود به درگاه بانک متصل شده که از طریق کلیه کارت های عضو شتاب قادر به پرداخت می باشید و بلافاصله بعد از پرداخت آنلاین به صورت خودکار  لینک دنلود مقاله و پایان نامه مربوطه فعال گردیده که قادر به دنلود فایل کامل آن می باشد .