نمایش نتایج 1 تا 13 از 13

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

  1. #1
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

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

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

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

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

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

  2. #2
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208
    با سلام
    دوستان علاقه مند لطفا جهت اطلاع سایر اعضا کاربردهای این الگوریتم را نام ببرید .

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

  3. #3
    کاربر جدید آواتار k.robot
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    ارومیه
    پست
    24
    لطفا وقتی میخوایین چیزی رو به مردم یاد بدین اول خودتون یاد بگرین.با پویا هزینه:
    O(n^2*2^n)

  4. #4
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208
    با سلام

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



    شبه کد الگوریتم فوق بصورت زیر است که در آن تعداد زیر مجموعه های یک مجموعه 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

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

  6. #6
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208
    با سلام
    دوست من شبه کد الگوریتم گذاشته شده زحمت پیاده سازی به عهده خودتون .

    موفق باشید

  7. #7
    منتظر تایید آدرس ایمیل
    تاریخ عضویت
    فروردین 1386
    پست
    19
    اینم یکی از راه حل های مسئله فروشنده دوره گرد که با الگوریتم شبیه سازی تبریدی پیاده سازی شده. از الگوریتم های هوش مصنوعی تو دسته الگوریتم های ژنتیک است

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

  8. #8

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

    با سلام خسته نباشید لطفاَ در مورد docuoments فروشنده دوره گرد توضیحات کامل دهید

  9. #9

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

    خیر کدی ندارم

  10. #10

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

    لطفا اگه كسي بتونه در مورد" موارد كاربرد فروشنده دوره گرد" مقاله اي بذاره... خيلي خيلي ممنون ميشم..

  11. #11
    کاربر تازه وارد آواتار tomboy
    تاریخ عضویت
    آذر 1388
    محل زندگی
    تو دنیا
    سن
    35
    پست
    36

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

    برای کی میخوای؟

  12. #12
    کاربر جدید
    تاریخ عضویت
    اسفند 1390
    محل زندگی
    www.iranbazargan.com
    پست
    6

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



    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


    چی هست ؟
    توضیح هر قسمت؟

  13. #13

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

    كسي هست كه كد اين برنامه رو توي C++‎ داشته باشه؟

قوانین ایجاد تاپیک در تالار

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