حل مسئله فروشنده دوره گرد به روش حریصانه در زندگی به چه دردمان می خورد؟(قسمت پیش درامد ریاضیاتی داستان)

داستان ما در اوایل داستان یه وصله. وصل یک مسئله ی ریاضی و یک راه حل. بعدش میریم سراغ درسی که داره

قصه از اونجا شروع شد که قرن هجدهم میلادی ریاضی دانان گرامی در اثر سر رفتگی حوصله ناشی از حل مسئله های بسیار اومدن و یک سوال سخت تر که چند قرنی فکرشون رو مشغول کنه مطرح کردند:

فرض کنید طول(یا هزینه طی کردن)هر جاده یک مقدار معینه؛ فروشنده دوره گرد ما که در تصویر مشاهده می کنید می خواد به تمام شهرها یک دور سر بزنه و دورباره برگرده سر جای اولش. به چند حالت میتونه انجامش بده؟

-یک نفر از همون اوایل تاریخ طرح سوال گفت در یک گراف کامل برابر است با اینقدر حالت:

(1/2)*(n-1)!

*صدای خدا پدرتو بیامرزه راحتمون کردی از قسمت تنبل های کلاس ریاضی بلند شد*

اساتید که انتظار وجود همچین افراد با استعدادی رو در تاریخ ریاضیات داشتند با همکاری اون نابغه سوال سخت تر رو مطرح کردند:

خب ما طول(یا هزینه طی کردن) هر جاده رو که می دونیم. حالا شما بگید چطوری میشه کوتاه(ارزان) ترین مسیر از مسیرهایی که جناب دوره گرد می تونه انتخاب کنه و شرط قبلی که فقط و فقط یک بار عبور از هر شهر در مسیر باشه رو رعایت کنه؟

یا به زبون اساتید : " تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاً یکبار عبور کند و به شهر شروع بازگردد. "

به دست آوردن جواب مسئله برای دو، سه، چهار یا پنج شهر نسبتا آسان بود اما وقتی کار به تعداد شهرهای بیشتر می رسید مغز آدمی قاصر از محاسبه تمام حالات بود

رایانه ها وارد جنگ های بزرگ ریاضیات شدند. ریاضی دانانی که الگوریتم نویس بهتری بودن دست به دامن رایانه ها شدند و از اونها برای رفع مشکل این دوره گرد بی چاره و در عین حال خیالی کمک خواستن. نتیجه هم داغ کردن این عزیزان و گاهی سوختنشان بود

الگوریتم نویسان خبره الگوریتم ها رو بهینه کردند؛ روش های مختلف برای برداشتن بار از روی دوش رایانه ها ابداع شد. این قضیه و امثالش بزرگ شدند و شدن قسمت بزرگی از طراحی الگوریتم به نام بهینه سازی. اما باز رایانه ها و ابر رایانه ها با بیشتر شدن تعداد شهرها دردی شبیه درد زایمان سراغشون میومد و دمای اونها با دمای میدان های اصلی شهرهای ایران در چهارشنبه سوری برابری میکرد

غافل از اینکه در جایی از دنیا یه فروشنده دوره گرد کم حوصله بود که قراره در قسمت بعدی به ما درس زندگی بده...

پس تا قسمت بعد خدا نگهدار

اگر می خواهید درباره ی مطالب بالا تخصصی تر بدانید:

و جست و جو کنید : الگوریتم های بهینه سازی