مسئله فروشنده دوره گرد ( به انگلیسی: Travelling salesman problem، به اختصار: TSP ) مسئله ای مشهور در بهینه سازی ترکیبیاتی است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و چوریو مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است که:
تعداد جواب های شدنی مسئله، برابر است با 1 2 ( n − 1 ) ! برای n> ۲ که n تعداد شهرها می باشد. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
مسئله فروشنده دوره گرد یا Traveling Salesman Problem ( به اختصار TSP ) ، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.
سه روش کلی برای کد کردن راه حل های مسئله TSP ارائه شده است که در الگوریتم های مختلفی قابل استفاده هستند. راه حل های سه گانه عبارتند از:
الف ) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms ( به اختصار GA ) شبیه سازی تبرید یا Simulated Annealing ( به اختصار SA ) جستجوی ممنوعه یا Tabu Search ( به اختصار TS ) جستجوی همسایگی متغیر یا Variable Neighborhood Search ( به اختصار VNS ) بهینه سازی کلونی مورچگان یا Ant Colony Optimization ( به اختصار ACO ) جستجوی هارمونی یا Harmony Search ( به اختصار HS ) و سایر الگوریتم های بهینه سازی گسسته
ب ) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms ( به اختصار GA ) بهینه سازی ازدحام ذرات یا Particle Swarm Optimization ( به اختصار PSO ) الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm ( به اختصار ICA ) تکامل تفاضلی یا Differential Evolution ( به اختصار DE ) بهینه سازی مبتنی بر جغرافیای زیستی یا Bio - geography Based Optimization ( به اختصار BBO ) استراتژی های تکاملی یا Evolution Strategies ( به اختصار ES ) برنامه ریزی تکاملی یا Evolutionary Programming ( به اختصار EP ) و سایر الگوریتم های بهینه سازی پیوسته
پ ) نمایش جواب به شکل ماتریس های شبیه فرومون که توسط تمامی الگوریتم های اشاره شده در مورد ( ب ) قابل استفاده می باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفشرح مسئله بدین شکل است که:
تعداد جواب های شدنی مسئله، برابر است با 1 2 ( n − 1 ) ! برای n> ۲ که n تعداد شهرها می باشد. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
مسئله فروشنده دوره گرد یا Traveling Salesman Problem ( به اختصار TSP ) ، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.
سه روش کلی برای کد کردن راه حل های مسئله TSP ارائه شده است که در الگوریتم های مختلفی قابل استفاده هستند. راه حل های سه گانه عبارتند از:
الف ) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms ( به اختصار GA ) شبیه سازی تبرید یا Simulated Annealing ( به اختصار SA ) جستجوی ممنوعه یا Tabu Search ( به اختصار TS ) جستجوی همسایگی متغیر یا Variable Neighborhood Search ( به اختصار VNS ) بهینه سازی کلونی مورچگان یا Ant Colony Optimization ( به اختصار ACO ) جستجوی هارمونی یا Harmony Search ( به اختصار HS ) و سایر الگوریتم های بهینه سازی گسسته
ب ) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms ( به اختصار GA ) بهینه سازی ازدحام ذرات یا Particle Swarm Optimization ( به اختصار PSO ) الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm ( به اختصار ICA ) تکامل تفاضلی یا Differential Evolution ( به اختصار DE ) بهینه سازی مبتنی بر جغرافیای زیستی یا Bio - geography Based Optimization ( به اختصار BBO ) استراتژی های تکاملی یا Evolution Strategies ( به اختصار ES ) برنامه ریزی تکاملی یا Evolutionary Programming ( به اختصار EP ) و سایر الگوریتم های بهینه سازی پیوسته
پ ) نمایش جواب به شکل ماتریس های شبیه فرومون که توسط تمامی الگوریتم های اشاره شده در مورد ( ب ) قابل استفاده می باشد.
wiki: مسئله فروشنده دوره گرد