یک الگوریتم موازی و ساده برای مسالهی
کوتاهترین مسیر تک-منبع
بر روی گراف مسطح
چکیده
در این مقاله یک الگوریتم ساده برای مسئلهی کوتاهترین مسیر تک-منبع در یک گراف مسطح با یالهای با وزن غیرمنفی ارائه خواهیم داد. الگوریتم مزبور در زمان و با انجام ، ، عمل بر روی مدل EREW PRAM اجرا میشود. نقطه قوت الگوریتم در سادگی آن است که آنرا برای پیادهسازی و استفاده ، در عمل بسیار کارامد میسازد. در این مقاله ساختار دادههایی برای پیادهسازی این الگوریتم بر روی EREW PRAM ارایه شده است. میتوان این الگوریتم را با انجام تغییراتی بر روی مدل برنامهنویسی MPI به سادگی پیاده کرد. الگوریتم ما بر اساس ناحیهبندی گراف ورودی و استفاده از روش موازی الگوریتم دایسترا ، بنا شده است.
1 مقدمه
مسالهی کوتاهترین مسیر یک مسالهی زیربنایی و مهم در بهینهسازی ترکیبیاتی است که از ارزش عملی و تئوری زیادی برخوردار است. برای یک گراف جهتدار که شامل n راس و m یال است، مسالهی کوتاهترین مسیر عبارت است از پیدا کردن یک مسیر با کمترین وزن بین هر دو راس u و v که در مجموعهی راسها وجود دارند. وزن مسیر u-v برابر مجموع وزن یالهای بین آنهاست. وزن کوتاهترین مسیر بین u-v ، فاصله از u تا v نامیده میشود. مسالهی کوتاهترین مسیر، بر حسب جفت راسهای u و v و نحوهی وزنگذاری یالهای گراف به گونههای مختلفی تقسیم میشود.
اگرچه الگوریتمهای سریال کارا برای بیشتر این گونه مسایل وجود دارند اما هنوز فقدان یک الگوریتم موازی کارا برای آن احساس میشود؛ الگورتیم کارا ، یعنی الگوریتمی که میزان کار انجام شده توسط آن برای حل مساله معادل یا نزدیک به تعداد کاری باشد که توسط بهترین الگوریتم سریال لازم است (منظور از کار، مجموع تمام کارهایی است که توسط پروسسورها انجام میشود). طراحی یک الگوریتم کارا برای مسالهی کوتاهترین مسیر ، یک مسالهی حل نشدهی مهم را در پردازش موازی تشکیل میدهد. یکی از دلایل ممکن برای نبود چنان الگوریتمی میتواند این باشد که بیشتر تاکیدها بر روی به دست آودردن یک الگوریتم خیلی سریع (یعنی NC) قرار گرفته است. به هر حال در اغلب موقعیتهای عملی، که تعداد پروسسورهای موجود ثابت و خیلی کوچکتر از اندازهی مسالهای است که در دست داریم ، هدف اصلی و ابتدایی ما اینست که یک الگوریتم work-efficient (بهجای الگوریتم خیلی سریع) داشته باشیم؛ چرا که در چنان مواردی زمان اجرا بر کاری که بین پروسسورها تقسیم میشود غالب است. اگر چنان الگوریتمی سایر پارامترهای خاص مانند سادگی و پیادهسازی راحت را داشته باشد از اهمیت ویژهای برخوردار خواهد بود.
یکی از گونههای مهم مسالهی کوتاهترین مسیر ، مسالهی کوتاهترین مسیر تک-منبع یا درخت کوتاهترین مسیر است : با داشتن یک گراف جهتدار که شامل n راس و m یال و یک راس مشخص که منبع نامیده میشود، است، مسالهی ما عبارت است از پیدا کردن کوتاهترین مسیر از s به تمام راسهای دیگر در G . مسالهی کوتاهترین مسیر تک-منبع یک راه حل سریال کارا دارد مخصوصا وقتی که G هیچ راس منفی نداشته باشد. در این مورد مساله میتواند توسط الگوریتم دایسترا در زمان با استفاده از هیپ فیبوناچی یا یک ساختار دادهی صف اولویت با زمان حدی مشابه، حل شود[2] .
در این مقاله ما برای مسالهی کوتاهترین مسیر تک-منبع بر روی یک گراف مسطح G با وزن یال حقیقی و غیرمنفی ، یک الگوریتم ساده ارایه میدهیم که پیادهسازی آن راحت است. با مصالحهای بر زمان اجرا ، الگوریتمی (قطعی) ارایه میدهیم که از لحاظ work-efficiency بهبودی بر الگوریتمهای قبل از آن باشد. این الگوریتم که با جزییات کامل و اثبات در [1] ارایه شده است. در اینجا ما آن الگوریتم را با توضیحات بیشتر توضیح میدهیم. بهطور دقیقتر الگوریتم مزبور بر روی EREW PRAM در زمان و با انجام عمل ، اجرا میشود که .
مانند الگوریتمهای کوتاهترین مسیر تک-منبع قبلی ، الگوریتم حاضر بر اساس ناحیهبندی گراف و تبدیل مساله به یک دسته از مسایل کوتاهترین مسیر بر روی ناحیهها، عمل میکند. عملکرد الگوریتم ما به این صورت است که با داشتن یک ناحیهبندی از گراف، ما برای هر ناحیه الگوریتم دایسترا را بکار میبریم و در پایان ، الگوریتم دایسترا را بر روی گراف کمکی که با استفاده از اطلاعات کوتاهترین مسیر در نواحی ساخته شده ، اجرا میکنیم. جزییات این الگوریتم در بخشهای بعدی آمده است. با تولید کپیهای مناسب و کافی از یالهای گراف ، از خواندن و نوشتن همزمان پروسسورها در حافظه جلوگیری میشود. همانطور که گفتیم ما در الگوریتم خود نیازمند یک ناحیهبندی از گراف ورودی هستیم که برای محاسبهی این ناحیهبندی ، ما یک پیادهسازی EREW PRAM از الگوریتم ارائه شده در [3] را ارایه میدهیم. این پیادهسازی خاص، یک ناحیهبندی از گراف مطابق با نیاز الگوریتم ما را محاسبه میکند. در این الگوریتم هم فرض میشود که گراف ورودی مسطح است.
مهمترین امتیاز الگوریتم ما سادگی آن است که پیادهسازی آنرا راحت میکند، طوری که پیادهسازی آن بر اساس روتینهای زیربنایی و قابل فهم ، همانطور که در ادامه گفته خواهد شد، استوار است که میتوان آنها را در همهی کتابخانههای الگوریتمهای موازی یافت. میتوان این الگوریتم را با انجام تغییراتی بر روی مدل برنامه نویسی MPI به راحتی پیاده کرد. ذکر این نکته حایز اهمیت است که برای ماشینی که اجازهی خواندن و نوشتن همزمان را میدهد، الگوریتم ما میتواند بهطرز قابل توجهی سادهتر شود؛ بخاطر اینکه دیگر ایجاد کپیهای فراوان از گراف ورودی برای خواندن همروند لازم نیست.
ما در بخش بعدی ، تعاریف را ارایه میدهیم و برخی از نکات ابتدایی در مورد جداسازها (separator) و ناحیهبندی گراف مسطح را بیان میکنیم. الگوریتم ما در بخش 3 ارایه شده است. در بخش 4 هم جزییات مربوط به پیادهسازی بدست آوردن یک ناحیهبندی از گراف را توضیح میدهیم. در بخش 5 در مورد پیادهسازی الگوریتم بر روی MPI صحبت میکنیم. نتیجهگیری و جمعبندی هم در بخش 6 ارایه شده است.
2 مقدمات اولیه
در ادامهی این مقاله فرض کنید یک گراف جهت دار مسطح با وزن یالهای حقیقی و غیر منفی است که راس و یال دارد (گراف را مسطح در نظر گرفتیم). در ادامه وقتی ما در مورد خصوصیات جداساز گراف G صحبت میکنیم، ما به گراف غیرجهتدار G اشاره داریم که با حذف جهت از یالهای آن بهدست میآید (یعنی جداساز را بر روی گراف غیرجهتدار پیدا میکنیم). اما وقتی ما در مورد کوتاهترین مسیر صحبت میکنیم، بههر حال ما جهت یالها را به حساب میآوریم.
تعریف 1 جداسازِ یک گراف ، برابر است با زیر مجموعهای مانند C از ، که بخشهای حذفشده از را به دو زیر مجموعهی جدا از هم A و B تقسیم میکند، بطوریکه هر مسیر از یک راس در A به یک راس در B ، حداقل شامل یک راس از C باشد.
به هر کدام از راسهای گراف یک عدد نسبت میدهیم و به آن ارزش راس میگوییم. ارزش هر راس را برابر در نظر میگیریم که n برابر تعداد راسهای گراف است. این برای آن است که هنگام تقسیم گراف به بخشهای جدا از هم آنرا بصورت متوازن تقسیم کنیم. فرض کنید ، نشان دهندهی ارزش راس باشد. آنگاه ارزش زیرمجموعهی ، بصورت نشان داده خواهد شد .
در شکل 1 یک جداساز نمونه برای گراف نشان داده شده است.
Lipton و Tarjan در قضیهی زیر ، [4] ، نشان دادند که اندازهی جداساز گراف میتواند کوچک باشد.
قضیه 1 (قضیهی جداساز مسطح) فرض کنید یک گراف n راسی مسطح است با ارزشهای غیرمنفی بر روی راسهای آن که مجموع آنها برابر 1 است؛ آنگاه یک جداساز S برای G وجود دارد که V را به دو مجموعهی و تقسیم میکند ، به طوری که و هر کدام از و ، حداکثر مجموع ارزش را دارند.
شکل 1 . یک جداساز برای گراف که نودهای آن با رنگ
خاکستری نشان داده شدهاند.
ما جداساز S را یک جداسازِ برای G مینامیم.
تعریف 2 ناحیهبندی یک گراف یعنی تقسیم بندی راسهای گراف به نواحی جداگانه ، بطوریکه : (1) هر راسی یا درونی باشد، یعنی متعلق به دقیقا یک ناحیه باشد، یا مرزی باشد، یعنی حداقل بین دو ناحیه مشترک باشد؛ (2) هیچ یالی بین دو راس درونی که متعلق به نواحی مختلف هستند، موجود نباشد. برای هر عدد صحیح ، ، یک تقسیم-r گراف G ، یعنی تجزیهی ناحیهای G به ناحیه، که هر ناحیه حداکثر راس و حداکثر راس مرزی داشته باشد ( و ضریبهای ثابت هستند).
شکل 2 یک ناحیهی بندی نوعی برای یک گراف را نشان داده است.
شکل 2 . ناحیهبندی گراف به 3 ناحیهی مجزا
روالهای مورد نیاز الگوریتم ما عبارتند از: (1) الگوریتم دایسترا (نسخهی سریال و موازی) که توسط یک ساختار دادهی هیپ (مثلا باینری هیپ) پیادهسازی شده است. (2) یک پیادهسازی استاندارد الگوریتم محاسبهی پیشوند (یا پیشوند بخشی ) و مرتبسازی؛ و (3) الگوریتم موازی جداساز مسطح که توسط Gazit و Miller در [5] ارایه شده ؛ نسخهی پیادهسازی EREW PRAM این الگوریتم در بخش 4 داده شده است.
دو زیرروال اصلی که توسط الگوریتم ما فراخوانی میشوند عبارتند از: (1) الگوریتم سریال دایسترا ؛ که ما آنرا در داخل الگوریتم خودمان ، بر روی گراف H با راس منبع s به صورت ، فراخوانی خواهیم کرد. (2) نسخهی موازی الگوریتم دایسترا ؛ این الگوریتم بر روی گراف در زمان با استفاده از پروسسور روی EREW PRAM اجرا میشود (که و ) . برای فراخوانی الگوریتم دایسترای موازی ، برای و راس مبدا s از عبارت استفاده میکنیم. در اینجا فرض میکنیم که خواننده با الگوریتم دایسترا آشناست. برای یادآوری میتوانید به [2] مراجعه کنید.
الگوریتم دایسترای موازی : نسخهی موازیشدهی الگوریتم دایسترا که دایسترای موازی نامیده میشود، سرراست و قابل فهم است و با بروز رسانی برچسبهای فاصله بصورت موازی انجام میپذیرد. ایدهی اصلی الگوریتم بصورت زیر است : فرض کنید که هر پروسسور P یک هیپ مخصوص به خود دارد که میتواند اعمال Insert و DecreaseKey را در زمان ثابت و اعمال Find و DeleteMin را در بدترین حالت در زمان انجام دهد (برای یاد آوری اعمال فوق به [2] نگاه کنید). فرض کنید یک راس با کوچکترین فاصله انتخاب شود و قبل از شروع تکرار بعدی به P پروسسور فرستاده (broadcast) شود. لیست مجاورت راس انتخاب شده ، به P بخش با اندازههای مساوی تقسیم میشود بطوریکه فاصلهی راسهای مجاور بتواند بطور موازی در زمان بهروز شود (d درجهی راس انتخابشده است). هر پرسسوری که یک راس را به روز رسانده است ، آن را در داخل هیپ خصوصی خودش Insert میکند (یا عمل DecreaseKey را بر روی آن انجام میدهد)، و دوباره از هیپ خصوصی خودش یک راس با کوچکترین برچسب را انتخاب میکند. در تکرار بعدی، پروسسورها بطور دسته جمعی با انجام یک عمل محاسبهی پیشوند ، راسی را که در کل کوچکترین فاصله را دارد را انتخاب میکنند. راس انتخابشده از تمام هیپهایی که در آن است حذف میشود. حال تکرار بعدی میتواند آغاز شود. پیادهسازی الگوریتم فوق راحت است: هر پروسسوری یک هیپ محلی دارد بطوریکه میتواند یک نسخهی سریال از الگوریتم را مورد استفاده قرار دهد. تنها عمل موازی که مورد نیاز است ، عمل محاسبهی پیشوند است.
لازم به ذکر است که ، استفاده از هر هیپی با بدترین زمان برای اعمال آن (مثلا هیپ دودویی)، خواست ما را برآورده میسازد. همانطور که در بخش 3 خواهیم دید، کار انجام شده توسط این نسخه از پیادهسازی الگوریتم دایسترای موازی ، ، بطور مجانبی از کارهایی که توسط سایر مراحل الگوریتم انجام میشود کمتر است (برای اینکه ).
3 الگوریتم کوتاهترین مسیر
در این بخش ما الگوریتم خود را برای حل مسالهی کوتاهترین مسیر تک-منبع بر روی گراف مسطح G با وزن یال غیرمنفی ، ارایه میدهیم. ما فرض میکنیم که گراف G دارای یک تقسیم-r معلوم است (تعریف 2 را ببینید). در بخش 4 نشان خواهیم داد که چگونه میتوان یک تقسیم-r برای گراف یافت. فعلا فرض میکنیم جنین تقسیمی را داریم.
فرض کنید که راس منبعی باشد که میخواهیم درخت کوتاهترین مسیر را برای آن حساب کنیم. بطور خلاصه الگوریتم ما بصورت زیر عمل میکند :
در داخل هر ناحیه ، برای هر راس مرزی v ، یک درخت کوتاهترین مسیر با ریشهی v محاسبه میشود. این محاسبات بصورت همروند با استفاده از الگوریتم دایسترا بر روی نواحی انجام میشود. در ناحیهای که شامل s است ، اگر s یک راس مرزی نباشد، یک محاسبهی اضافی باید انجام شود. سپس G را به تبدیل میکنیم. گراف شامل موارد زیر است : راس مبدا s ؛ تمام راسهای مرزی بر روی نواحی G ؛ یالهای بین هر دو راس مرزی که به ناحیهی یکسانی از G تعلق دارند که وزنهای آنها معادل با فاصلهی آنها در داخل ناحیه است (اگر مسیر بین آنها وجود نداشته باشد، یال متناظر آن برابر قرار داده میشود)؛ در درون ناحیهای که شامل s است ، مثلا ناحیهی ، یالهای بین s و راسهای مرزی نیز در شامل میشوند که وزن این یالها برابر با فاصلهی راسهای مرزی از s است. بعد از بدست آوردن ، یک محاسبه برای بدست آوردن کوتاهترین مسیر تک-منبع با استفاده از الگوریتم موازی دایسترا بر روی آن انجام میدهیم که در نتیجه ، کوتاهترین مسیر از s به تمام راسهای دیگر ، یعنی تمام راسهای مرزی در G ، محاسبه میشود. بعد از این مرحله، سرانجام کوتاهترین مسیر از s به باقیماندهی راسها در G (یعنی راسهای درونی) بصورت موازی محاسبه میشود. برای محاسبهی فاصلهی هر راس درونی ، از اطلاعات راسهای مرزی ناحیهی متعلق به آن استفاده میشود. جزییات پیادهسازی الگوریتم ما بصورت زیر است :
ورودی: یک گراف جهتدار مسطح ، و یک راس منبع مشخص ، و یک تقسیم-r از گراف به نواحی ، و . فرض کنید مجموعهی راسهای باشد و مجموعهی راسهای مرزی باشد. و مجموعهی را برابر مجموعهی تمام راسهای مرزی در نظر بگیرید. و همچنین برای را ، برابر مجموعهای از ناحیهها در نظر بگیرید که راس مرزی v متعلق به آنهاست. بدون از دست دادن کلیت مساله فرض کنید . اگر s یک راس مرزی باشد آنگاه بطور دلخواه از میان یکی از ناحیههایی که s بین آنها مشترک است انتخاب میشود.
گراف ورودی بهصورت مجموعهای از لیستهای مجاورت که در آرایه A ذخیره شدهاند، نشان داده میشود بطوریکه راسهای مجاور راس یک بخش متوالی در آرایه را تشکیل میدهد که آنرا بصورت نشان میدهیم (شکل 3 را نگاه کنید). برای راحت کردن تولید کپیهای مورد نیاز از گراف ، گراف ورودی به ساختار دادههای زیر مجهز شده است: هر راس داخلی ناحیهی (یعنی راسی که در قرار دارد) یک برچسب دارد که نشان دهندهی ناحیهای است که به آن تعلق دارد. مجموعهی راسهای مرزی (یعنی ) بصورت یک آرایه نشان داده میشود. همچنین تمام راسهای مرزی ،C، بصورت یک آرایه نشان داده میشوند. فرض میشود که تمام راسهای مجاور راس مرزی ، که متعلق به یک ناحیه هستند، یک بخش متوالی از راسها را در ایجاد میکنند. راسهای مرزیِ مجاورِ راس که آنها را با نشان میدهیم ، متعلق به چند ناحیه هستند که بطور دلخواه در درون یکی از بخشها قرار میگیرند. هر راس دو اشارهگر به دارد، یکی به راس ابتدایی و یکی به راس انتهایی در بخش متوالی از راسها در آرایه، که به تعلق دارد، اشاره میکند. هر یک اشارهگر به آرایهی ، که شامل ناحیههایی است که v در آنها یک راس مرزی است، دارد. سرانجام هر راس مرزی یک اشارهگر به محل در آرایهی دارد. نمایش ساختار دادههای مربوط به تقسیم-r در شکل 3 نشان داده شده است.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 23 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله یک الگوریتم موازی و ساده برای مسالهی کوتاهترین مسیر
