الگوریتم کوتاه ترین مسیر دایجسترا در سوئیفت — به زبان ساده

۶۸۶ بازدید
آخرین به‌روزرسانی: ۰۱ مهر ۱۴۰۲
زمان مطالعه: ۴ دقیقه
الگوریتم کوتاه ترین مسیر دایجسترا در سوئیفت — به زبان ساده

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

997696

ایجاد اتصال

چالش ما با گراف‌ها این است که باید شیوه ارتباط با دیگر شیءها را بدانیم. برای نمونه وب‌سایت شبکه اجتماعی LinkedIn را در نظر بگیرید. در LinkedIn هر پروفایل را می‌توان به عنوان یک رأس منفرد تصور کرد که می‌تواند به رئوس دیگر وصل شود. یک قابلیت LinkedIn توانایی معرفی خود به افراد دیگر است. در این سناریو، LinkedIn امکان مسیریابی پیام را از طریق اتصال مشترک فراهم می‌سازد.

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

کوتاه ترین مسیر دایجسترا در سوئیفت
کوتاه‌ترین مسیر از A به C از B می‌گذرد.

یافتن روش

کوتاه‌ترین مسیر می‌تواند به عنوان سرویس‌های مبتنی بر نقشه مانند Google Maps نیز نگریسته شود. کاربران به طور مکرر از Google Maps برای یافتن مسیر راندگی بین دو نقطه استفاده می‌کنند، چنان که می‌دانیم در اغلب موارد چند راه برای رسیدن به هر مقصد وجود دارد. کوتاه‌ترین مسیر در اغلب موارد به عوامل مختلفی مانند ترافیک، شرایط جاده، تصادف‌ها و زمان روز بستگی دارد. در نظریه گراف این عوامل خارجی نماینده وزن یال هستند.

کوتاه ترین مسیر دایجسترا در سوئیفت
کوتاه‌ترین مسیر از A به C از A می‌گذرد.

این مثال برخی نکات کلیدی مربوط به الگوریتم دایجسترا را نشان می‌دهد. علاوه بر این راه‌های چندگانه برای رفتن از A به C، کوتاه‌ترین مسیر از طریق B تصور می‌شود. تنها زمانی که از طریق B به نقطه C برسیم می‌توانیم تفسیر خود را از کوتاه‌ترین مسیر و تغییر جهت مورد تعدیل قرار دهیم. این تغییر در جهت به نام «رویکرد حریصانه» (greedy approach) خوانده می‌شود و برای مسائل مشابهی مانند «فروشنده دوره‌گرد» مورد استفاده قرار می‌گیرد.

معرفی الگوریتم دایجسترا

الگوریتم دایجسترا در سال 1959 معرفی شده و برای یافتن کوتاه‌ترین مسیر بین دو رأس در یک گراف جهت‌دار بدون وزن‌های یال غیر منفی مورد استفاده قرار می‌گیرد. در ادامه شیوه پیاده‌سازی آن را در سوئیفت مورد بررسی قرار می‌دهیم.

کوتاه ترین مسیر دایجسترا در سوئیفت

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

کوتاه ترین مسیر دایجسترا در سوئیفت

استفاده از مسیرها

در این سفر ما هر گرهی را که در یک ساختمان داده سفارشی بازدید می‌کنیم، مسیر می‌نامیم. مجموع نهایی از تجمیع وزن یال‌هایی که برای رسیدن به مقصد مشخص طی می‌شوند به دست می‌آید. مشخصه previous مسیر انتخابی برای رسیدن به رأس را نمایش خواهد داد:

1//the path class maintains objects that comprise the "frontier"
2class Path {
3    
4    var total: Int
5    var destination: Vertex
6    var previous: Path?
7//object initialization
8    init(){
9        destination = Vertex()
10        total = 0
11    }    
12}

تجزیه دایجسترا

