در این پست می‌خوام با زبان ساده به یکی از پرسش‌ها در بین علاقه‌مندان به علوم کامپیوتر پاسخ بدم.
- نرم‌افزار‌های مسیریابی مثل Waze و Google Maps این‌روز‌ها به یکی از اعضای بدن ما تبدیل شده‌اند و خیلی از ما بدون استفاده از آن‌ها یا دیر به مقصد می‌رسیم و یا حتی گم می‌شیم! اما این نرم‌افزارها چگونه کار می‌کنند و چطوری کوتاه‌ترین مسیر رو به ما پیشنهاد می‌دهند؟!
- در زیر مرحله به مرحله به این مساله می‌پردازیم:
۱. اطلاعات جفرافیایی و هندسی خیابون‌ها و کوچه‌ها و میدون‌ها و … (اینکه کجاند، چقدر طول و چقدر عرض دارند، شکل آن‌ها چجوری است و …) در قالب داده‌های Geospatial (فارسی: زمین-مکانی!) با فرمت‌هایی مثل GeoJSON ذخیره می‌شوند که شما هم می‌تونید دیتا‌های geospatial شهر خودتون رو در قالب فایل GeoJSON از اینترنت دانلود کنید.
۲. داده‌های geospatial خیابون‌ها پردازش شده و اطلاعاتی مثل تقاطع خیابون‌ها ازش استخراج میشه. شما هم می‌تونید مثلا با پکیج GeoPandas خودتون این پردازش‌ها رو انجام بدید.
۳. یک گراف بزرگ ساخته می‌توان ساخت که هر گره گراف یکی از تقاطع‌ها و هر یال گراف یکی از خیابون‌های متصل‌کننده دو تقاطع است. این گراف یک گراف وزن‌داره. یعنی هر یال یه عدد دارد که مدت زمان لازم برای تردد در آن یال (خیابون) رو نشون می‌دهد. حالا این عدد رو فعلا نداریم. مرحله بعد این عدد تخمین زده می‌شود.
۴. بر اساس میانگین سرعت حرکت افرادی که در اون خیابون در حال تردد اند و اطلاعات آن‌ها توسط اپلیکیشن جمع‌آوری می‌شود می‌شود به یک تخمینی از میزان ترافیک موجود در آن خیابون رسید. به کمک این تخمین و همچنین اطلاعات و تاریخچه‌ی جمع‌آوری شده در روز‌های قبل، یک مدل Machine Learning (معمولا یک شبکه عصبی عمیق) میاد و مدت زمانی که برای طی کردن اون خیابون (بین دو تقاطع) لازمه (Estimated Time of Arrival) رو تخمین میزند. این عدد در واقع میشه وزن هر یال روی گراف.
۵. حالا که داستان به یک مساله فرمال ریاضی (گراف) مدلسازی شد، به راحتی با الگوریتم‌های پیمایش گراف و الگوریتم‌های Shortest Path Finding برای گراف‌های وزن‌دار میشه کوتاه‌ترین مسیر بین دو نقطه و همینطور مدت زمان لازم برای تردد از آن را پیدا کرد. سیستم‌های مسیریاب (Routing Engines) معمولا از الگوریتم *A برای پیدا کردن مسیر شبه‌بهینه استفاده می‌کنند. اگر با این الگوریتم آشنا باشید (بچه‌های کامپیوتری در درس هوش مصنوعی می‌خونن) می‌دونید که با سرعت بالایی مسیر شبه‌بهینه رو پیدا می‌کنه. این الگوریتم از یک نقطه در گراف شروع کرده و به بهترین نقطه همسایه خود می‌رود و این‌کار را انقدر ادامه داده تا به مقصد برسد.
بهترین نقطه همسایه هم نقطه ای است که (زمان رسیدن از مبدا تا آن نقطه + فاصله تا مقصد) در آن کمترین باشه. اما اینجا فاصله تا مقصد رو که نداریم (اگه داشتیم که مساله وجود نداشت) بنابراین با استفاده از یک هیوریستیک شهودی اون رو تخمین میزنیم. هیوریستیک شهودی اینجا معمولا فاصله مستقیم (بدون توجه به ساختار خیابون‌ها) بین مختصات جغرافیایی دو نقطه است. فقط دقت کنید که مختصات جغرافیایی در بیشتر موارد بر اساس طول و عرض جغرافیایی (Latitude/Longitude) بیان شده که برحسب درجه است بنابراین نمیتونید از فرمول فاصله اقلیدسی (یا قضیه فیثاغورث) برای آن استفاده کنید به جاش باید از فرمول Haversine استفاده کرده و فاصله great-circle distance رو حساب کنید که قوس سیاره زمین را هم در نظر بگیره.
۶. جمع وزن یال‌ها درمسیر هم به عنوان مدت زمان طی شدن مسیر در نظر گرفته می‌شود.
تمام
