چطور سریع ترین مسیر را پیدا کنیم؟ در این مقاله می خواهیم یک الگوریتم مسیریابی، برای خطوط مترو بنویسیم. فرض میکنیم که فاصله هر ایستگاه، با ایستگاه بعدی یکسان است، حالا میخواهیم که الگوریتمی بنویسیم که ایستگاه مبدا و مقصد را به آن بدهیم و نزدیک ترین مسیر بین این دو ایستگاه را به ما دهد. منظورمان از نزدیک ترین مسیر، مسیری است که کمترین تعداد ایستگاه را داشته باشد. برای اینکه این الگوریتم را بنویسیم، اول باید با یک ساختار داده بسیار مهم و کاربردی، آشنا شویم؛ گراف!
گراف چیست؟
گراف، یک نوع ساختار داده است که برای نشان دادن ارتباطات بین داده ها استفاده میشود، هر گراف از تعدادی راس و تعدادی یال تشکیل میشود. راس که به آن گره هم گفته میشود، نقطه هایی هستند که در گراف نشان دهنده اشیاء هستند و یال به خطوطی گفته میشود که این نقاط را به یکدیگر متصل میکند.
در چه مواردی از گراف استفاده میکنیم؟
به طور کلی ما در هرجایی که بخواهیم ارتباط بین اشیاء را نشان دهیم از گراف استفاده میکنیم، برای مثال در شبکه های اجتماعی برای نشان دادن ارتباط بین افراد از گراف استفاده میشود، یا در یک نقشه برای نشان دادن مسیر های بین شهر ها. ما میخواهیم یک الگوریتم مسیریابی، برای خطوط مترو بنویسیم و برای نگه داشتن اطلاعات ایستگاه ها و ارتباط آن ها از گراف استفاده میکنیم.
الگوریتم جستجوی سطح اول (BFS) چیست؟
الگوریتم جستجوی سطح اول، یک الگوریتم است که برای پیدا کردن کوتاه ترین مسیر بین دو راس در یک گراف استفاده میشود. این الگوریتم، از راسی که به عنوان مبدا در نظر گرفتیم شروع میکند و تمام رئوس را به ترتیب نزدیک بودن بررسی میکند تا زمانی به مقصد برسد و با این روش کوتاه ترین مسیر را محاسبه میکند.
جستجوی سطح اول چطور کار میکند؟
الگوریتم جستجوی سطح اول، بسیار ساده است، برای پیاده سازی این الگوریتم ما نیاز به یک صف داریم. صف یک نوع ساختار داده است که کاملا مشابه همان مفهومی است که در دنیای واقعی دارد، داده ها یکی یکی، وارد صف میشوند و به همان ترتیبی که وارد شدند خارج میشوند.
برای پیاده سازی این الگوریتم، ما نیاز به یک صف داریم که در شروع کار فقط راس مبدا را در آن قرار میدهیم، سپس سه مرحله زیر را مدام تکرار میکنیم تا به مقصد برسیم.
- اولین داده را، از صف بردار.
- آیا به مقصد رسیدیم؟
- اگر به مقصد نرسیدیم، همه راس های مجاور این راس را که قبلا بررسی نشده در صف قرار بده.
این سه مرحله تا جایی تکرار میشود که به مقصد برسیم.
مثالی برای درک بهتر
فرض کنیم ما میخواهیم با استفاده از مترو تهران، از ایستگاه شهید بهشتی به ایستگاه میدان ولیعصر برویم و میخواهیم از الگوریتم جستجوی سطح اول برای مسیریابی استفاده کنیم. ابتدا ایستگاه شهید بهشتی را در صف قرار میدهیم و شروع میکنیم به انجام مراحل.
- اولین داده را، از صف بردار : اولین داده ای که در صف قرار دارد، همان ایستگاه شهید بهشتی است.
- آیا به مقصد رسیده ایم؟ : مقصد ما، ایستگاه میدان ولیعصر بود، پس فعلا باید ادامه بدهیم.
- همه راس های مجاور را در صف قرار بده : چهار ایستگاه در همسایگی ایستگاه شهید بهشتی وجود دارد و ما باید این چهار ایستگاه را در صف قرار دهیم. صف جدید به این صورت خواهد بود [مصلی امام خمینی، میرزای شیرازی، شهید مفتح، سهروردی]
همین فرایند را باید تکرار کنیم تا جایی که به ایستگاه مقصد برسیم، اما باید دقت داشته باشیم که ایستگاه های تکراری را به صف اضافه نکنیم، برای مثال زمانی که ما ایستگاه مصلی را بررسی میکنیم و به مرحله سوم میرسیم، باید همسایه های ایستگاه مصلی را به صف اضافه کنیم اما باید دقت داشته باشیم که ایستگاه بهشتی را مجددا به صف اضافه نکنیم چون قبلا یک بار بررسی شده است. برای جلوگیری از این اشتباه، باید ایستگاه های بررسی شده را در یک آرایه ذخیره کنیم.
دو نکته قابل توجه
جستجوی سطح اول، ففط با این فرض درست کار میکند که فاصله همه ایستگاه ها، با هم برابر باشد. به عبارتی فقط برای گراف های هم وزن کار میکند، برای مسیریابی در گراف غیر هم وزن باید از الگوریتم دیگری استفاده کنیم که در مقالات بعدی با آن آشنا خواهیم شد.
نکته دیگری که باید درباره الگوریتم جستجوی سطح اول بدانیم، این است که برای گراف های بزرگ، عملکرد خوبی ندارد، به دلیل اینکه ما باید تمام رئوس گراف را ذخیره کنیم و این ممکن است باعث پر شدن حافظه بشود.
جمع بندی
در ابتدای این مقاله با مفهوم گراف، آشنا شدیم که یکی از پر کاربرد ترین ساختار های داده است و به طور خاص برای نشان دادن ارتباطات بین داده ها استفاده میشود، و همچنین با الگوریتم جستجوی سطح اول، آشنا شدیم و یاد گرفتیم که چطور کار میکند و چه کاربرد هایی دارد. جستجوی سطح اول در مواردی غیر از مسیریابی هم استفاده میشود، برای مثال برای پیدا کردن یک داده در یک شبکه.
اگر این مطلب برایتان مفید بود، پیشنهاد میکنم سری مقالات الگوریتم و ساختمان داده را دنبال کنید.
خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.
