صفحه 1 از 3 123 آخرینآخرین
نمایش نتایج: از شماره 1 تا 10 , از مجموع 23

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

  1. #1
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

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

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


    290px Salesman

    اگر فروشنده دوره‌گرد از نقطه 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) = 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
    .............
    اين مسئله ، مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
    شرح مسئله بدین شکل است:
    تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
    تعداد کل راه‌حل‌ها برابر است با برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.

    مسئله‌های مرتبط

    مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
    مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP ) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
    تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌ از یک شهر عبور کند. این مسئله به « مسئله سیاست‌مدار مسافر» نیز شهرت دارد.

    الگوریتم‌ها
    مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
    طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
    استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
    پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.

    الگوریتم‌های دقیق
    سرراست ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی n22n حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.

    الگوریتم‌های مکاشفه‌ای
    الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آنها را به صورت زیر دسته‌بندی کرد:
    مکاشفه‌ای سازنده
    بهبود تکراری
    مبادله دوبه‌دو
    مکاشفه‌ای k-opt
    مکاشفه‌ای V-opt
    بهبود تصادفی
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  2. 4 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  3. #2
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    ابتدا سايتهايي که کدهاي حل اين مسئله را از روش هاي متفاوت و زبانهاي مختلف ارائه کرده اند:

    traveling salesmanhtm cmp kidsplainbanner2010 bnr

    Source Code Library: Travelling Salesman Problem (TSP

    Solving Travelling Salesman Problems Using Genetic Algorithms


    Solution to Travelling Salesman Problem
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  4. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  5. #3
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    روش ابتکاری ساخت و بهبود تور مسئله فروشنده دوره گرد نامتقارن


    [DOWN]http://dl.azardl.com/sh/52613859810.pdf[/DOWN]
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  6. 4 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  7. #4
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    کد حل مساله فروشنده دوره گرد با الگوريتم ژنتيک


    [DOWN]http://dl.azardl.com/sh/TSP.zip[/DOWN]
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  8. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  9. #5
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    براي حل مسئله فروشنده دوره گرد با استفاده از شبکه هاپفیلد توصيه ميکنم اين مقالات را مطالعه بفرمائيد:

    همچنين کدي با متلب در اين سايت قرار دارد:
    كد:
    کد:
    http://en.pudn.com/downloads136/sourcecode/math/detail578369_en.html
    يک کد هم از tsp در لینک های زیر آمده است .

    [DOWN]http://dl.azardl.com/sh/Downloads43.rar[/DOWN]
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  10. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  11. #6
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    حل مسأله tsp (فروشنده دوره گرد)با استفاده از شبکه عصبی هاپفیلد
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  12. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  13. #7
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    و اين هم توضيحات کامل و برنامه همراه سورس سي پلاس پلاس
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  14. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  15. #8
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    ارائه الگوریتم تركیبی مورچگان وژنتیك برای حل مسئله فروشنده دوره گرد

    منبع: چهارمین کنفرانس بین المللی مهندسی صنایع - 1384

    چکیده:
    مساله فروشنده دوره گرد جزء مسائل مشهور و كلاسیك تحقیق در عملیات می باشد. بسیاری از فعالیت های
    علمی را می توان به صورت مسئله فروشنده دوره گرد در آورد و سپس حل نمود. روشهای بهینه یابی موجود برای حل مسائل سخت (همچون مسئله فروشنده دوره گرد) بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می باشند كه از كارایی عملی آنها در حل مسائل با ابعاد واقعی می كاهد بدین علت در دهه های اخیراستفاده ازالگوریتم های ابتكاری و فوق ابتكاری مورد توجه قرار گرفته است. در این بین الگوریتم های فوق ابتكاری بدلیل ساختار ساده وتوانایی هایی كه از خود نشان داده اند مورد استفاده محققین تحقیق در عملیات قرار گرفته است. در این تحقیق با تركیب دو الگوریتم كلونی مورچگان و الگوریتم ژنتیك سعی شده است الگوریتم تركیبی ساخته شود كه تور بهتری را برای مسئله فروشنده دوره گرد بدست آورد. پس از طراحی الگوریتم، تنظیم پارامترهای آن با حل مسائل متعدد صورت گرفته است و برای مقایسه روش پیشنهادی با روشهای الگوریتم ژنتیك و مورچگان برخی از مسائل حل شده است. نتایج بدست آمده نشان می دهد كه روش تركیبی پیشنهادی tsp فروشنده دوره گرد موجود در سایت در اغلب مسائل قادر است جواب بهتری بدست آورد.

    وازه های كلیدی
    فروشنده دوره گرد، الگوریتم تركیبی، الگوریتم كلونی مورچگان، الگوریتم ژنتیك
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  16. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  17. #9
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

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

    [DOWN]http://dl.azardl.com/sh/moorche.pdf[/DOWN]
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  18. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


  19. #10
    عضو سایت
    گاه برای ساختن باید ویران کرد، گاه برای داشتن باید گذشت ، و گاه در اوج تمنا باید نخواست!
    تاریخ عضویت
    Jun 2011
    محل سکونت
    یک خانه
    نوشته ها
    25,040
    تشکر تشکر کرده 
    3,527
    تشکر تشکر شده 
    5,275
    تشکر شده در
    3,184 پست
    حالت من : Akhmoo
    قدرت امتیاز دهی
    4452
    Array

    پیش فرض

    يک شبکه عصبی فازی ژنتيکی جديد برای حل مسأله فروشنده دور ه گرد

    [DOWN]http://dl.azardl.com/sh/icee_533.pdf[/DOWN]
    [دل خوش از آنیم که حج میرویم؟ ..]
    غافل از آنیم که کج میرویم



    [SIGPIC][/SIGPIC]


  20. 3 کاربر مقابل از shirin71 عزیز به خاطر این پست مفید تشکر کرده اند.


صفحه 1 از 3 123 آخرینآخرین

برچسب ها برای این تاپیک

علاقه مندی ها (بوک مارک ها)

علاقه مندی ها (بوک مارک ها)

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست در پست خود ضمیمه کنید
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  

http://www.worldup.ir/