با دانلود تحقیق در مورد يك الگوريتم موازي و ساده براي مساله‌ي كوتاهترين مسير تك منبع بر روي گراف مسطح در خدمت شما عزیزان هستیم.این تحقیق يك الگوريتم موازي و ساده براي مساله‌ي كوتاهترين مسير تك منبع بر روي گراف مسطح را با فرمت word و قابل ویرایش و با قیمت بسیار مناسب برای شما قرار دادیم.جهت دانلود تحقیق يك الگوريتم موازي و ساده براي مساله‌ي كوتاهترين مسير تك منبع بر روي گراف مسطح ادامه مطالب را بخوانید.

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

فرمت فایل:word و قابل ویرایش

تعداد صفحات فایل:21 صفحه

قسمتی از فایل:

چكيده

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

1 مقدمه

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

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

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

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

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

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

ما در بخش بعدي ، تعاريف را ارايه مي‌دهيم و برخي از نكات ابتدايي در مورد جداساز‌ها (separator) و ناحيه‌بندي گراف مسطح را بيان مي‌كنيم. الگوريتم ما در بخش 3 ارايه شده است. در بخش 4 هم جزييات مربوط به پياده‌سازي بدست آوردن يك ناحيه‌بندي از گراف را توضيح مي‌دهيم. در بخش 5 در مورد پياده‌سازي الگوريتم بر روي MPI صحبت مي‌كنيم. نتيجه‌گيري و جمع‌بندي هم در بخش 6 ارايه شده است.

2 مقدمات اوليه

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

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

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

در شكل 1 يك جداساز نمونه براي گراف نشان داده شده است.

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

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