. متن داده‌شده را خلاصه کن

متن: ردیابی تاریخچه مسئله مسیریابی و کوتاهترین مسیر دشوار است. می‌توان تصور کرد که حتی در جوامع بسیار بدوی (حتی حیوانات) نیز این کار بسیار ضروری بوده‌است (به عنوان مثال برای یافتن غذا). تحقیقات ریاضی درباره این مسئله نسبت به مسئله‌های معروف دیگر دیر شروع شد. از اولین الگوریتم‌هایی که برای این مسئله ارائه شد می‌توان به الگوریتم جستجوی اول سطح اشاره کرد. با توجه به پیشرفت کامپیوترها و ظهور مسائل جدید، این مسئله به تدریج از اواسط قرن بیستم مورد توجه قرار گرفت و با ایجاد شبکه جهانی اینترنت، بیش از پیش به آن پرداخته شد. بازی‌های کامپیوتری و نقشه‌های آنلاین، امروزه از پیشرفته‌ترین الگوریتم‌های مسیریابی استفاده می‌کنند. مسیریابی عبارت است از پیدا کردن یک مسیر بین دو نقطه از فضا که ممکن است مابین آنها موانعی وجود داشته باشد. مسئله مسیریابی به دو زیرمساله زیر قابل تقسیم است: ایجاد یک گراف یافتن مسیر مطلوب روی گراف با طراحی یک الگوریتم مسیریابی در مرحله اول سعی بر این است که فضای پیوسته به فضایی گسسته نگاشته شود. به این ترتیب یک گراف به وجود می‌آید که در آن (مجموعه رئوس گراف) نماینده نقاطی از فضای پیوسته و (مجموعه یالهای گراف) نماینده وجود یا عدم وجود ارتباط بدون واسطه بین دو نقطه از فضای پیوسته‌است. این گراف در مرحله دوم به عنوان ورودی به یک الگوریتم مسیریابی داده می‌شود. خروجی این الگوریتم یک آرایه‌ی مرتب از راس‌ها است که برای رسیدن به راس هدف باید آن‌ها را به ترتیب و بدون واسطه طی کرد. الگوریتم‌های مسیریابی معمولا علاوه بر این‌که می‌خواهند یک مسیر پیدا کنند، در پی مسیری هستند که بر اساس معیار خاصی (مثلا طول مسیر) بهینه باشد. متد مسیریابی با شروع از یک راس و جستجو در راس‌های مجاور آن تا زمان رسیدن به راس مقصد، یک گراف را جستجو می‌کند؛ که معمولا هدف آن یافتن سریع‌ترین مسیر است. در حقیقت هدف الگوریتم مسیر یابی عموما یافتن مسیری با کمترین تعداد راس استفاده‌شده (در گراف‌های فاقد وزن)، یا کمترین جمع اوزان مشاهده‌شده (در گراف‌های وزن‌دار) است. به عنوان مثال می‌توان گفت که الگوریتم مد نظر، همانند شخصی است که قصد دارد از نقطه‌ای به نقطه دیگری برسد؛ به جای این‌که این شخص تمام مسیرهای موجود را بررسی کند، در یک مسیر حرکت می‌کند و فقط زمانی از مسیر خود منحرف می‌شود که مانعی بر سر راه وی وجود داشته …
خلاصه:
مسیر یابی یک الگوریتم برای برنامه‌های کامپیوتری است که هدف آن یافتن (غالبا) کوتاه‌ترین مسیر بین دو نقطه است . مسیر یابی یک راه کاربردی برای حل هزارتو‌ها است . مسیر یابی به مقدار زیادی به مسئلهٔ کوتاه‌ترین مسیر در نظریهٔ گراف‌ها ارتباط دارد ؛ که در واقع این مسئله به این موضوع می‌پردازد که چگونه سریع‌ترین ، ارزان‌ترین (از لحاظ تعداد راس‌ها) و کوتاه‌ترین مسیر را بین دو نقطه در یک شبکهٔ بزرگ بیابیم .