بخشی از پاورپوینت
اسلاید 1 :
بسم الله الرحمن الرحیم
اسلاید 2 :
مسئله فروشنده دوره گرد(Traveling salesman problemیاTSP)
در محدوده ی جغرافیایی فروشنده ی دوره گرد تعدادی شهر وجود دارد که فاصله بین هر زوج از شهر ها مشخص وعددی ثابت است. قرار است فروشنده از یکی از شهر ها شروع کند و کلیه ی شهر ها را ، هر یک را فقط یکبار ، ملاقات کند و در نهایت به نقطه ی شروع برگردد.
مساله فروشنده ی دوره گرد کاربرد های متنوعی دارد. مانند تخلیه ادواری صندوق های پستی به وسیله ی پستچی.
اسلاید 3 :
این مسئله اولین بار توسط دو دانشمند به نام های 1-هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد.
اولین نمونه شبیه به این مساله درسال 1759 مطرح شد و به این صورت بود که یک مهره اسب می بایست روی بردشطرنج حرکت کند و از هر خانه دقیقا یک بار عبور کند .
مسئله فروشنده دوره گرد جزو مسائل رام نشدنی می باشد و حل دقیق آن زمان زیادی می برد.
اسلاید 4 :
در این مساله میخواهیم دوری همیلتنی با حداقل هزینه را بیابیم .
در یک گراف جهت دار، یک تور، که به آن دور هامیلتونی نیز گفته می شود عبارت است از مسیری از یک راس به خودش که از تمام رئوس دیگر دقیقا یک بار عبور کند.
نکته: ممکن است گرافی اصلا تور نداشته باشد.
اسلاید 5 :
نکته: طول تور بهینه وابسته به انتخاب راس آغازین نیست.
این مساله را می توان به صورت ریاضی هم شبیه سازی کرد . به دوری فراگیر G(v,e) این ترتیب که ما در یک گراف وزن دار( اویلری) با مینیمم مجموع وزنهای یالهای گذرنده می خواهیم بیابیم .
در حالت عادی باید کلیه ی روش های ممکن بررسی شود.که در این حالت مرتبه ی زمانی ! n خواهد بود.
اسلاید 6 :
به روش ریاضی مساله با یافتن تعداد جایگشت ها وسپس ارزیابی هر حالت بررسی می شود .
تعداد جایگشتها n! است. برای یافتن مینیمم دورها نیز به حداکثرn! محاسبه احتیاج داریم. ولی اگر n را زیاد فرض کنیم تعداد محاسبات بسیار بالا خواهد بود به همین دلیل گفته می شود که الگوریتم حل مسأله در زمان چند جمله ای نیست. (None-Polynomial)
اسلاید 7 :
حال می خواهیم الگوریتم برنامه نویسی پویا (Dynamic programming)ارائه شده برای حل مساله TSP را مطرح کنیم .
تا به امروز الگوریتمی بدست نیامده است. که این مساله را در زمان چندجمله ای (Polynomial) حل کند .
به همین دلیل ما بهینگی را فدای زمان می کنیم تا بتوانیم در یک زمان معقول به یک جواب خوب برسیم .
اسلاید 8 :
گراف زیر را در نظر بگیرید:
اسلاید 9 :
در گراف فوق، سه تور که از V1 شروع شوند عبارتند از:
[V1,V2,V3,V4,V1]=22
[V1,V3,V2,V4,V1]=26
[V1,V3,V4,V2,V1]=21
در شکل فوق، مسیر [V1,V3,V4,V2,V1] بهینه می باشد.
اسلاید 10 :
همان طور که در ابتدا اشاره شد، یک راه برای پیدا کردن مسیر بهینه، بدست آوردن همه تور های ممکن می باشد که پیچیدگی آن از مرتبه O(n!) می باشد.دلیل آن هم این است که اگر فرض کنیم از هر گره به تمام گره های دیگر یال (مسیرمستقیم) وجود داشته باشد، اگر از یگ گره دلخواه شروع کنیم، گره دوم می تواند n-1 حالت داشته باشد و وقتی بر روی گره دوم قرار گرفتیم، گره سوم می تواند هر یک از n-2 راس باقی مانده باشد و به همین تربیت جلو می رویم تا به گره n ام برسیم . بنابراین تعداد کل تور ها برابر است با:
(n-1)*(n-2)*…*2*1=(n-1)!
اسلاید 11 :
حال می خواهیم روش برنامه نویسی پویا را برای حل مسأله فوق به کار بریم. برای حل مسأله فوق از تعاریف زیر استفاده می کنیم:
مجموعه همه رئوس گراف = V
زیر مجموعه ای از رئوس گراف = A
طول کوتاه ترین مسیر از Vi به V1 که از هر راس زیر مجموعه A دقیقا یکبار می گذرد = D[Vi][A]
اسلاید 12 :
برای نشان دادن مجموعه ای از رئوس از علامت {}و برای نمایش یک مسیر از علامت [ ] استفاده می کنیم.
در گراف مثال قبلی اگر A = {V3} باشد، داریم:
D[V2][A] = len[V2,V3,V1] = ∞
و اگر A = {V3,V4} باشد، داریم:
D2[V2][A] = D2[V2][{V3,V4}] = Min(len[V2,V3,V4,V1],len[V2,V4,V3,V1]) = Min(20,∞) = 20
با توجه به تعریف فوق بدیهی است که: D[Vi][ᴓ] = W[i][1] کهW همان ماتریس هم جواری است.
اسلاید 14 :
فرمول بازگشتی زیر، حل مساله فروشنده دوره گرد را با روش برنامه نویسی پویا فراهم می کند:
اسلاید 15 :
الگوریتم برنامه نویسی پویا برای مسئله فروشنده دوره گرد:
ورودی : یک گراف جهت دار و موزون و n تعداد رئوس در گراف. این گراف توسط آرایه دو بعدی w نشان داده می شود که سطرها و ستون های آن از 1 تا n اندیس گذاری شده اند و [i][j] وزن یال میان راس i ام و راس j ام است .
خروجی : یک متغیر minlength که مقدار آن طول یک تور بهینه است و آرایه دوبعدی p که بتوان از آن یک تور بهینه ایجاد کرد.
اسلاید 17 :
تحلیل پیچیدگی فضا و زمان در حالت معمول برای الگوریتم فوق:
عمل اصلی: زمان در هر دو حلقه ی اول و آخر ، در مقایسه با زمان در حلقه میانی چشمگیر نیست، بنابراین دستورات اجرا شده برای هرمقدار vjرامی توان عمل اصلی در نظر گرفت.
اندازه ورودی :n،تعداد رئوس موجود در گراف
به ازای هرمجموعه A رأس، باید n-1-k رأس در نظر بگیریم وبه ازای هریک از این رئوس،عمل اصلی k رأس، برابر با است،تعداد کل دفعاتی عمل اصلی انجام می شود