اینک که همه مؤلفه‌های گراف در جای خود هستند، به بررسی الگوریتم دایجسترا می‌پردازیم. متد processDijkstra رئوس مبدأ و مقصد را به عنوان پارامتر می‌گیرد. همچنین یک مسیر (path) بازگشت می‌دهد. از آنجا که ممکن است مکان یافتن یک مقصد وجود نداشته باشد، مقدار بازگشتی به در سوئیفت به صورت optimal اعلان می‌شود:

1//Dijkstra’s shortest path algorithm
2func processDijkstra(source: Vertex, destination: Vertex) -> Path? {
3...
4}

ساخت frontier

چنان که قبلاً گفتیم، کلید درک الگوریتم دایجسترا دانستن شیوه پیمایش گراف است. برای کمک به درک آن چند قاعده و یک مفهوم جدید به نام frontier را معرفی می‌کنیم:

1        var frontier = Array<Path>()
2        var finalPaths = Array<Path>()
3          
4        //use source edges to create the frontier
5        for e in source.neighbors {
6            
7            let newPath: Path = Path()
8         
9          newPath.destination = e.neighbor
10            newPath.previous = nil
11            newPath.total = e.weight
12            
13            //add the new path to the frontier
14            frontier.append(newPath)
15            
16        }

الگوریتم با بررسی رأس مبدأ و تکرار روی لیستی از همسایگی‌ها آغاز می‌شود. می‌دانیم که هر همسایه نماینده یک یال است. در هر تکرار اطلاعاتی در مورد یال همسایه برای ساخت مسیر جدید مورد استفاده قرار می‌گیرد. در نهایت هر مسیر به frontier اضافه می‌شود:

کوتاه ترین مسیر دایجسترا در سوئیفت
بصری‌سازی frontier به صورت یک لیست
1...
2//construct the best path
3var bestPath: Path = Path()        
4        
5while frontier.count != 0 {
6            
7  //support path changes using the greedy approach
8  bestPath = Path()
9  var pathIndex: Int = 0
10    for x in 0..<frontier.count {
11               
12      let itemPath: Path = frontier[x]
13                
14         if (bestPath.total == 0) || (itemPath.total < bestPath.total) {
15            bestPath = itemPath
16            pathIndex = x
17         }
18                
19   }
20...

چنان که می‌بینید از bestPath برای ساخت یک سری از مسیرها استفاده کرده‌ایم. همچنین سابقه بازدیدهای خود را در مورد هر شیء جدید حفظ می‌کنیم. زمانی که این بخش کامل شد، به بررسی تغییرات frontier می‌پردازیم:

کوتاه ترین مسیر دایجسترا در سوئیفت
frontier پس از بازدید از دو رأس دیگر

در این مرحله در مورد گراف دانش بیشتری کسب کردیم. اکنون دو مسیر احتمالی دیگر به رأس D وجود دارد. به این ترتیب کوتاه‌ترین مسیر برای رسیدن به رأس D نیز تغییر یافته است. در نهایت مسیری که از A-B می‌گذرد حذف و به ساختار جدیدی که finalPaths نام دارد اضافه می‌شود.

یک مبدأ منفرد

الگوریتم Dijkstra را می‌توان به صورت «مبدأ منفرد» توصیف کرد، زیرا مسیر را به هر رأس محاسبه می‌کند. در مثالمان این اطلاعات را در آرایه finalPaths حفظ می‌کنیم.

کوتاه ترین مسیر دایجسترا در سوئیفت
finalPaths زمانی که frontier به صفر می‌رسد. چنان که می‌بینید همه جایگشت‌ها از رأس A محاسبه شده‌اند.

بر اساس این داده‌ها می‌توانیم ببینیم که کوتاه‌ترین مسیر به رأس E از A مسیر A-D-E است. مزیت افزوده آن این است که علاوه بر به دست آوردن این اطلاعات برای یک مسیر مبدأ، کوتاه‌ترین مسیر برای هر گره در گراف را نیز محاسبه کرده‌ایم.

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

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای ۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
swift-algorithms-data-structures
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *