نویسنده (ها): آتاروا دسموخ
در ابتدا منتشر شده در به سمت هوش مصنوعیبشر
تصور کنید که قصد سفر در شهر یا یک شهر کاملاً متفاوت را دارید. شما نقشه های Google را باز می کنید ، مقصد خود را تایپ می کنید ، و در عرض چند ثانیه سریعترین مسیر را به شما نشان می دهد – با زمان ورود تخمین زده شده ، به روزرسانی ترافیک ، مسیرهای جایگزین و حتی گزینه های حمل و نقل عمومی. تقریباً جادویی احساس می شود ، اما در زیر این سادگی دنیایی از تصمیم گیری هوشمندانه است که توسط برخی از الگوریتم های پیشرفته در علوم کامپیوتر تأمین می شود.
بنابراین چگونه نقشه های Google تقریباً فوراً بهترین مسیر را محاسبه می کنند؟ چگونه می داند کدام جاده ها پر ازدحام می شوند ، که سریعترین چرخش است ، و حتی قبل از شروع سفر ، واقعاً چه مدت طول می کشد تا به مقصد خود برسید؟
پاسخ در ترکیبی از تئوری نمودار ، داده های زمان واقعی ، مدل سازی پیش بینی کننده و الگوریتم های بهینه سازی پیشرفته است. هر بار که یک مسیر را درخواست می کنید ، Google Maps اساساً یک معمای ریاضی پیچیده را حل می کند – پیدا کردن کارآمدترین راه برای سفر از طریق یک شبکه گسترده از جاده ها ، با استفاده از شرایط زنده ، داده های تاریخی و الگوهای پیش بینی.
در این وبلاگ ، ما لایه هایی را که چگونه Google Maps کار می کند ، باز می کنیم-نه فقط از منظر فناوری اطلاعات بلکه با شکستن منطق و استراتژی ها به روشی که درک آن آسان باشد. از چگونگی درک جاده ها به عنوان نمودارها ، تا نحوه پیش بینی ترافیک و تصمیم گیری در مورد تغییر شکل دوم ، الگوریتم های واقعی را که باعث می شود ناوبری روزمره احساس بی دردسر شود ، کشف خواهیم کرد.
جاده ها به عنوان نمودارها: ایده اصلی
Google Maps در بنیاد خود ، کل جهان را به عنوان یک شبکه غول پیکر از جاده ها ، تقاطع ها و مقصد می داند. از نظر علوم کامپیوتر ، این شبکه به عنوان یک مدل سازی شده است نمودار – نه نوعی که در کلاس ریاضی با نمودارهای نوار یا توطئه های خط می بینید ، اما الف نمودار ساخته شده از گره ها و لبه هابشر
- گره نکات کلیدی در دنیای واقعی هستند – مانند تقاطع ها ، نقاط دیدنی یا مختصات جغرافیایی (مانند مکان فعلی یا مقصد خود).
- لبه جاده هایی هستند که این نقاط را به هم وصل می کنند. هر لبه دارای یک مقدار است که به عنوان a شناخته می شود وزن، که به طور معمول نشان می دهد که برای سفر به آن بخش جاده چه مدت طول می کشد. وزن می تواند به فاصله ، محدودیت سرعت ، ترافیک یا شرایط جاده بستگی داشته باشد.
بنابراین ، هنگامی که نقشه های Google را باز می کنید و از آن می خواهید که شما را از نقطه A به نقطه B برد ، اساساً از آن سؤال می کنید:
“کوتاهترین یا سریعترین مسیر بین دو گره در این نمودار گسترده جهانی چیست؟”
برای پاسخ به این موضوع ، Google Maps به یک روش واحد متکی نیست. درعوض ، از ترکیبی از الگوریتم های قدرتمند و خوب تحقیق شده استفاده می کند-هر کدام برای رسیدگی به جنبه های مختلف مشکل ، مانند سرعت ، دقت ، به روزرسانی در زمان واقعی و مقیاس طراحی شده اند.
بیایید نحوه عملکرد این الگوریتم ها را با شروع اصول اولیه و ایجاد تکنیک های پیشرفته مورد استفاده Google تجزیه کنیم.
الگوریتم Dijkstra: بنیاد
الگوریتم Dijkstra یکی از اولین و پرکاربردترین تکنیک ها برای یافتن کوتاهترین مسیر از یک گره شروع به تمام گره های دیگر در یک نمودار با وزن غیر منفی.
اینگونه کار می کند:
- از گره منبع شروع کنید و فاصله آزمایشی 0 را به آن اختصاص دهید.
- به همه گره های دیگر فاصله اولیه بی نهایت اختصاص دهید.
- به طور مکرر گره بدون استفاده را با کمترین فاصله انتخاب کنید ، مسافت ها را برای همسایگان خود به روز کنید و آن را بازدید کنید.
- تا رسیدن به مقصد ادامه دهید.
فرمول (ایده اصلی):
new_distance = min(current_distance, previous_distance + edge_weight)
پیچیدگی زمان:
با یک پشته باینری ، الگوریتم Dijkstra دارای پیچیدگی زمانی است
o ((v + e) log v)
کجا حرفهای تعداد راس ها است و اشمیه تعداد لبه ها است.
سلسله مراتب انقباض: پیش پردازش سریع
برای مقیاس الگوریتم Dijkstra برای استفاده جهانی ، Google Maps از یک تکنیک بهینه سازی هوشمندانه شناخته شده به عنوان استفاده می کند سلسله مراتب انقباض (CH)بشر CH به جای اینکه همه جاده ها را به طور یکسان درمان کند ، بر این واقعیت تمرکز می کند که بیشتر سفرهای طولانی به جاده های اصلی مانند بزرگراه ها و مسیرهای شریانی متکی هستند. ایده این است که گره های کم اهمیت – مانند خیابان های مسکونی کوچک یا خطوط محلی – را از نظر مکرر و در عوض حذف کنید میانبرهای مقدماتی بین نقاط مهم تر در شبکه جاده.
این میانبرها زمان سفر واقعی را حفظ می کنند اما از تقاطع های بی اهمیت پرش می کنند و به الگوریتم اجازه می دهد بخش های “پرش” از نقشه را در حین محاسبه مسیر “پرش کند”. این تعداد گره ها را به طرز چشمگیری کاهش می دهد این نیاز به بررسی در طی یک پرس و جو زنده است.
این تکنیک با اولویت بندی جاده های “مهم” مانند بزرگراه ها و اتصالات شهر ، جستجو را انجام می دهد 10 تا 100 برابر سریعتربشر این مانند این است که ابتدا به الگوریتم نمای بزرگنمایی از نقشه و سپس تکمیل جزئیات فقط در صورت لزوم-نقشه های Google را قادر می سازد تا تقریباً فوراً ، حتی برای مسیرهایی که در کل کشورها امتداد دارند ، دستورالعمل های زمان واقعی را ارائه دهند.
A* جستجو: باهوش تر و سریعتر
Google Maps با استفاده از الگوریتم Dijkstra بهبود می یابد a* (A-Star) جستجو. A* یک عملکرد اکتشافی برای هدایت جستجو اضافه می کند و آن را به سمت مقصد متمرکز می کند.
فرمول:
f(n) = g(n) + h(n)
کجا:
g(n)هزینه از نقطه شروع تا گره استnبشرh(n)هزینه تخمین زده شده (اکتشافی) ازnبه هدف (اغلب فاصله مستقیم).
این باعث می شود تعداد مسیرهای غیر ضروری کاوش شده و آن را در استفاده در دنیای واقعی سریعتر کند.
پیچیدگی زمان:
بدترین حالت هنوز است o ((v + e) log v)، اما در عمل ، A* بسیار سریعتر از Dijkstra برای نمودارهای بزرگ به دلیل هرس اکتشافی است.
تطبیق نقشه: رسیدگی به خطاهای GPS
برای اطمینان از اینکه مکان شما به طور دقیق در نقشه منعکس شده است ، حتی اگر داده های GPS کامل نباشد ، Google Maps از تکنیکی به نام استفاده می کند تطابق نقشهبشر سیگنال های GPS به دلیل عوامل مختلفی مانند ساختمانهای بلند ، درختان یا حتی تونل ها می توانند نادرست باشند که می تواند مکان گزارش شده را کمی خاموش کند. این سیستم با مقایسه داده های GPS پر سر و صدا با شبکه جاده و تعیین محتمل ترین مسیری که در واقع در آن قرار دارد ، این نادرست ها را جبران می کند.
این اغلب با استفاده از a حاصل می شود مدل مخفی مارکوف (HMM)، یک مدل آماری که هم موقعیت فعلی و هم الگوهای حرکت کاربر را در نظر می گیرد. هوم شما را تجزیه و تحلیل می کند سرعت ، جهت و نزدیکی به جاده های اطراف برای پیش بینی محتمل ترین مسیری که طی می کنید. به عنوان مثال ، اگر با سرعت ثابت رانندگی می کنید و GPS شما کمی از جاده خارج می شود ، این مدل محاسبه می کند که جاده ای که در نزدیکی آن قرار دارید ، بر اساس جهت و سرعت خود قرار دارید.
قدرت این روش به ویژه در محیط های چالش برانگیز مانند آشکار می شود شهرهای متراکم یا تونل های زیرزمینی، جایی که سیگنال های GPS ضعیف تر یا اغلب از بین می روند. در این شرایط ، مطابقت با نقشه تضمین می کند که “نقطه آبی” روی صفحه شما در جاده صحیح باقی بماند و مکان واقعی خود را به درستی با نقشه هماهنگ نگه دارید. این به Google Maps کمک می کند تا راهنمایی های دقیقی را ارائه دهند ، حتی اگر داده های GPS به تنهایی کافی نباشند.
ترافیک در زمان واقعی با استفاده از مسیریابی پویا
حتی اگر یک ترافیک وجود داشته باشد ، حتی کوتاهترین مسیر نیز مفید نیست. Google Maps شامل می شود داده های ترافیک زنده از:
- میلیون ها کاربر Android (جمع و ناشناس)
- سنسورهای ترافیک و گزارش های جاده ای
- برنامه هایی مانند Waze
به صورت پویا وزن لبه را در نمودار بر اساس سرعت فعلی ترافیک تنظیم می کند. جاده ای که معمولاً 5 دقیقه طول می کشد به دلیل احتقان ممکن است به طور موقت 15 هزینه داشته باشد.
نتیجه؟ نقشه ها می توانند شما را در زمان واقعی مجدداً مسیریابی کنند تا از تأخیر جلوگیری شود.
پیش بینی شرایط آینده با شبکه های عصبی نمودار
Google Maps نیز استفاده می کند شبکه های عصبی نمودار (GNN) برای پیش بینی شرایط ترافیکی برای پنجره های زمان آینده. بوها شبکه عصبی نمودار نوعی از شبکه عصبی است که به طور خاص برای پردازش داده های ساختار یافته به عنوان نمودارها طراحی شده است. در مورد Google Maps ، نمودار نمایانگر شبکه جاده است ، جایی که تقاطع ها و بخش های جاده به ترتیب گره ها و لبه ها هستند. GNN به سیستم اجازه می دهد با عبور از اطلاعات در لبه های نمودار ، ترافیک در یک جاده را تحت تأثیر قرار دهد.
این سیستم عواملی مانند سرعت فعلی ترافیک ، زمان روز ، روندهای تاریخی و انواع جاده ها را در نظر می گیرد. این به نقشه های Google کمک می کند نه تنها بهترین مسیر در حال حاضر بلکه مسیر بهینه را پیش بینی می کند 30 دقیقه جلوتر – یک ویژگی ارزشمند برای سفرهای طولانی.
از نظر پیچیدگی زمانی ، هر لایه GNN در آن فعالیت می کند O (E × D) زمان ، کجا اشمیه تعداد بخش های جاده (لبه ها) و د ابعاد ویژگی های گره/لبه (مانند سرعت ترافیک و نوع جاده) است.
محافظت از حریم خصوصی کاربر
در حالی که Google از داده های موقعیت مکانی با منبع جمعیت استفاده می کند ، از حریم خصوصی نیز محافظت می کند:
- از بین بردن شناسه ها
- جمع آوری داده ها فقط از گروه های بزرگ
- استفاده از تکنیک های حریم خصوصی دیفرانسیل برای جلوگیری از آشکار کردن مسیرهای فردی
این تضمین می کند که حرکات شخصی شما محرمانه باقی می ماند و در عین حال در پیش بینی های بهتر ترافیک برای همه کمک می کند.
نتیجه گیری: الگوریتم های واقعی برای ناوبری در دنیای واقعی
Google Maps به مراتب بیشتر از یک ابزار ساده ناوبری است – این یک کاربرد چشمگیر از علم رایانه پیشرفته است. با استفاده از الگوریتم های قدرتمند مانند:
- الگوریتم Dijkstra برای محاسبات مسیر قابل اعتماد
- a* برای مسیریابی سریعتر و باهوش تر
- سلسله مراتب انقباض برای بهره وری پیشرفته
- تطابق نقشه برای دقت نقطه
- شبکه های عصبی نمودار (GNN) برای پیش بینی ترافیک
- داده های زمان واقعی برای تطبیق مسیرها بر اساس شرایط فعلی
Google Maps می تواند مشکلات مسیریابی پیچیده را پردازش کرده و برنامه های سفر بهینه شده را در یک میلی ثانیه ارائه دهد. این الگوریتم ها با هم کار می کنند تا اطمینان حاصل کنند که سفر شما تا حد امکان کارآمد و دقیق است ، مهم نیست که چند کاربر به طور همزمان آنلاین باشند. بنابراین دفعه بعد که با Google Maps حرکت می کنید ، درک عمیق تری از فناوری پیشرفته ای خواهید داشت که خط آبی ساده را روی صفحه نمایش شما می گذارد.
منتشر شده از طریق به سمت هوش مصنوعی