مسیریابی (الگوریتم)
مسیر یابی یک الگوریتم برای برنامه‌های کامپیوتری است که هدف آن یافتن (غالبا) کوتاه‌ترین مسیر بین دو نقطه است. مسیر یابی یک راه کاربردی برای حل هزارتو‌ها است.
مسیر یابی به مقدار زیادی به مسئلهٔ کوتاه‌ترین مسیر در نظریهٔ گراف‌ها ارتباط دارد؛ که در واقع این مسئله به این موضوع می‌پردازد که چگونه سریع‌ترین، ارزان‌ترین (از لحاظ تعداد راس‌ها) و کوتاه‌ترین مسیر را بین دو نقطه در یک شبکهٔ بزرگ بیابیم.
ردیابی تاریخچه مسئله مسیریابی و کوتاهترین مسیر دشوار است. می‌توان تصور کرد که حتی در جوامع بسیار بدوی (حتی حیوانات) نیز این کار بسیار ضروری بوده‌است (به عنوان مثال برای یافتن غذا). تحقیقات ریاضی دربارهٔ این مسئله نسبت به مسئله‌های معروف دیگر دیر شروع شد. از اولین الگوریتم‌هایی که برای این مسئله ارائه شد می‌توان به الگوریتم جستجوی اول سطح اشاره کرد.
با توجه به پیشرفت کامپیوترها و ظهور مسائل جدید، این مسئله به تدریج از اواسط قرن بیستم مورد توجه قرار گرفت و با ایجاد شبکهٔ جهانی اینترنت، بیش از پیش به آن پرداخته شد. بازی‌های کامپیوتری و نقشه‌های آنلاین، امروزه از پیشرفته‌ترین الگوریتم‌های مسیریابی استفاده می‌کنند.
مسیریابی عبارت است از پیدا کردن یک مسیر بین دو نقطه از فضا که ممکن است مابین آنها موانعی وجود داشته باشد. مسئلهٔ مسیریابی به دو زیرمسالهٔ زیر قابل تقسیم است:
در مرحلهٔ اول سعی بر این است که فضای پیوسته به فضایی گسسته نگاشته شود. به این ترتیب یک گراف formula_1 به وجود می‌آید که در آن formula_2 (مجموعهٔ رئوس گراف) نمایندهٔ نقاطی از فضای پیوسته و formula_3 (مجموعهٔ یالهای گراف) نمایندهٔ وجود یا عدم وجود ارتباط بدون واسطه بین دو نقطه از فضای پیوسته‌است.
این گراف در مرحلهٔ دوم به عنوان ورودی به یک الگوریتم مسیریابی داده می‌شود. خروجی این الگوریتم یک آرایه‌ی مرتب از راس‌ها است که برای رسیدن به راس هدف باید آن‌ها را به ترتیب و بدون واسطه طی کرد. الگوریتم‌های مسیریابی معمولاً علاوه بر این که می‌خواهند یک مسیر پیدا کنند، در پی مسیری هستند که بر اساس معیار خاصی (مثلا طول مسیر) بهینه باشد.
متد مسیریابی با شروع از یک راس و جستجو در راس‌های مجاور آن تا زمان رسیدن به راس مقصد، یک گراف را جستجو می‌کند؛ که معمولاً هدف آن یافتن سریع‌ترین مسیر است. در حقیقت هدف الگوریتم مسیر یابی عموماً یافتن مسیری با کمترین تعداد راس استفاده شده (در گراف‌های فاقد وزن)، یا کمترین جمع اوزان مشاهده شده (در گراف‌های وزن‌دار) است. به عنوان مثال می‌توان گفت که الگوریتم مد نظر، همانند شخصی است که قصد دارد از نقطه‌ای به نقطهٔ دیگری برسد؛ به جای این که این شخص تمام مسیرهای موجود را بررسی کند، در یک مسیر حرکت می‌کند و فقط زمانی از مسیر خود منحرف می‌شود که مانعی بر سر راه وی وجود داشته باشد.
دو نکته مهم در مسیر یابی که باید به آن توجه شود عبارت‌اند از:
الگوریتم‌های پایه ای مانند جستجوی اول سطح و جستجوی اول عمق مشکل اول را با بررسی تمام حالت‌های موجود بررسی می‌کنند. به این صورت که با گرفتن یک راس تمام مسیرهای موجود را جستجو می‌کنند تا به راس هدف برسند. از لحاظ مرتبه زمانی چنین الگوریتمی در زمان formula_4 طول می‌کشد که formula_2 تعداد راس‌ها و formula_3 تعداد یال‌ها است.
اما مسئلهٔ پیچیده‌تر یافتن مسیر بهینه است. راه‌حل کلی در این موارد استفاده از الگوریتم بلمن-فورد است که پیچیدگی زمانی آن formula_7 می‌باشد. الگوریتم‌هایی مانند Dijkstra و formula_8 به صورت استراتژیک مسیرها را خرد می‌کنند.
"مقالهٔ اصلی: الگوریتم جستجوی اول عمق"
الگوریتم جستجوی اول عمق یک روش ساده و در عین حال کارا برای مسیریابی است که در سال ۱۸۸۲ توسط ریاضی‌دان فرانسوی، چارلز پیر ترما به منظور حل هزارتوها پیشنهاد شد. این الگوریتم بر پایهٔ روش پس‌گرد استوار است.
در این روش یکی از همسایه‌های گره شروع به صورت دلخواه انتخاب می‌شود. اگر این گره همسایه‌ای داشته باشد که تا آن لحظه بازدید نشده باشد، الگوریتم به آن همسایه می‌رود (اگر چند همسایه با این شرایط وجود داشته باشد یکی به دلخواه انتخاب می‌شود). این روند آنقدر ادامه پیدا می‌کند تا یکی از دو اتفاق زیر بیفتد:
الگوریتم جستجوی اول عمق با وجود سادگی، پایهٔ بسیاری از الگوریتم‌های مهم در نظریهٔ گراف است.
این الگوریتم را می‌توان به صورت تابع بازگشتی زیر در پایتون پیاده‌سازی کرد: def depth_first_search(graph, start, visited=None): "مقالهٔ اصلی: الگوریتم جستجوی اول سطح"این روش نخستین بار در سال ۱۹۵۹ توسط ادوارد مور برای یافتن کوتاه‌ترین مسیر در یک هزارتو معرفی شد. با استفاده از این الگوریتم می‌توان کوتاه‌ترین مسیر بین دو راس از یک گراف غیر وزن دار را پیدا کرد.
در این روش که با استفاده از داده ساختار صف پیاده‌سازی می‌شود، قسمتی از گراف به عنوان جلودار (frontier) در نظر گرفته می‌شود. این قسمت از نقطهٔ شروع آغاز به گسترش می‌نماید و بسته به کاربرد می‌تواند تا دربرگرفتن تمام گراف یا تا حدی که نقطهٔ پایان مسیر را شامل شود گسترش یابد. در صورت پیمایش تمام گراف، می‌توان مسیر بهینه را از نقطهٔ شروع تا هر نقطهٔ دلخواه دیگر را پیدا کرد.
این الگوریتم از یک حلقهٔ تکرار با دو گام زیر تشکیل می‌شود و تا خالی شدن جلودار ادامه می‌یابد:
با اجرای این حلقه مولفهٔ همبند گراف که شامل راس شروع است پیمایش می‌شود. برای ذخیرهٔ مسیر از راس شروع تا هر راس دلخواه، باید حین اضافه کردن همسایه‌ها به جلودار، در جدولی نام راسی که همسایه‌ها از آن منشأ گرفته‌اند را نوشت. به این ترتیب پس از رسیدن به راس دلخواه (پایانی) می‌توان به صورت بازگشتی مسیری به سمت راس شروع پیدا کرد.
شبه کد الگوریتم به قرار زیر است. frontier = Queue() frontier.put(start ) visited[start] = True
while not frontier.empty(): "مقالهٔ اصلی: الگوریتم دایکسترا"
الگوریتم Dijkstra برای یافتن کوتاهترین مسیر بین گره‌ها در یک گراف مورد استفاده قرار می‌گیرد. این الگوریتم به عنوان مثال، در شبکه‌های جاده‌ای کاربرد زیادی دارد. این الگوریتم توسط ادسخر دایکسترا در سال ۱۹۵۶ پیشنهاد شد.
این الگوریتم انواع مختلفی دارد. الگوریتم اصلی دایکسترا کوتاه‌ترین مسیر را بین دو گره معین پیدا می‌کرد، اما یک نوع رایج‌تر این الگوریتم یک گره منفرد را به عنوان گره "مبدأ" مشخص می‌کند و کوتاه‌ترین مسیر را از مبدأ مشخص شده تا همهٔ گره‌های دیگر در گراف پیدا می‌کند که به آن "درخت کوتاه‌ترین مسیر (Shortest path tree)" گفته می‌شود.
برای یک مبدأ مشخص شده در گراف، این الگوریتم کوتاه‌ترین مسیر را بین آن گره و سایر نقاط پیدا می‌کند. همچنین از این الگوریتم می‌توان برای یافتن کوتاه‌ترین مسیر بین دو گره مشخص استفاده کرد، به این صورت که الگوریتم از گره مبدأ آغاز می‌شود و در زمانی که به گره مقصد رسید متوقف خواهد شد. این الگوریتم کوتاه‌ترین مسیر به شکل گسترده در پروتکل‌های مسیریابی در شبکه‌ها کامپیوتری، به‌طور مثال در IS-IS یا در OSPF مورد استفاده است.
الگوریتم دایکسترا از برچسب‌هایی استفاده می‌کند که اعداد صحیح مثبت یا اعداد حقیقی هستند و کاملاً مرتب شده‌اند. اما می‌توان آن را به اعدادی که به صورت جزئی (محلی) مرتب هستند نیز تعمیم داد. به این عمومی سازی، الگوریتم کوتاه‌ترین مسیر عمومی دایکسترا گفته می‌شود.
الگوریتم دایکسترا برای ذخیره‌سازی دسترسی به اطلاعات ذخیره‌شده، از یک داده ساختار استفاده می‌کند. الگوریتم اصلی از صف اولویت‌دار استفاده می‌کند و پیچیدگی آن formula_9 (جایی که formula_10 تعداد گره‌ها است) می‌باشد. ایده این الگوریتم در مقالهٔ نیز ارائه شده‌است. با استفاده از یک صف اولویت‌دار در هرم فیبوناچی پیچیدگی زمان اجرا را به formula_11 (که formula_12 تعداد لبه‌ها است) رساندند. این الگوریتم به صورت مجانبی سریعترین الگوریتم یافتن کوتاه‌ترین مسیر از یک مبدأ برای یک گراف جهت دار با وزنهای غیر منفی بدون محدودیت شناخته شده‌است.
گرهی که الگوریتم از آن آغاز می‌شود گره اولیه نامیده می‌شود. طول مسیر گره Y را فاصلهٔ گره Y تا گره اولیه (مبدأ) قرار می‌دهیم. الگوریتم دایکسترا مقادیر اولیه‌ای (معمولا صفر برای گره اولیه و بی‌نهایت برای سایر گره‌ها) را به گره‌ها نسبت می‌دهد و در هر مرحله آن را بهبود می‌بخشد.