این روزها همه ما با استفاده از برنامه های مختلف روی گوشی مسیر رسیدن به جاهایی که اصلا بلد هم نیستیم را به راحتی پیدا می کنیم. اما اگر قرار بود شما به عنوان یک فروشنده مستقل به ده جای مختلف در شهر سر بزنید و با کمترین هزینه ممکن این کار را انجام دهید چه باید می کردید ؟
این مشکلی بود که آقای دایکسترا در سال ۱۹۵۵ برای شما حل کرد. آقای دایکسترا که یک روز با دوست دختر خودش به خرید در شهر رفته بود در هنگام استراحت در یکی از کافه ها، راه حل این مساله به ذهنش رسیده و این مشکل را حل کرد.
الگوریتم دایکسترا یکی از الگوریتم های بسیار مشهور دنیاست که در روتینگ شبکه ها، مسیر یابی نقشه های ترافیکی و حتی یافتن مسیر برای ربات های هوشمند استفاده می شود.
حال ما یک مثال ساده اینجا بعنوان فروشنده داریم. این فروشنده ما در خانه a زندگی می کند.
فروشگاه هایی که قرار است برود به اسم های b, c,d,e,f نام گذاری شده و قیمت کرایه مسیر هم بر روی خطوط نوشته شده.
به زبان علمی به شکل بالا گراف گفته شده و محل فروشگاه ها را راس گراف و خطوط بین انها را یال گراف می نامند.
آنچه من فهمیدم … مثلا قراره هر روز از خانه بزنی بیرون و فروشگاه های مختلف را برای فروش سر بزنی. هر روز یک فروشگاه.
و چون آدم خسیسی هستی…می خواهی با کمترین پول این کار را انجام بدی.
با توجه به نقشه بالا که خانه a محل زندگی من است. بیدار می شم و می بینم که برای من سه تا انتخاب هست. ۱) فروشگاه b برم با ۲ تومان.. ۲) فروشگاه c برم با ۵ تومان ۳) فروشگاه d برم با ۸ تومان..
خوب چون من خسیسم و معلوم نیست فردا چی خواهد شد ..پس من کمترین پول را خرج می کنم تا به یک فروشگاه سر بزنم.
پس فروشگاه b را که ۲ تومن برام هزینه داره را انتخاب می کنم. وقتی رفتم فروشگاه b... اطلاعات جدیدی درباره مبلغ رفتن به فروشگاه c , f بدست میارم که اونها را هم برای خودم یادداشت می کنم.
روز بعدی فرا میرسه ..باز از خانه میام بیرون و می خوام به یک فروشگاه جدید سر بزنم ولی با کمترین هزینه ممکن..
فروشگاه b را که رفتم..پس هیچی ..میمونه فروشگاه های بعدی..اگه بخوام برم به فروشگاه c باید ۵ تومن بدم..اگر بخوام برم d هشت تومن ..اگر بخوام برم f هم بازم هشت تومن…ولی اگه کمی تفکر اقتصادی داشته باشی :) می دونی که با رفتن به b سپس به فروشگاه c می تونی اون روز را با چهار تومان هزینه تموم کنی…(یک تومان به نفعت میشه ) پس مسیر جدید a->b->c را با هزینه چهار تومان انتخاب می کنی.
شب می خوابی و از اینکه تونستی تریک بزنی خوشحالی ..فردا باز بیدار می شی و این بار می خوای بری به یک فروشگاه جدید با کمترین هزینه سفر…
اگر برم به d که میشه ۸ تومن…اگر بخوام برم به f میشه ۸ تومن …ولی اگر برم به e چی ؟
اگر مستقیم برم به c بعدش به e میشه ۶ تومن…ولی می تونم بازم تفکر اقتصادی داشته باشم و با رفتن به b از انجا به c و سپس به e با ۵ تومن روزم را به پایان برسونم…
به من میگن یک آدم باهوش که با استفاده از گراف مسیر تونستم هزینه هام را کنترل کنم.
دو تا فروشگاه های e, f را که روزهای دیگر قراره برم را بررسی می کنم و می بینم که با کمتر از ۸ تومان نمی شه…پس برای هر کدام از آنها نیز ۸ تومان هزینه می کنم و بدین ترتیب آخر روز پنجم همه فروشگاه ها را با کمترین هزینه بازدید کردم.
بدین ترتیب مشکل آقای فروشنده ما حل شد ولی برای دوستانی که میخواهند کمی بیشتر و بصورت علمی تری این مبحث را ادامه بدهند. می توانند از فیلم آموزشی پایین استفاده کنند.
با تشکر از زمانی که برای یادگیری سپری کردید.
