سفارش ترجمه تخصصی رشته ریاضی - تخصصی گراف ها

مرتب کردن

مرتب کردن کاری متداول در محاسبات علمی نیست: این محاسبات  چه مالی باشد یا بیولوژیکی (مثلا در تنظیم توالی)، در پایگاه داده­ها عمل مهمی محسوب می شود. اما گاهی، مثلا در پالایش شبکه سازگار (AMR) و کار­های دیگر، ساختار داده ها دستکاری می شود.

در این بخش نگاه کوتاهی داریم بر الگوریتم های اساسی و انجام موازی آنها. برای جزئیات رجوع کنید به [104] و منابع قید شده در آن.

 

برای ثبت سفارش ترجمه تخصصی کلیک کنید

8.1 مقدمه­ای کوتاه درباره مرتب سازی

8.1.1. پیچیدگی

الگوریتم­های زیادی برای مرتب سازی وجود دارد. به طور سنتی الگوریتم­ها براساس پیچیدگی محاسباتی از هم متمایز می شدند یعنی با داشتن آرایه­ای از n المان، چند عمل به صورت تابعی از n برای مرتب سازی آن لازم است.

از نظر تئوری می توان نشان داد که حداقل پیچیدگی الگوریتم باید O (n log n) باشد. در واقع چندین الگوریتم وجود دارد که این پیچیدگی در آنها تضمین شده است اما الگوریتم بسیار متداولی که Quiksort (مرتب سازی سریع) نامیده می شود با پیچیدگی پیش بینی شده O (n log n) و بدترین پیچیدگی O (n²) است.

8.1.2. مرتب سازی شبکه ها

الگوریتم­های مرتب سازی را می توان از نگاه دیگری دید و براساس مستقل بودن یا نبودن آنها از حالت داده­های ورودی متمایز کرد. برای مثالی از الگوریتمی که به داده­های ورودی وابسته است الگوریتم مرتب سازی را تصور کنید که از روی داده­ها می گذرد تا برررسی کند که قبلا مرتب سازی شده اند یا نه. این الگوریتم پیچیدگی خطی (یعنی n عمل برای n المان) برای لیست مرتب شده دارد و برای لیست مرتب نشده این پیچیدگی کمی بیشتر است.

الگوریتم متداول مرتب سازی سریع چنین وابستگی دارد زیرا براساس یافتن المان­های محوری است.

از سوی دیگر، الگوریتم معروف حباب (bubble) را می توان مستقل از داده های که قرار است مرتب شود، توصیف کرد. این الگوریتم عبارت است از:

الگوریتم 2: الگوریتم مرتب سازی حباب

به راحتی می توان دید که این الگوریتم با پیچیدگی O (n²) است: حلقه داخلی t مقایسه و تا t مبادله دارد. با با جمع بندی این از 1 تا n -1 تقریبا n² / 2 مقایسه و غالبا همان تعداد مبادله بدست می آید.

اینگونه الگوریتم مرتب سازی وابسته به داده گاهی شبکه مرتب سازی نامیده می شود. می توان آن را سخت­افزاری در نظر گرفت که فقط یک الگوریتم را اجرا می کند. المان سخت افزار اصلی المان مقایسه و معاوضه است که دو ورودی و دو خروجی دارد. برای دو ورودی x, y خروجی ها عبارتند از max (x, y) و min (x, y).

در ادامه الگوریتم مرتب سازی بایتونیک (Bitonic) را به عنوان مثالی از شبکه مرتب سازی بررسی می کنیم.

8.1.3. پیچیدگی موازی

در بالا گفتیم که مرتب سازی به صورت متوالی حداقل به زمان O (N log N) نیاز دارد. اگر با استفاده از P=N پردازشگر، افزایش سرعت خیلی خوب داشته باشیم، زمان موازی O (log N) را خواهیم داشت. اگر زمان موازی بیش از این باشد، پیچیدگی موازی را مجموع تعداد عمل تعریف می کنیم. برای مثال، در ادامه مرتب سازی ترانهادن فرد – زوج را خواهیم دید، که N مرحله طول می کشد و با پیچیدگی N² است، و م رتب سازی بایتونیک را بررسی می کنیم که زمان موازی (log N)²  نیاز دارد و با پیچیدگی توالی N (log N)² است.

