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

[usef01]

سلام
من مي خواستم مسئله فروشنده دوره گرد رو با روش ژنتيك با استفاده از متلب حل كنم لطفا من رو راهنمايي كنيد.

 

[kind_hearted]

سلام
من مي خواستم مسئله فروشنده دوره گرد رو با روش ژنتيك با استفاده از متلب حل كنم لطفا من رو راهنمايي كنيد.

با سلام خدمت دوست گرامي

مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem ، به‌اختصار: TSP )

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

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

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


كد:
C({1},1) = 0for (S=2 to n )for All Subsets S subset of {1,2,3,...} of size S and containing 1C(S,1) = &for All J member of S , J<>1C ( 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
.............
اين مسئله ، مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
"تعداد کل راه‌حل‌ها برابر است با برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس."


اميدوارم مطالب ارائه شده به دردتان بخورد !

 

[mohammadheydari]

کمک از اساتید زبان متلب_مساله فروشنده دوره گرد

کمک از اساتید زبان متلب_مساله فروشنده دوره گرد

[FONT=&quot]سلام بر دوستان و اساتید محترم[/FONT]​

[FONT=&quot]خسته نباشید[/FONT]​

[FONT=&quot]پروژه بنده حل مساله فروشنده دوره گرد به وسیله الگوریتم ژنتیک به زبان مطلبه [/FONT]​

[FONT=&quot]من این برنامرو تو سایت [/FONT] Mathworks [FONT=&quot] پیدا کردم[/FONT]​

http://mohammadheydari.persiangig.com/TSPO.rar​

[FONT=&quot]اما باید یسری تغییرات توش داده بشه[/FONT]​

[FONT=&quot]چون تو این برنامه 50 تا شهر بصورت رندوم در موقعیت های مختلف ایجاد میشن و به هرکدوم یه مقداری به عنوان فاصله یا ارزش اختصاص داده میشه و شهر مبدا و مقصد هم به صورت اتفاقی انتخاب میشن[/FONT]​

[FONT=&quot]اما من میخوام فاصله ی بین شهرها، توسط کاربر که در یک فایل اکسل ذخیره شده مشخص بشه مهمتر از همه در هر بار اجرای برنامه شهر مبدا و مقصد رو خود کاربر انتخاب کنه[/FONT]​

[FONT=&quot]البته من فاصله بین شهرهارو تو فایل اکسل ذخیره کردم و با استفاده از دستور [/FONT]xlsread [FONT=&quot] هم توی برنامه اوردمشون اما نتیجه ی درستی رو نشون نمیداد ولی در مورد اینکه چطور میتونم خودم شهر مبدا و مقصد رو انتخاب کنم چیزی نمیدونم[/FONT]​

[FONT=&quot]اگه دوستان و اساتید راهنمایی کنند خیلی خیلی ممنون میشم[/FONT]​