الگوریتم های جدید مسیریابی برخط و با حافظه ی محدود برای مثلث بندی های دلانی

«مسیریابی» همواره به عنوان یکی از مسائل اساسی و مهم در علوم کامپیوتری به شمار می‌رود و در بسیاری از زمینه ها از جمله رباتیک و شبکه های بی سیم کاربرد دارد. ورودی این مسئله اغلب اطلاعاتی از یک گراف، راس مبدا و مقصد بوده و خروجی آن نیز مسیری (دنباله ای از رئوس) از مبدا به مقصد است. مسیریابی اغلب در یک فضای هندسی که توسط یک «گراف هندسی» قابل مدل سازی است مطرح می شود، یکی از مفیدترین انواع گراف های هندسی که ویژگی های مفیدی جهت سهولت مسیریابی در بر دارد «مثلث بندی دلانی» است. هنگامی که اطلاعات کاملی از گراف مورد نظر در دسترس باشد با استفاده از الگوریتم‌های پیدا کردن مسیر بهینه در گراف های جهت دار از جمله dijkstra می توان به مسیر بهینه رسید، اما در حالت «برخط» که اطلاعات موجود محدود هستند و در هر مرحله انتخاب بسته/ربات مورد نظر باید فقط بر اساس اطلاعات محلی صورت بگیرد، مسئله با چالش‌های بیشتری روبرو می‌گردد. در این مقاله، ما چهار الگوریتم برخط با پیچیدگی حافظ o(1) برای مثلث بندی های دلانی را ارائه نموده و با مقایسه‌ی عملکرد آن ها با الگوریتم‌های مشابه روی نمونه‌های شبیه سازی شده، آن ها را ارزیابی می‌نماییم. نتایج به دست آمده در آزمایشات ما نشان می‌دهند که الگوریتم‌های جدید در عین حفظ سادگی و آسان بودن پیاده سازی، عملکرد بیشتر الگوریتم های مشابه موجود را بهبود می‌دهند.