8.2. مرتب سازی ترانهادن فرد – زوج

الگوریتم مرتب سازی ترانهادن فرد – زوج الگوریتمی ساده است و مزیت اصلی آن این است که به راحتی در حوزه خطی پردازشگر پیاده می شود. یک مرحله از الگوریتم شامل دو زیرمرحله است:

• هر پردازشگر  با شماره روج با همسایه سمت راست خود مقایسه و معاوضه انجام می دهد؛ سپس
• هر پردازشگر با شماره فرد با همسایه سمت راست خود مقایسه و معاوضه انجام می دهد.

قضیه 1. بعد از N مرحله، هر یک شامل دو زیر مرحله،  یک توالی مرتب می شود.

با زمان موازی 2N، این مرتب سازی توالی با پیچیدگی O (N²) می دهد.

8.3. مرتب سازی سریع

مرتب سازی سریع (Quicksort) الگوریتم بازگشتی است که برخلاف مرتب سازی حبابی، قطعی نیست. این الگوریتم فرآیندی دو مرحله ای براساس مرتب سازی مجدد دوباره توالی است:

الگوریتم: مرتب کردن آرایه پرچم ملی هلند

ورودی: آرایه ای از المان ها، مقدار "محور"

برای ثبت سفارش ترجمه تخصصی کلیک کنید

خروجی: آرایه ورودی با المان هایی که به صورت قرمز – سفید – آبی مرتب شده اند که در آن المان های قرمز بزرگتر از محور است، المان های سفید برابر با محور است، المان های آبی کمتر از محور است.

بدون اثبات می گوییم که می توان این الگوریتم را در O (n) عمل انجام داد. با این کار، مرتب سازی سریع به این شکل خواهد بود.

الگوریتم: مرتب سازی سریع

ورودی: آرایه ای از المان ها

خروجی: آرایه ورودی مرتب شده

در حالیکه آرایه بلندتر از یک المان است

مقدار دلخواه به عنوان محور انتخاب کنید

مرتب سازی پرچم ملی هلند را برای این ارایه بکار برید

مرتب سازی سریع (المان های آبی)

مرتب سازی سریع (المان های قرمز)

قطعی نبودن این الگوریتم، و تغییر در پیچیدگی از انتخاب محور ریشه می گیرد. در بدترین مورد، محور همیشه کوچکترین عنصر (منحصر) آرایه است. بنابراین المان آبی وجود نخواهد د اشت، تنها المان سفید محور است، و فراخوانی بازگشتی در آرایه­ای از n – 1 المان قرمز خواهد بود. به راحتی می توان دید که زمان اجرا O (n²) است. از سوی دیگر، اگر محور همیشه (نزدیک به) میان شماره (میانه) باشد، یعنی المانی که اندازه متوسط دارد، در اینصورت فراخوانی های بازگشتی زمان اجرای برابری خواند داشت، و فرمول بازگشتی زمان اجرا عبارت است از:

T_n=2T_n/2+O(n)

که (بازهم بدون اثبات) O (n log n) است.

حالا اجرای موازی مرتب سازی سریع را بررسی می کنیم.

8.3.1. مرتب سازی سریع در حافظه مشترک

موازی سازی الگوریتم سریع را می توان با اجرای دو فراخوانی بازگشتی به صورت موازی انجام داد. این کار با مدل حافظه مشترک و تردهای فراخوانی بازگشتی (بخش 2.6.1) بهتر قابل درک است. با این حال، پیاده سازی موثر و کارآمد نیست.

در آرایه ای به طور n، و با انتخاب خوب محور، n ترد فعال در مرحله نهایی الگوریتم وجود خواهد داشت. می خواهیم الگوریتم موازی در زمان O (logn) اجرا شود، اما در اینجا زمان تحت تاثیر ثبت اولیه آرایه بوسیله ترد اول قرار دارد.

تمرین 8.1. این بحث را دقیق تر بررسی کنید. مجموع زمان اجرا، افزایش سرعت، و راندمان موازی سازی الگوریتم مرتب سازیس سریع به این صورت چقدر است؟

