سلام مهمان گرامی ، خوش آمدید. آیا این نخستین بازدید شماست ؟ وارد شده یا عضو شوید

انجمن های تخصصی علوم رایانه و هنرهای دیجیتال



مسئله فروشنده دوره‌گرد (Travelling salesman problem : TSP )
زمان کنونی: 24-09-2017، 12:27 AM
کاربرانِ درحال بازدید از این موضوع: 1 مهمان
نویسنده: Mohsen Omidvar
آخرین ارسال: seyyedvahid
پاسخ 5
بازدید 5120
محبوب کنید:

امتیاز موضوع:
  • 2 رأی - میانگین امتیازات: 5
  • 1
  • 2
  • 3
  • 4
  • 5
مسئله فروشنده دوره‌گرد (Travelling salesman problem : TSP )
#1
در این تاپیک مسئله فروشنده دوره گرد را به روش های مختلف حل می کنیم

[تصویر:  290px-Salesman.PNG]
طرح مسئله

تعدادی شهر داریم و هزینه (مسافت) مسافرت به هر یک از آنها مشخص است به دنبال کم هزینه ترین مسیر هستیم بطوریکه از همه شهرها فقط یکبار عیور کنیم و مجددا به محل شروع بازگردیم
اگر فروشنده دوره‌گرد از نقطه 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
بهبود تصادفی
----------------------------------------------
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید* 
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
خورشید باش که اگر خواستی بر کسی نتابی نتوانی.
پاسخ
 سپاس شده توسط Ehsan ، razer ، Farzad
#2
مقاله ای كامل در مورد مسئله فروشنده دوره گرد با فرمت پی دی اف

تاريخچه ، تجزيه و تحليل و پیاده سازي مسئله فروشنده دوره گرد 

*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
زبان : انگلیسی
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
خورشید باش که اگر خواستی بر کسی نتابی نتوانی.
پاسخ
 سپاس شده توسط Ehsan
#3
[تصویر:  images1.jpg]
مسأله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP)، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.

سه روش کلی برای کد کردن راه حل های مسأله TSP ارائه شده است که در الگوریتم های مختلفی قابل استفاده هستند. راه حل های سه گاه عبارتند از:

الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم های زیر قابل استفاده است: الگوریتم های ژنتیک یا Genetic Algorithms (به اختصار GA) شبیه سازی تبرید یا Simulated Annealing (به اختصار SA) جستجوی ممنوعه یا Tabu Search (به اختصار TS) جستجوی همسایگی متغیر یا Variable Neighborhood Search (به اختصار VNS) بهینه سازی کلونی مورچگان یا Ant Colony Optimization (به اختصار ACO) جستجوی هارمونی یا Harmony Search (به اختصار HS) و سایر الگوریتم های بهینه سازی گسسته

ب) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم های زیر قابل استفاده است: الگوریتم های ژنتیک یا Genetic Algorithms (به اختصار GA) بهینه سازی ازدحام ذرات یا Particle Swarm Optimization (به اختصار PSO) الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm (به اختصار ICA) تکامل تفاضلی یا Differential Evolution (به اختصار DE) بهینه سازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization (به اختصار BBO) استراتژی های تکاملی یا Evolution Strategies (به اختصار ES) برنامه ریزی تکاملی یا Evolutionary Programming (به اختصار EP) و سایر الگوریتم های بهینه سازی پیوسته

پ) نمایش جواب به شکل ماتریس های شبیه فرومون که توسط تمامی الگوریتم های اشاره شده در مورد (ب) قابل استفاده می باشد.

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

کد:
#include<stdio.h>
#include<conio.h>

#define ALL -1
#define MAXCITIES 10

enum BOOL{FALSE,TRUE};
long*visited;
long*min_circuit;
long*ham_circuit;
long min_circuit_length;
int n;
long matrix[MAXCITIES][MAXCITIES];
long INFI;

void reset_min_circuit(int s_v_id)
{
        min_circuit[0]=s_v_id;
          for(int i=1;i<n;i++)     min_circuit[i]=-1;
}

