درباره مسئله فروشنده دوره گرد
مسئله فروشنده دوره گرد The traveling-salesman problem
مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های 1- هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .
طرح مسئله
تعدادی شهر داریم و هزینه (مسافت) مسافرت به هر یک از آنها مشخص است به دنبال کم هزینه ترین مسیر هستیم بطوریکه از همه شهرها فقط یکبار عیور کنیم و مجددا به محل شروع بازگردیم
پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می شود اما اگر به روش برنامه نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن ( (O( (n^2)*(2^ n خواهد شد که جز مرتبه های نمایی است. باید توجه داشت علی رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد .
نقل قول: درباره مسئله فروشنده دوره گرد
با سلام خسته نباشید لطفاَ در مورد docuoments فروشنده دوره گرد توضیحات کامل دهید
نقل قول: درباره مسئله فروشنده دوره گرد
نقل قول: درباره مسئله فروشنده دوره گرد
لطفا اگه كسي بتونه در مورد" موارد كاربرد فروشنده دوره گرد" مقاله اي بذاره... خيلي خيلي ممنون ميشم..
نقل قول: درباره مسئله فروشنده دوره گرد
نقل قول: درباره مسئله فروشنده دوره گرد
C({1},1) = 0
for (S=2 to n )
for All Subsets S subset of {1,2,3,...} of size S and containing 1
C(S,1) = &
for All J member of S , J<>1
C ( S , J ) = min { C ( S - { J } , i ) + D i,J : i member of S , i <> J }
return min j C ( {1 . . . n}, J ) + D J,1
چی هست ؟
توضیح هر قسمت؟
نقل قول: درباره مسئله فروشنده دوره گرد
كسي هست كه كد اين برنامه رو توي C++ داشته باشه؟