آیا راهی برای تقسیم موثر آرایه وجود دارد؟ بله وجود دارد و کلید اینکار استفاده از عمل پیشوند موازی است؛ رجوع کنید به 23. اگر آرایه مقادیر x₁, . . ., x_n باشد، پیشوند موازی بکار می بریم تا محاسبه کنیم چند المان کمتر از محور π است:

X_i= ≠{x_j:j<i ∧ x_j<π

براین اساس، اگر پردازشگری به x_i نگاه کند، و x_i کمتر از محور باشد، باید به محل X_i + 1 در آرایه ای منتقل شود که المان ها بر طبق محور تقسیم می شود. همین طور می توان فهمید چند المان در محور وجود دارد و آنها را براین اساس جابجا کرد.

این نشان می دهد که هر مرحله محور بندی را می توان در زمان O(logn)² انجام داد، و چون log n مرحله برای الگوریتم مرتب سازی وجود دارد، کل الگوریتم در زمان O (log n)² اجرا می شود.

8.3.2. مرتب سازی سریع در فرامکعب ها

به طوریکه از روی بخش قبل روشن است، برای موازی سازی موثر الگوریتم مرتب سازی سریع، باید مرتب سازی مجدد پرچم ملی هلند را نیز موازی کنیم. بنابراین فرض می کنیم که آرایه در p پردازشگر فرا مکعب بعد d (یعنی p=2^d) تقسیم شده است.

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

برای اینکه المان های قرمز را در این سطح اول گرد آوریم، هر پردازشگر با پردازشگری موازی می شود که آدرس باینری دارد که در همه بیت ها به جز مهم ترین بیت یکسان هستند. در هر جفت المان­های آ بی به پردازشگری فرستاده می شود که در آن بیت مقدار 1 را دارد؛ المان های قرمز به پردازشگری فرستاده می شود که مقدار 0 در آن بیت دارد.

بعد از این مبادله (که محلی است و در نتیجه کاملا موازی است)، پردازشگرهای با آدرس 1xxxxx همه المان های قرمز را دارد، و پردازشگرهای با آدرس 0xxxxx همه المان های آبی را دارد. حالا مراحل قبل در فرامکعب ها تکرار می شود.

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

8.3.3. مرتب سازی سریع  در پردازشگر موازی کلی

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

مرتب سازی سریع موازی آرایه (یا زیرآرایه در فراخوان بازگشتی) با ساخت درخت باینری در پردازشگرهای مرتب سازی آرایه شروع می شود. مقدار محور انتخاب می شود و در درخت پخش گسترده می شود. با استفاده از ساختار درختی تعداد المان ها در زیردرخت سمت راست و سمت چپ هر پردازشگر برابر با مقدار محور، کمتر یا بیشتر مقدار محور شمارش می شود.

با این اطلاعات، پردازشگر ریشه را می توان محاسبه کرد که در آن مناطق  قرمز / سفید / آبی در آن ذخیره خواهد شد. این اطلاعات به درخت ارسال می شود و هر زیر درخت مکان های هدف برای المان ها در زیردرخت خود را محاسبه می کند.

اگر رقابت شبکه صرفنظر کنیم، بازآرایی را می توان در یک بار انجام داد، زیرا هر پردازشگر در نهایت یک المان ارسال می کند. یعنی هر مرحله فقط به اندازه زمان جمع کردن تعداد المان آبی و قرمز در زیر درخت طول می کشد که O (log n) در سطح بالا، O (log n/2) در سطح بعدی، و غیره است. این امر موجب افزایش سرعت بسیار خوبی می شود.

برای ثبت سفارش ترجمه تخصصی کلیک کنید

8.4. مرتب سازی بایتونیک

برای بهبود مرتب سازی بایتونیک، فرض کنید توالی x = (x₀, . . ., x_n – 1) شامل قسمت صعودی و سپس قسمت نزولی است. حالا این توالی را به دو زیر توالی (زیر دنباله) با طول برابر تقسیم کنید که عبارت است از:

شکل 8.1. تقسیم توالی بایتونیک.

 

از روی تصویر به راحتی می توان دید که s₁, s₂ بازهم توالی با قسمت صعودی و نزولی هستند. بعلاوه، همه المان ها در s₁ کمتر از همه المان ها در s₂ است.

رابطه (8.1) را مرتب ساز بایتونیک صعودی می نامیم، زیرا توالی حاوی عناصری بزرگتر از از توالی اول است. همین طور می توان با حفظ نقش حداکثر و حداقل، مرتب ساز نزولی ساخت.

به راحتی می توان این را مرحله­ای از الگوریتم مرتب سازی عنوان کرد: که با توالی به این شکل شروع می شود، با استفاده مکرر از فرمول (8.1) توالی ( دنباله) مرتب بدست می­آید. شکل 8.2 چهار مرتب ساز بایتونیک را نشان می دهد که به ترتیب در فاصله 8، 4، 2، 1 توالی به طول 16 را مرتب می کنند.

تعریف واقعی مرتب ساز بایتونیک کمی پیچیده تر است. یک توالی در صورتی بایتونیک است که شامل قسمت صعودی (افزایشی) و سپس قسمت نزولی (کاهشی)، یا جایگشت چنین توالی باشد.

تمرین 8.2. اثبات کنید که تقسیم توالی بایتونیک طبق فرمول (8.1) دو زیرتوالی بایتونیک می دهد.

بنابراین پرسش این است که چگونه توالی بایتونیک بدست آوریم.  پاسخ استفاده از شبکه های بایتونیک بزرگتر و کوچکتر است.

• مرتب سازی بایتونیک دو المان توالی مرتب به شما می دهد.
• اگر دو توالی به طول دو داشته باشید که یکی به سمت بالا مرتب شده است و دیگری به سمت پایین مرتب شده باشد، توالی بایتونیک است.

شکل 8.2 تصویر شبکه بایتونیک که توالی بایتونیک به طول 16 را مرتب می کند.

• بنابراین این توالی به طول چهار را می توان در دو مرحله بایتونیک مرتب کرد.
• و دو توالی مرتب شده به طول چهار توالی بایتونیک با طولی را تشکیل می دهند که می توان در سه مرحله بایتونیک مرتب کرد؛ و غیره.

شکل 8.3. مرتب سازی بایتونیک کامل برای 16 المان.

از روی انی شکل می توان گفت که log2 N مرحله برای مرتب سازی N المان دارید که مرحله iام آن به طول log ₂ i است. این موجب می شود مجموع پیچیدگی توالی مرتب سازی بایتونیک (log₂ N)  باشد.

توالی عملیات در شکل 8.3 شبکه مرتب سازی نامیده می شود، که از المان­های مقایسه – و معاوضه ساخته شده است. وابستگی به مقدار المان های داده وجود ندارد، همانطور که در مرتب سازی سریع نیز چنین وابستگی وجود ندارد.

 

فصل 9

تحلیل گراف

مسائل مختلفی در محاسبات علمی را می توان به صورت مسائل گراف طرح کرد (برای مقدمه ای درباره تئوری گراف رجوع کنید به ضمیمه 20)؛ برای مثال، با مسئله توازن بار (بخش 2.10.1.3) و یافتن مجموعه های غیر وابسته ( بخش 6.9.2) مواجه شده اید.

الگوریتم های گراف زیادی برای این منظور قبل استفاده نیستند یا حداقل موثر نیستند، زیرا غالبا گراف ها توزیع شده هستند و تئوری گراف سنتی با فرض دانش عمومی درباره کل گراف است. بعلاوه، تئوری گراف اغلب با یافتن الگوریتم مطلوب مرتبط است که معمولا موازی نیست. بنابراین الگوریتم های گراف موازی خود یک حوزه تحقیقی محسوب می شوند.

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

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

9.1. الگوریتم های گراف سنتی

با بررسی چند الگوریتم گراف "کلاسیک" شروع می کنیم، و بررسی می کنیم که چگونه می توان آنها را به صورت موازی پیاده کرد. ارتباط بین گراف ها و ماتریس های اسپارس (رجوع کنید به ضمیمه 20) در اینجا خیلی مهم است: بسیاری از الگوریتم های گراف ساختار ضرب ماتریس – بردار دارند.

برای ثبت سفارش ترجمه تخصصی کلیک کنید

9.1.1. الگوریتم­های کوتاهترین مسیر

چندین نوع الگوریتم کوتاهترین مسیر وجود دارد. برای مثال، در الگوریتم کوتاهترین مسیر یک منبع به دنبال کوتاهترین مسیر از گرهی مشخص یه گرهی دیگر هستیم. در الگوریتم های کوتاهترین مسیر همه جفت ها می­خواهیم فاصله بین دو گره را پیدا کنیم. محاسبه مسیرهای واقعی بخشی از این الگوریتم­هاست؛ با این حال همیشه به راحتی می توان برخی اطلاعات را شامل کرد که بعداً بتوان مسیر را دوباره ساخت.

با الگوریتمی ساده شروع می کنم: یافتن کوتاهترین مسیرها با یک منبع در گراف بدون وزن. اینکار با جستجوی اولین عرض (Breadth – First) (BFS) راحت است:

ورودی: گراف، و گره شروع s

خروجی: تابع d(v) که فاصله از s تا v را اندازه می گیرد

S را معلوم بگیرید، و d(s) = 0 بگیرید

مجموعه نهایی را به صورت U = {s} وارد کنید

C = 1 بگیرید

while تمام نشده  do

V را همسایه های U بگیرید که خودشان در U نیستند

اگر V = Ø باشد دراینصورت (then)

کار تمام شده

در غیراینصورت (else)

d(v) = c + 1 برای هر v ϵ V بگیرید.

U ⟵U ∪V 

c ← c + 1 را افزایش دهید

اینگونه طرح الگوریتم برای اهداف نظری مفید است: معمولا می توانید گزاره­ای را طرح کنید که برای هر تکرار حلقه while صدق کند. این طرح امکان اثبات خاتمه الگوریتم و اینکه الگوریتم چیزی را که شما می خواهید، محاسبه می کند، فراهم می کند. با این حال، این روزها گراف هایی مثل فیس بوک ممکن است خیلی عظیم باشند و بخواهید الگوریتم گراف را موازی برنامه نویسی کنید.

در اینصورت فرمول های سنتی جواب نمی دهد:

• این فرمول ها براساس صف­هایی است که گره ها به آنها افزوده یا از آنها کم می شود؛ یعنی شکلی از حافظه مشترک وجود دارد.
• بدون توجه به این که با نوع مکان فضایی مطابقت می کند یا نه دستورات برای گره ها و همسایه ها ایجاد می شود.

حالا نشان می دهیم که الگوریتم های گراف را می توان الگوریتم های ماتریس اسپارس در نظر گرفت، یعنی می توان همه مفاهیم و تحلیلی را که برای آنها ارائه کردیم، بکار بست.   

اگر G ماتریس مجاورت گراف باشد، می توان الگوریتم کوتاهترین مسیر را شبیه به یک سری ضرب ماتریس – بردار طرح کرد (رجوع کنید به بخش 20.4.4). x را برداری بگیرید که فاصله از منبع را نشان می دهد، یعنی x_i فاصله گره i از منبع است. برای هر همسایه j برای i، فاصله تا منبع عبارت است از x_i + G_ij، مگر اینکه کوتاهترین فاصله از قبل معلوم باشد. به عبارت دیگر می توان ضرب را ا ینگونه تعریف کرد:

و تکرارهای بالای حلقه while معادل است با ضرب بعدی ماتریس – بردار براساس این تعریف.

این الگوریتم جواب می دهد زیرا می توان d(v) را مقدار نهایی اولین باری که آن را ملاقات کردیم، گرفت؛ این دقیقا بعد از اینکه تعداد تکرارها برابر با طول مسیر شد، روی می دهد. مجموع تعداد اجراهای حلقه داخلی برابر است با تعداد لبه ها در گراف. گراف وزن­دار تا حدودی مستلزم دقت زیاد است، ز یرا ممکن است مسیر با مراحل بیشتر کوتاهتر از میزان اندازه گیری شده با مجموع وزن مراحل باشد. الگوریتم بلمن – فورد (bellman-Ford):

این الگوریتم درست است زیرا برای گره مشخص u، بعد از k مرحله تکرار بیرونی، همه مراحل مورد نظر مسیر s→u را دارد.

تمرین 9.1. پیچیدگی این الگوریتم چیست؟ آیا طول حلقه بیرونی را می توان با داشتن اطلاعاتی از گراف کاهش داد؟

می توان این مسئله را به صورت یک سری ضرب ماتریس – بردار نوشت، اگر ضرب را به اینصورت تعریف کنیم:

در واقع اساس این ضرب همانند بالاست: حداقل فاصله تا j حداقل فاصله ای است که قبلا محاسبه شده است یا حداقل فاصله تا هر گره i به اضافه گذار g_ij است.

9.1.2. موازی سازی

الگوریتم های گراف در فرمول سنتی را می توان موازی سازی کرد. معمولا مراحل بزرگ بیشتری وجود دارد که متوالی هستند، اما تعداد متغیرها در آنها مستقل از هم در نظر گرفته می شود. بنابراین موازی سازی می توان انجام داد.

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

با توجه این دلایل، فرمول جبر خطی می تواند مورد ترجیح باشد. قطعاً با در نظر گرفتن حافظه توزیع شده به این روش نیاز داریم، اما حتی در معماری های چند هسته ای این روش می تواند در تشویق موقعیت جواب دهد. در نتیجه تقسیم بندی را با یکی از متغیرهای مسئله در نظر می گیریم. این تنها استراتژی است که برای الگوریتم­های کوتاهترین مسیر منبع منطقی به نظر می رسد.

تمرین 9.2. آیا می توان آرگومانی قیاسی ایجاد کرد که مبنای موازی سازی توزیع در بردار باشد؟  چقدر داده در این عمل دخیل است، چقدر کار لازم است و چند مرحله متوالی را دربرمی گیرد؟

9.1.3. کوتاهترین مسیر همه جفت های فلوید – وارشال

الگوریتم فلوید- وارشال نمونه ای از الگوریتم های کوتاهترین مسیرهای همه جفت هاست. این الگوریتم برنامه نویسی پویا است که براساس افزایش تدریجی مجموعه گره های واسطه این مسیر است. بویژه در مرحله k، همه مسیرهای u ⇝v با گره های واسطه در مجموعه k = {0, . . ., k-1} در نظر گرفته می شود و ∆_k(u, v) طول مسیر از u تا v تعریف می شود که در آن همه گره ها در k هستند. در ابتدا، این یعنی فقط لبه های گراف در نظر گرفته می شود، وقتی k = |V| باشد همه مسیرهای ممکن در نظر گرفته شده است و کارمان تمام می شود.

مرحله محاسبه عبارت است از

یعنی برآورد kام از فاصله ∆(u, v) حداقل مسیر قبلی است و با در نظر گرفتن گره k مسیر جدیدی ممکن می شود. این مسیر آخر با الحاق مسیر u⇝k و k⇝v پیدا می شود.

به عبارت الگوریتمی داریم:

می توان دید که این الگوریتم ساختاری شبیه به حذف گاوسی دارد، به جز اینکه حلقه داخلی برای همه u,v>k’ خواهد بود.

از نظر جبری:

الگوریتم فلوید – وارشال مسیر واقعی را به شما نمی­گوید. ذخیره این مسیرها در حین محاسبه فاصله پرهزینه است، هم از نظر زمان و هم از نظر حافظه. راه حلی مشابه امکان پذیر است: ماتریس دوم n (i, j) را ذخیره می­کنیم که بیشترین تعداد گره در مسیر بین i و j دارد.

تمرین 9.3. محاسبه n(i, j) را در الگوریتم فلوید – وارشال شامل کنید و توضیح دهید با معلوم بودن d(. , .) و n (. , .)، چگونه از این الگوریتم برای یافتن کوتاهترین مسیر بین i و j استفاده کنیم.

موازی سازی: در الگوریتم کوتاهترین مسیر تک منبع بالا گزینه زیادی نداشتیم جز اینکه با توزیع بردار به جای ماتریس موازی سازی کنیم. این نوع توزیع در اینجا هم امکان پذیر است، و معادل است با توزیع تک بُعدی مقادیر D (. , .).

تمرین 9.4. پیاده سازی این الگوریتم را رسم کنید. نشان دهید که هر تکرار kام پخش گسترده با پردازشگر k را به عنوان ریشه دربرمی­گیرد.

با این حال، این روش منجر به همان مسائل مقیاس­پذیری در ضرب ماتریس – بردار با استفاده از توزیع تک بعدی ماتریس می شود؛ رجوع کنید به بخش 6.2.2. بنابراین باید از توزیع دو بعدی استفاده کنیم.

برای ثبت سفارش ترجمه تخصصی کلیک کنید

تمرین 9.5. تحلیل مقیاس­گذاری را انجام دهید. در سناریوی مقیاس گذاری ضعیف با حافظه ثابت، راندمان مجانبی چیست؟

تمرین 9.6. الگوریتم فلوید – وارشال  را با استفاده از توزیع دو بعدی مقادیر D (. , .)  رسم کنید.

تمرین 9.7. الگوریتم فلوید – وارشال عملیاتی کاملا مشابه در صفرها، و مطمئناً در مراحل اول انجام می­دهد. آیا می توانید الگوریتمی طراحی کنید که با اجتناب از اینها باشد؟

9.1.4. درختان پوشا

در گراف بدون جهت G= <V, B>، T⊂E را در صورتی درخت می نامیم که همبسته غیرچرخه ای باشد. هم چنین درصورتی درخت پوشا نامیده می شود که لبه های آن همه رئوس را داشته باشد. اگر وزن لبه گراف  w_i:i ∈E داشته باشد، وزن درخت _{e ∈T}w_e است، و در صورتی درخت را درخت حداقل پوشا می نامیم که وزن آن حداقل باشد. لزومی ندارد درخت پوشای حداقل منحصر به فرد باشد.

الگوریتم پریم، گونه کمین الگوریتم کوتاهترین مسیر دایجسترا (Dijkstra)، درخت پوشا را که از ریشه شروع می شود، محاسبه می کند. طول مسیر ریشه صفر است، و همه گره های دیگر بی نهایت است. در هر مرحله همه گره های متصل به گره های معلوم درخت در نظر گرفته می شود و طول بهترین مسیر معلوم به روز می شود.

قضیه 2. الگوریتم بالا کوتاهترین فاصله از هر گره تا گره ریشه را محاسبه می کند.

اثبات. کلید درستی این الگوریتم این است که ما u را با مقدار کمین l(u) انتخاب می کنیم. طول کوتاهترین مسیر درست  تا بردار را L (v) بنامید. از آنجا که با مقدار l بی نهایت شروع می کنیم و همواره آن را کاهش می دهیم، همیشه داریم L v≤l(v).

فرضیه ما این است که در هر مرحله از الگوریتم، برای گره های در T فعلی، طول مسیر درست تعیین می شود:

مطمئناَ این زمانی درست است که درخت فقط شامل ریشه s باشد. حالا باید مرحله القاء را محاسبه کنیم: اگر برای همه گره های در درخت فعلی طول مسیر درست باشد، در اینصورت داریم L(u) = l(u).

فرض کنید این درست نیست، و مسیر دیگری کوتاهتر است. این مسیر باید از گره y بگذرد که در حال حاضر در T نیست؛ این وضعیت در شکل 9.1 نشان داده شده است. x را گرهی در T در کوتاهترین مسیر جایگشتی درست قبل از y بگیرید. حالا داریم l(u) > L (u) زیرا هنوز طول درست را نداریم، و L (u) > L (x) + w_xy زیرا حداقل یک لبه (که وزن مثبت دارد) بین y و u وجود دارد. حالا مشاهده می کنیم که وقتی x به T اضافه شد، همسایه های آن به روز شد، بنابراین l(y) عبارت است از l_x + w_xy یا کمتر. با جمع بندی این نامعادلات د اریم:

که با این واقعیت در تناقض است که ما u را طوری انتخاب می کنیم که مقدار کمین l را داشته باشیم.

شکل 9.1: درستی الگوریتم دایجسترا.

برای موازی سازی این الگوریتم مشاهده می کنیم که حلقه داخلی غیروابسته است و در نتیجه به راحتی موازی می شود. اما حلقه بیرونی گزینه­ای  دارد که مقدار تابع را به حداقل می رساند. محاسبه این گزینه عملگر کاهش است، و در نتیجه باید پخش گسترده شود. این استراتژی زمان ترتیبی را برابر با d log P می­سازد که در آن d عمق درخت پوشا است.

در یک پردازشگر، یافتن مقدار حداقل آرایه تقریبا عمل O (N) است، اما با استفاده از صف الویت می­توان این مقدار را به O (log N) کاهش داد. برای نسخه موازی الگوریتم درخت پوشا، عبارت معادل O(log (N/P)) است، که هزینه کاهش O (log P) را شامل نمی شود.