void set_visited(int v_id,BOOL flag)
{
        if(v_id==ALL)
        for(int i=0;i<n;i++)     visited[i]=flag;

        else                 visited[v_id]=flag;
}

void SET_HAM_CKT(long pl)
{

        ham_circuit[0]=pl;

        for(int i=0;i<n;i++)
        ham_circuit[i+1]=min_circuit[i];
        ham_circuit[n+1]=min_circuit[0];
}

long get_valid_circuit(int s_v,int s_n_v)
{
        int next_v,min,v_count=1;
        long path_length=0;
        min_circuit[0]=s_v;
        min_circuit[1]=s_n_v;
        set_visited(s_n_v,TRUE);
        path_length+=matrix[s_v][s_n_v];

        for(int V=s_n_v;v_count<n-1;v_count++)
        {           min=INFI;

                    for(int i=0;i<n;i++)

                        if (matrix[V][i]<INFI && !visited[i]
                                && matrix[V][i]<=min
                          )                           )
                                min=matrix[V][next_v=i];

            set_visited(next_v,TRUE);
            V=min_circuit[v_count+1]=next_v;
            path_length+=min;
        }
        path_length+=matrix[min_circuit[n-1]][s_v];
        return(path_length);
}

void main()
{
        clrscr();
        printf("Make sure that infinity value < sum of all path distances\nSet Infinity at (signed long):");
        scanf("%ld",&INFI);
        int pathcount,i,j,source,dest;
        long dist=0;
        long new_circuit_length=INFI;
        printf("Tedade Shahr ha ra vared Kon (MAX:%d):",MAXCITIES);
        scanf("%d",&n);
        printf("Tetade Masir ha ra vared kon :");
        scanf("%d",&pathcount);
        printf("Enter paths:< source_id destination_id distance >\n ids varying from 0 to %d\n",n-1);
        for(i=0;i<n;i++)

            for(j=0;j<n;j++)
                   matrix[i][j]=INFI;

        for(i=0;i<pathcount;i++)
        {
            printf("[path %d]:",i);
            scanf("%d %d %ld",&source,&dest,&dist);

            if(source!=dest)

                 matrix[source][dest]=matrix[dest][source]=dist;
        }

        visited=new long[n];
        min_circuit=new long[n];
        ham_circuit=new long[n+2];
        min_circuit_length=INFI;

        for(int S_V_id=0;S_V_id<n;S_V_id++)
        {
            for(i=0;i<n;i++)
            {
                    set_visited(ALL,FALSE);
                    set_visited(S_V_id,TRUE);
                    reset_min_circuit(S_V_id);
                    new_circuit_length=get_valid_circuit(S_V_id,i);

                    if(new_circuit_length<=min_circuit_length)
                    SET_HAM_CKT(min_circuit_length=new_circuit_length);

               }
        }

if(min_circuit_length<INFI)
{
        printf("\n\nMinimum circuit length is: %ld\nCircuit is:\n",min_circuit_length);
        for(i=1;i<n+2;i++)
        printf("<%ld> ",ham_circuit[i]);
}

else     printf("\n\nNo hamiltonian circuit !");

getch();
delete []visited;
delete []min_circuit;
delete []ham_circuit;
}
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
خورشید باش که اگر خواستی بر کسی نتابی نتوانی.
پاسخ
 سپاس شده توسط Ehsan
#4
حل مسئله فروشنده دوره گرد با استفاده از الگوریتم ژنتیک :

*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
*شما قادر به دیدن لینک ها نیستید ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید*
خورشید باش که اگر خواستی بر کسی نتابی نتوانی.
پاسخ
#5
سلام جناب امیدوار
برای 10 شهر و در صورتی که مسافت بیبن شهر ها را بصورت یک ماتریس 10*10 داشته باشیم و بخواهیم از دستور sort متلب  استفاده کنم باید چیکار کنم؟ لطفا راهنماییم کنید
پاسخ


پرش به انجمن:


کاربرانِ درحال بازدید از این موضوع: 1 مهمان