🚀 پیشرفت بزرگ در الگوریتم‌های گراف: روش جدیدی برای یافتن کوتاه‌ترین مسیرها سریع‌تر از دیکسترا

🧩 محققان دانشگاه‌های Tsinghua، استنفورد و Max Planck موفق به ارائه الگوریتمی قطعی برای مسئله‌ی SSSP (یافتن کوتاه‌ترین مسیر از یک رأس به تمام رأس‌های دیگر) در گراف‌های جهت‌دار با وزن‌های غیرمنفی شده‌اند که از «سد مرتب‌سازی» عبور می‌کند و از دیکسترا سریع‌تر عمل می‌کند.

🔍 ایده کلیدی، ترکیبی از دیکسترا و بلمن-فورد است:

✳️به جای نگه‌داری کامل مجموعه‌ی مرزی مرتب، الگوریتم در صورت بزرگ شدن این مجموعه، چند گام بلمن-فورد را روی رأس‌های آن اجرا می‌کند تا مسیرهای کوتاه سریعاً مشخص شوند.

✳️رأس‌هایی که مسیر طولانی‌تری دارند باید از «نقاط تکیه‌گاه» عبور کنند که تعدادشان به‌مراتب کمتر است.

✳️با روش تقسیم و حل (Divide & Conquer)، مسئله به سطوح کوچک‌تر شکسته می‌شود و پیچیدگی لگاریتمی به یک عامل آهسته‌تر کاهش می‌یابد.


📈 نتیجه: زمانی متناسب با تعداد یال‌ها × یک ضریب لگاریتمی کندتر از دیکسترا، که در عمل سرعت بالاتری به‌ویژه برای کاربردهایی مانند ناوبری، شبکه‌ها و برنامه‌ریزی دارد.

💡 اهمیت کشف:

♻️اثبات اینکه دیکسترا سقف نهایی سرعت نیست.
♻️بهبود قابل‌توجه در حل مسائل مسیرکوتاه در گراف‌های بزرگ.

لینک

#الگوریتم #هوش_مصنوعی #GraphTheory #SSSP #AIResearch
@rss_ai_ir