فروشنده دوره گرد tsp با الگوریتم ژنتیک در #c سی شارپ، traveling salesman problem
موضوع پروژه: سورس الگوریتم فروشنده دوره گرد فروشنده دوره گرد tsp با الگوریتم ژنتیک در #c سی شارپ، traveling salesman problem
|نسخه نرم افزار:Microsoft Visual Studio|
همراه با فایل پیاده سازی درC#
Microsoft Visual Studio
مسئله فروشنده دوره گرد Travelling salesman problem، یا به اختصار: TSP به این صورت است که نقشه شهر به صورت یک گراف وزن دار به عنوان ورودی داده میشود که وزن یال ها فاصله شهر ها از همدیگر است فرض کنید یک فروشنده بخواهد از هر شهر تنها یک بار عبور کند که نقطه شروع و پایان یک شهر باشد. کمترین مسافتی که فروشنده می تواند همه مسیر را بپیماید، کدام است؟ در واقع ما به دنبال یک دور همیلتونی بهینه هستیم .این مساله را می توان با نوشتن همه دورهای همیلتونی ممکن با نقطه شروع و پایان از راس و محاسبه کل مسافت پیموده شده برای هر دور حل کرد. اما این کار در عمل برای حتی تعداد کم شهرها بسیار زمان بر است به همین دلیل از روش پویا برای حل این مسئله استفاده می شود
شرح مسئله بدین شکل است:
- تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه‌حل‌ها برابر است با 
برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های ۱- هامیلتون ایرلندی و ۲- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .
دیدگاه ها