traveling salesman problem

شهر بازدید می کند و به شهر مبدأ باز می گردد. در اینجا به تفکیک اجزای اصلی آمده است: شهرها: مجموعه مکان هایی که باید بازدید کرد. فاصله ها ( یا هزینه ها ) : هزینه سفر بین هر جفت شهر. این اغلب به عنوان یک ماتریس بیان می شود که در آن �فاصله[i][j]� فاصله شهر �i� تا شهر �j� است. مسیر/تور: دنباله ای از شهرها که دقیقاً یک بار از هر شهر بازدید می کند و به شهر شروع باز می گردد. هدف بهینه سازی: یافتن مسیر با حداقل مسافت کل ( یا هزینه ) . چرا مهم است؟ مسئله فروشنده دوره گرد فقط یک تمرین تئوری نیست. در بسیاری از زمینه ها کاربردهای عملی دارد: تدارکات و حمل و نقل: بهینه سازی مسیرهای تحویل کامیونها، اتوبوسها و خدمات پستی. ساخت: بهینه سازی حرکت روباتها یا ماشین های خودکار در یک کارخانه برای به حداقل رساندن زمان تولید. توالی یابی :DNAیافتن ترتیب بهینه برای تجزیه و تحلیل قطعات DNA. زمان بندی کار: یافتن بهترین دنباله برای اجرای وظایف در یک ماشین برای به حداقل رساندن کل زمان. سیم کشی کامپیوتر: بهینه سازی قرار دادن قطعات روی برد مدار برای به حداقل رساندن طول سیم. بهینه سازی کلونی زنبورها و مورچه ها: رفتار زنبورها و مورچه هایی را که کوتاه ترین مسیر را برای رسیدن به منبع غذایی پیدا می کنند، تقلید می کند. به طور خلاصه، مسئله فروشنده دوره گرد یک مشکل اساسی در تحقیقات علوم کامپیوتر و عملیات است که چالش های بهینه سازی و نیاز به الگوریتم های کارآمد را برجسته می کند. در حالی که یافتن بهترین راه حل مطلق اغلب دشوار است، تکنیک های مختلف، تقریب خوبی برای کاربردهای عملی ارائه می دهند.