تا حالا فکر کردید وقتی تو «اسنپ» یا «گوگل مپس» مبدأ و مقصد رو می‌زنید، چطوری تو یه چشم به هم زدن «بهترین» مسیر رو از بین این همه کوچه و خیابون پیدا می‌کنه؟

یا مثلاً تو یه بازی کامپیوتری، اون هوش مصنوعی (AI) دشمن چطوری انقدر قشنگ شما رو پیدا می‌کنه و کوتاه‌ترین راه رو برای رسیدن بهتون انتخاب می‌کنه؟

اینا همشون دارن یه مسئله‌ی معروف به اسم «پیدا کردن کوتاه‌ترین مسیر» (Shortest Path) رو حل می‌کنن. تو این پست میخوایم بریم سراغ دوتا از غول‌های حل این مسئله: دایکسترا (Dijkstra) و اِی-اِستار (A*).

1️⃣ الگوریتم دایکسترا (Dijkstra): کاوشگرِ وظیفه‌شناس (ولی کور!)

این الگوریتم که اسمش رو از خالقش، ادسخر دایکسترا، گرفته، کوتاه‌ترین مسیر از مبدأ رو پیدا میکنه.

چطوری کار می‌کنه؟

✔️ از نقطه‌ی شروع (Source) کارش رو شروع می‌کنه.

✔️ یه «صف اولویت» (Priority Queue) داره. کارش اینه که در هر مرحله، گرهی (node) رو برای بررسی انتخاب می‌کنه که کمترین هزینه (cost) رو از مبدأ داشته باشه.

✔️ این الگوریتم «کور» (Uninformed) ـه. یعنی چی؟ یعنی اصلاً نمی‌دونه مقصد کجاست! 😅

✔️ در نتیجه، جستجوش به صورت «یکنواخت» (مثل Uniform Cost Search) پخش می‌شه. کارش اینه که به صورت سیستماتیک کوتاه‌ترین مسیر از مبدأ به همه‌ی نقاط دیگه رو حساب کنه تا اینکه بالاخره اتفاقی به مقصد ما هم برسه.

نتیجه این روش چیه؟

مزیت: اینه که تضمین می‌کنه کوتاه‌ترین و بهینه‌ترین مسیر رو پیدا می‌کنه (بهش میگن Optimal)، البته به شرطی که وزن منفی (negative weight) تو گراف نداشته باشیم (مثلاً راهی که به جای هزینه داشتن، بهت زمان اضافه کنه!).

عیب: چون «کوره» و نمی‌دونه هدف کجاست، کلی زمان و انرژی صرف بررسی گره‌هایی می‌کنه که اصلاً در جهت مقصد نیستن. (مثلاً می‌خوای از تهران بری شمال، این بنده خدا همزمان مسیرهای به سمت اصفهان رو هم چک می‌کنه، چون شاید یه راه عجیبی از اونجا باشه!).

2️⃣ الگوریتم A* (A-Star): کاوشگرِ هوشمند (و هدفمند)

اِی-اِستار (A*) نسخه‌ی باهوش‌تر و «زرنگ»ترِ دایکستراست. می‌تونیم بگیم A* همون دایکسترای خودمونه، فقط یه «قطب‌نما» یا «GPS» هم دستش گرفته.

چطوری کار می‌کنه؟

✔️ اِی-استار هم مثل دایکسترا، هزینه‌ای که واقعاً تا الان طی کرده (یعنی مسافت واقعی از مبدأ تا گره فعلی) رو حساب می‌کنه. (ریاضیش رو بخوامی بگیم g(n)).

✔️ اما، برگ برنده‌اش اینجاست: اون یه «حدس هوشمندانه» (Heuristic) هم می‌زنه که چقدر فکر می‌کنه تا مقصد مونده. (ریاضیش رو بخوامی بگیم h(n)).

هیوریستیک یعنی چی؟

خیلی ساده‌ست: در مسیریابی، بهترین هیوریستیک همون «فاصله خط صاف» خودمونه. یعنی تو نقشه یه خط صاف از جایی که هستی تا مقصد بکشی.

✔️ پس اِی-استار در هر قدم، میره سراغ گرهی که مجموعِ «هزینه واقعی تا اینجا» + «هزینه تخمینی تا مقصد» (f(n) = g(n) + h(n)) از همه کمتر باشه.

نتیجه این هوشمندی چیه؟

مزیت: چون «آگاه» (Informed) هست و یه «حس جهت‌یابی» داره، جستجوی خودش رو مستقیم می‌بره به سمت هدف. دیگه الکی همه‌جا رو نمی‌گرده و در نتیجه خیلی خیلی سریع‌تره و گره‌های (nodes) کمتری رو بررسی می‌کنه.

عیب (یا نکته مهم): همه‌چی به «خوب» بودن اون حدس (Heuristic) بستگی داره. اگه هیوریستیک شما «قابل قبول» (Admissible) نباشه (یعنی بدبین باشه و فاصله رو بیشتر از حد واقعی حدس بزنه)، A* ممکنه گول بخوره و اصلاً جواب بهینه (Optimal) رو پیدا نکنه!


💡 خب، ما چی یاد گرفتیم؟ (Dijkstra vs A*)

دایکسترا: «کور»ـه و جستجوش (UCS) در تمام جهات پخشه. هدفش پیدا کردن کوتاه‌ترین راه از مبدأ به همه‌ی نقاطه.

اِی-اِستار: «هوشمند»ـه و با کمک هیوریستیک به سمت هدف می‌گرده. هدفش پیدا کردن کوتاه‌ترین راه از مبدأ به یک مقصد مشخصه.

حالا یه نکته:

الگوریتم دایکسترا در واقع یه حالت خاص از الگوریتم A* هست!

چطوری؟ اگه توی A*، اون «حدس هوشمندانه» (h(n)) رو برای همه‌ی گره‌ها صفر در نظر بگیری (یعنی عملاً بگی: «آقا من هیچ حدسی ندارم!»)، الگوریتم A* دقیقاً تبدیل می‌شه به دایکسترا!

پس کی از کدوم استفاده کنیم؟

برو سراغ Dijkstra:

* وقتی می‌خوای کوتاه‌ترین مسیر از یک نقطه به تمام نقاط دیگه رو بدونی (مثلاً تو پروتکل‌های روتینگ شبکه مثل OSPF که باید بدونن بهترین راه تا همه‌ی روترهای دیگه چیه).

برو سراغ A*:

* وقتی یک مبدأ و یک مقصد مشخص داری (۹۹٪ کاربردهای ما مثل GPS، مسیریابی تو بازی‌ها، رباتیک و...).

* وقتی سرعت برات مهمه و می‌تونی یه هیوریستیک خوب (مثل فاصله خط صاف) حساب کنی.

دفعه‌ی بعدی که «نشان» رو باز کردید یا تو یه بازی مثل The Last of Us دیدید که دشمن چقدر هوشمندانه دنبالتون میاد، یادتون باشه که یه چیزی شبیه A* پشت صحنه داره کار می‌کنه.

—-

💡 مثل همیشه کنجکاو بمونید :)

🆔 @MdDaily