درباره مسئله فروشنده دوره گرد

[raha_hakhamanesh]

مسئله فروشنده دوره گرد The traveling-salesman problem

مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های 1- هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .

طرح مسئله
تعدادی شهر داریم و هزینه (مسافت) مسافرت به هر یک از آنها مشخص است به دنبال کم هزینه ترین مسیر هستیم بطوریکه از همه شهرها فقط یکبار عیور کنیم و مجددا به محل شروع بازگردیم

پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می شود اما اگر به روش برنامه نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن ( (O( (n^2)*(2^ n خواهد شد که جز مرتبه های نمایی است. باید توجه داشت علی رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد .

[raha_hakhamanesh]

با سلام
دوستان علاقه مند لطفا جهت اطلاع سایر اعضا کاربردهای این الگوریتم را نام ببرید .

1- طراحی بردهای الکترونیکی دارای مداراهای پیچیده
2- . . .

[k.robot]

لطفا وقتی میخوایین چیزی رو به مردم یاد بدین اول خودتون یاد بگرین.با پویا هزینه:
O(n^2*2^n)

[raha_hakhamanesh]

با سلام

ضمن تشکر از شما دوست عزیز و گرانقدر فرمایش شما کاملا صحیح است .
و لذا جمله فوق تصحیح شد .
به دیگران احترام بگذاریم تا دیگران به ما نیز احترام بگذارند



شبه کد الگوریتم فوق بصورت زیر است که در آن تعداد زیر مجموعه های یک مجموعه n عضوی 2 به توان n می باشد
و for اول یک ضریب n را نیز حاصل می شود که به ازای تمام شهرهای غیر مبدا می باشد و حاصل (n*(2^n را پدید می آورد
بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب می شود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل می کند


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

[zahra_20200]

سلام.خسته نباشید میخواستم بدونم کدی ازش ندارین؟ اگه دارین میشه بفرستین ممنون:D

[raha_hakhamanesh]

با سلام
دوست من شبه کد الگوریتم گذاشته شده زحمت پیاده سازی به عهده خودتون .

موفق باشید

[release2008]

اینم یکی از راه حل های مسئله فروشنده دوره گرد که با الگوریتم شبیه سازی تبریدی پیاده سازی شده. از الگوریتم های هوش مصنوعی تو دسته الگوریتم های ژنتیک است

http://www.codeproject.com/useritems/SimulatedAnnealing.asp