عنوان مقاله:

يك الگوريتم موازي و ساده براي مسئله‌ي

كوتاهترين مسير تك-منبع

بر روي گراف مسطح

تعداد صفحه: 35

فرمت: WORD (قابل ویرایش)

چكيده

در اين مقاله يك الگوريتم ساده براي مسئله‌ي كوتاهترين مسير تك-منبع[1] در يك گراف مسطح با يالهاي با وزن غير‌منفي ارائه خواهيم داد. الگوريتم مزبور در زمان و با انجام ، ، عمل بر روي مدل EREW PRAM اجرا مي‌شود. نقطه قوت الگوريتم در سادگي آن است كه آنرا براي پياده‌سازي و استفاده ، در عمل بسيار كارامد مي‌سازد. در اين مقاله ساختار داده‌هايي براي پياده‌سازي اين الگوريتم بر روي EREW PRAM ارايه شده است. مي‌توان اين الگوريتم را با انجام تغييراتي بر روي مدل برنامه‌نويسي MPI به سادگي پياده كرد. الگوريتم ما بر اساس ناحيه‌بندي گراف ورودي و استفاده از روش موازي الگوريتم دايسترا ، بنا شده است.

مقدمه

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

اگرچه الگوريتم‌هاي سريال كارا[1] براي بيشتر اين گونه مسايل وجود دارند اما هنوز فقدان يك الگوريتم موازي كارا براي آن احساس مي‌شود؛ الگورتيم كارا ، يعني الگوريتمي كه ميزان كار[2] انجام شده توسط آن براي حل مسئله معادل يا نزديك به تعداد كاري باشد كه توسط بهترين الگوريتم سريال لازم است (منظور از كار، مجموع تمام كارهايي است كه توسط پروسسورها انجام مي‌شود). طراحي يك الگوريتم كارا براي مسئله‌ي كوتاهترين مسير ، يك مسئله‌ي حل نشده‌ي مهم را در پردازش موازي تشكيل مي‌دهد.

يكي از دلايل ممكن براي نبود چنان الگوريتمي مي‌تواند اين باشد كه بيشتر تاكيدها بر روي به دست آودردن يك الگوريتم خيلي سريع (يعني NC) قرار گرفته است. به هر حال در اغلب موقعيتهاي عملي، كه تعداد پروسسورهاي موجود ثابت و خيلي كوچكتر از اندازه‌ي مسئله‌اي است كه در دست داريم ، هدف اصلي و ابتدايي ما اينست كه يك الگوريتم work-efficient (به‌جاي الگوريتم خيلي سريع) داشته باشيم؛ چرا كه در چنان مواردي زمان اجرا بر كاري كه بين پروسسورها تقسيم مي‌شود غالب است. اگر چنان الگوريتمي ساير پارامترهاي خاص مانند سادگي و پياده‌سازي راحت را داشته باشد از اهميت ويژه‌اي برخوردار خواهد بود.