رتبه موضوع:
  • 1 رای - 5 میانگین
  • 1
  • 2
  • 3
  • 4
  • 5
مسئله فروشنده دوره‌گرد(Travelling salesman problem، به‌اختصار: TSP )
#1
مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem، به‌اختصار: TSP ) مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.

شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.

تعداد کل راه‌حل‌ها برابر است با 1/2(n-1) برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.

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


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

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


الگوریتم‌های دقیق

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


الگوریتم‌های مکاشفه‌ای

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

منبع
[عکس: matlabOpencv.gif]

« کلاس های آموزش پردازش تصویر با نرم افزار متلب »

جهت کسب اطلاعات بیشتر با شماره تلفن 09130130252 تماس حاصل فرمائید.


«جهت مشاهده سرفصل این دوره کلیک نمایید»
پاسخ
سپاس شده توسط
#2
[عکس: 600px-Weighted_K4.svg.png]
مساله فروشنده دوره گرد (TSP ) یکی از مسائل مشهور بهینه سازی ترکیبی است که اساس آن به این صورت است که یک فروشنده دوره گرد می خواهد بهN شهر برود و کالای خود را به فروش برساند ، به طوری که از هر شهر فقط یک بار عبور کند و تمام شهر ها را رفته باشد و در نهایت کمترین مسیر را طی کرده باشد عکس. دراینجا یک ماتریس فاصله شهر ها (d) وجود دارد که فاصله شهر i از j را با dij نشان می دهد و فاصله شهر i از خودش را با dii نشان می دهیم که مقدار آن صفر است و روی قطر اصلی ماتریس می باشد . یک تور یک جایگشت Π از {n،……۱,۲,} می باشد . هدف مساله فروشنده دوره گرد پیدا کردن جایگشتی است که کمترین طول را دارد. فضای حل مساله TSP با زیاد شدن تعداد شهرها به سرعت افزایش می باشد و دیگر با روشهای برنامه ریزی خطی نمی توان جواب بهینه آن را به دست آورد.

[عکس: TSP_Deutschland_3.png]
از لحاظ مهم بودن و کاربرد بسیار زیاد TSP در مسائل گو.ناگون تا کنون افراد زیادی روی این مساله با روشهای گوناگونی کار کره اند . تاریخ ابداع مساله TSP دقیقا معلوم نیست . ولی برای اولین بار در سال ۱۷۰۰ برای مساله حرکت اسب در شطرنج به کار برده شد و در سال ۱۸۰۰ آقای William Rowan Hamilton در تئوری گراف از مساله فروشنده دوره گرد استفاه کرد .و در سال ۱۸۳۲ در آلمان به نام مساله فروشنده دوره گرد شناخته شد .و در سال ۱۹۳۰ Whitney Hassler ، مساله TSP را در دانشگاه Harvard و Princeton در ایالات متحده معرفی کرد. در سال ۱۹۴۰ آقای M Floodاین مساله را در شرکت RAND در کالیفرنیا مشهور کرد و Dantzig, Fulkerson و Johnson برای اولین بار یک روش به نام روش صفحه برش که قسمتی از برنامه ریزی خطی می باشد را برای حل TSP ارائه کردند .و بدین ترتیب روشهای گوناگونی برای حل ان پیدا شد و مساله کاربرد بیشتری پیدا کرد.و کم کم از سال ۱۹۷۸ به بعد از الگوریتمهای متا هیوریستیک برای حل آن استفاده شد. حل این مساله کاربرد وسیعی در حوزه های مختلف مهندسی از جمله حل انواع مسایل زمانبندی، مسیریابی، جایابی کالا در انبار، جایابی ماشینها در کارگاهها، طراحی مدارات چاپی و.. دارد.
در ادامه لینک دانلود این برنامه قرار داده شده است:

دانلود کد حل مسئله فروشنده دوره گرد توسط الگوریتم ژنتیک (۳۵٫۵ KB)
پسورد: matlabsite.com

منبع
[عکس: matlabOpencv.gif]

« کلاس های آموزش پردازش تصویر با نرم افزار متلب »

جهت کسب اطلاعات بیشتر با شماره تلفن 09130130252 تماس حاصل فرمائید.


«جهت مشاهده سرفصل این دوره کلیک نمایید»
پاسخ
سپاس شده توسط
#3
[عکس: favicon.ico]الگوریتم ژنتیک
یکی از معروفترین الگوریتمهای متاهیوریستیک است که تا کنون کتب و مقالات بسیار زیادی در مورد انواع آن (مثل Sequntial GA، Adaptive GA، Genetic
Programming و ...)، روشهای پیاده‌سازی و بهینه‌سازی در آن منتشر شده است. من
هم مدت زیادی در مورد انواع اپراتورهای بهینه و روشهای نوین پیاده‌سازی GA مطالعه کرده‌ام، که ماحصل یکی از آن مطالعات، پیاده‌سازی مسئله TSP در
الگوریتم ژنتیک بوده است که البته متاسفانه هنوز فرصت تکمیل این پروژه را بدست نیاورده‌ام.
در حال حاضر در این برنامه روشها و امکانات زیر پیاده‌سازی شده‌اند (این برنامه به تدریج تکمیل خواهد گشت):
  • روشهای انتخاب کروموزومها: Roulette wheel, Tournament Random/Unique, Ranking Linear/Biased و ...
  • متدهای ترکیب: 1-point, 2-point, Uniform, GST, GSX, Greedy 1pt, PMX, Circular و ...
  • بهینه‌سازی محلی Sengoku-Yoshihara
  • امکان ذخیره و بازیابی نقشه‌های TSP
  • امکان تعیین و تغییر تمامی پارامترها مثل نرخهای جهش، ترکیب، انتخاب و ... در حین اجرای الگوریتم و به شکل داینامیک
  • امکان
    رسم نمودار پیشرفت الگوریتم بر اساس مقادیر برازش در هر نسل، به منظور
    مقایسه کارایی و کاربرد الگوریتمها در مواردی مانند همگرایی زودرس، همگرایی
    دیررس، تاثیر نرخ جهش و ...
هدف
اصلی از پیاده‌سازی این برنامه مقایسه کارایی الگوریتم Genetic و برخی اپراتورهای بهینه شده، در حالتهای Steady-State و Dynamic بوده است.
دریافت برنامه GATSP 1.7 Beta (حل TSP بوسیله Genetic Algorithm)



منبع
[عکس: matlabOpencv.gif]

« کلاس های آموزش پردازش تصویر با نرم افزار متلب »

جهت کسب اطلاعات بیشتر با شماره تلفن 09130130252 تماس حاصل فرمائید.


«جهت مشاهده سرفصل این دوره کلیک نمایید»
پاسخ
سپاس شده توسط
#4
سورس کدهای الگوریتم فروشنده دوره گرد به زبان های مختلف از جمله c++,matlab,fortran,pascal,java,cشارپ:
Source Code Library: Travelling Salesman Problem (TSP)


این هم یک نمونه پیاده سازی به زبان c++:
کد پی‌اچ‌پی:
#include<stdio.h>
int cost=0;
void get(int a[10][10],int n,int visited[10])
{
int i,j,max,src,dest,wt;
for(
i=1;i<=n;i++)
{
visited[i]=0;
for(
j=1;j<=n;j++)
{
a[i][j]=999;
}
}
max=n*(n-1)/2;
for(
i=1;i<=max;i++)
{
printf("\nEnter source:");
scanf("%d",&src);
printf("\nEnter destination:");
scanf("%d",&dest);
if(
src==0&&dest==0)
break;
else
{

printf("\nEnter the distance:");
scanf("%d",&wt);
a[src][dest]=wt;
a[dest][src]=wt;

}
}
printf("\nCost Matrix");
printf("\n~~~~~~~~~~~\n");
for(
i=1;i<=n;i++)
{
for(
j=1;j<=n;j++)
{
if(
a[i][j]!=999)
printf("%d\t",a[i][j]);
else
printf("0\t");
}
printf("\n");
}
}
 
int least(int c,int n,int a[10][10],int visited[10])
{
int i,nc=999,min=999,kmin;
for(
i=1;i<=n;i++)
{
if((
a[c][i]!=0)&&(visited[i]==0))
{
if(
a[c][i]<min)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
}
if(
min!=999)
cost+=kmin;
return 
nc;
}

void mincost(int city,int n,int a[10][10],int visited[])
{
int i,ncity;
visited[city]=1;
printf("%d->",city);
ncity=least(city,n,a,visited);
if(
ncity==999)
{
ncity=1;
printf("%d",ncity);
cost+=a[city][ncity];
return;
}
mincost(ncity,n,a,visited);
}




void put()
{
printf("\nMinimun cost for visiting all cities:%d\n",cost);
}
main()
{
int n,a[10][10],visited[10];
printf("\nTravelling Salesman Problem Using Branch and Bound");
printf("\n**************************************************");
printf("\n Enter number of Cities:");
scanf("%d",&n);
get(a,n,visited);
mincost(1,n,a,visited);
put();



این هم نمونه ای دیگه:
کد پی‌اچ‌پی:
// CS1410 - Travelling Saleman
// &nbsp;- &nbsp;Bob Nielson
//
// record is 16245.
//
// profitMatrix[i][j] - matrix of profits acheived by moving from city i to city j
// currentRoute &nbsp; &nbsp; &nbsp; - the current planned route
// bestRoute &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;- the best route so far
//
//
// &nbsp;This is the classic travelling salesman problem. &nbsp;A travelling salesman has to
// &nbsp;visit 19 cities in any order. &nbsp;Each city has a profit to be earned by moving
// &nbsp;from a city to a different city. &nbsp;Each movement has a different payoff.
//
// &nbsp;This is a classic CS problem because there are 19! routes to check for the 
// &nbsp;best one. &nbsp;It is impossible to check that many routes in a given amount of 
// &nbsp;time. &nbsp;One has to do the 'best he can'. &nbsp;We are searching for a perfect way
// &nbsp;to solve this. &nbsp;One that will give you the best possible route in a short
// &nbsp;amount of time.
//
// &nbsp;The rules are simple. &nbsp;You are only allowed to change the code in tryRoute. &nbsp;
// &nbsp;No other changes are allowed. &nbsp;
//
// &nbsp;The goal is to achieve the maximium amount of profit in the 60 seconds given.


#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

// creates a random profit matrix
void createProfit(int profitMatrix[20][20]);

// creates a random route
void createRoute(int currentRoute[20]);

// evaluates a route
int evaluateRoute(int currentRoute[20], const int profitMatrix[20][20]);

// trys a new route (you get to play with this function
void tryRoute(int currentRoute[20], int bestRoute[20], const int profitMatrix[20][20]);

// swap swap two items
void swap(int &item1int &item2);

int main()
{
    
// variables used
    
int profitMatrix[20][20];
    
int currentRoute[20];
    
int bestRoute[20];
    
int value=0;
 &
nbsp; &nbsp;int max=0;
    
int i=0;
    
long int start;
    
int kount=0;

    
// create a random environment
    
createRoute(currentRoute);
    
createRoute(bestRoute);
    
createProfit(profitMatrix);

    
// seed the rand number generator
    
srand(time(0));

    
// loop for 60 CPU seconds
    
start=clock();
    while ((
clock()-start)<60000)
    {
 &
nbsp; &nbsp;value=evaluateRoute(currentRouteprofitMatrix);
 &
nbsp; &nbsp;tryRoute(currentRoutebestRouteprofitMatrix);

 &
nbsp; &nbsp;// display every 10000 cycles
 
&nbsp; &nbsp;kount++;
 &
nbsp; &nbsp;if (kount 10000)
 &
nbsp; &nbsp;{
 &
nbsp; &nbspkount=0;
 &
nbsp; &nbspcout << "Current = " << evaluateRoute(currentRoute,profitMatrix) << "\t"
 
&nbsp; &nbsp; &nbsp;<< " Best = " &nbsp; << evaluateRoute(bestRoute,profitMatrix) << "\t"
     
&nbsp;<< " Time = " &nbsp; << (clock()-start)/1000 
     
&nbsp;<< " &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; " << "\r";
 &
nbsp; &nbsp;}
    }

    
// output the best route found in the 60 seconds alloted
    
cout << "\n\n";
    
cout << "Profit is: " << evaluateRoute(bestRoute,profitMatrix) << "\n";
    for (
i=1i<=19i++)
    {
 &
nbsp;cout << bestRoute[i] << "\n";
    }
    
cout << "\n\n";

    
// Grade the route - Hopefully you did great
    
cout << "Grade is: " << int((evaluateRoute(bestRoute,profitMatrix)-14000)*.025+60.00) << "\n";

    return 
0;
}



// tryRoute - tries a route. &nbsp;You get to pick what route to try next.
//
// &nbsp; &nbsp;inputs - currentRoute - the current route plan
// &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - bestRoute &nbsp; &nbsp;- the best route so far
// &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - profitMatrix - the matrix used to calculate the profit for a route
// &nbsp; 
// &nbsp; outputs - currentRoute - update this plan for you current route
// &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - bestRoute &nbsp; &nbsp;- Update this plan for the best route you have seen.
// &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - profitMatrix - Changes to profitMatrix ARE NOT ALLOWED
void tryRoute(int currentRoute[20], int bestRoute[20], const int profitMatrix[20][20])
{
    
    
// variables
    
int planRoute[20];
    
int i;
    
int first;
    
int second;

    static 
long int tries=0// inializes to zero the first time only. (static)
    
    // increments the number of tries.
    
tries++;

    
// copy the current route.
    
for (i=1i<=19i++)
    {
 &
nbsp;planRoute[i]=currentRoute[i];
    }
    
    
// HINT: When is it best to start over?
    // &nbsp; &nbsp; &nbsp; When is it best to try small corrections to a known good route?
    // &nbsp; &nbsp; &nbsp; Maybe you could use the tries counter to see if you have spent
    // &nbsp; &nbsp; &nbsp; &nbsp; to much time on a specific route?


    // 90% of the time start over, otherwise see if we can plan a better route
    // based on the current route.
    
if (rand() < 32767*.90)
    {
 &
nbsp;// random route
 
&nbsp;createRoute(planRoute);
    }
    else
    {

 &
nbsp;// HINT: &nbsp;Do I want to try small changes or massive changes?
 
&nbsp;// &nbsp; &nbsp; &nbsp; &nbsp;To change more than two cities put the following code in a loop!
     
&nbsp;
 &
nbsp;// flip two cities
 
&nbsp;first=rand()%19+1;
 &
nbsp;second=rand()%19+1;
 &
nbsp;swap(planRoute[first],planRoute[second]);
    }

    
// HINT: &nbsp; Do I really want to save a bad route for further analysis?
    // &nbsp; &nbsp; &nbsp; &nbsp; Maybe sometimes, maybe never?

    // save the current route reguardless of whether or not it is better
    
for (i=1i<=19i++)
    {
 &
nbsp;currentRoute[i]=planRoute[i];
    }

    
// save the best one.
    
if (evaluateRoute(currentRoute,profitMatrix) > evaluateRoute(bestRoute,profitMatrix))
    {
 &
nbsp;// reset the tries counter
 
&nbsp;tries=0;

 &
nbsp;// save current route to best route
 
&nbsp;for (i=1i<=19i++)
 &
nbsp;{
     &
nbsp;bestRoute[i]=currentRoute[i];
 &
nbsp;}
    }
}

// evaluateRoute - evaluates a route. 
//
// &nbsp; &nbsp;inputs - route &nbsp; &nbsp; &nbsp; &nbsp;- the current route plan
// &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; - profitMatrix - the matrix used to calculate the profit for a route
// &nbsp; 
// &nbsp; outputs - the profit for the route provided.
//
int evaluateRoute(int route[20], const int profitMatrix[20][20])
{
    
int total=0;

    for (
int i=1i<=18i++)
    {
 &
nbsp;total=total+profitMatrix[route[i]][route[i+1]];
    }
    
total=total+profitMatrix[19][1];
    return 
total;
}


// createRoute - creates a route. 
//
// &nbsp; &nbsp;inputs - route &nbsp; &nbsp; &nbsp; &nbsp;- the current route plan
// &nbsp; outputs - route &nbsp; &nbsp; &nbsp; &nbsp;- a random route.
void createRoute(int route[20])
{
    
int first;
    
int second;
    
int numb;
    
int i;
    
    for (
i=1i<=19i++)
    {
 &
nbsp;route[i]=i;
    }

    
numb=rand()%10+5;
    for (
i=1i<=numbi++)
    {
 &
nbsp;first=rand()%19+1;
 &
nbsp;second=rand()%19+1;
 &
nbsp;swap(route[first],route[second]);
    }
}

// createProfit - creates a random profit matrix.
//
// &nbsp; &nbsp;inputs - profitMatrix - the current profit matrix
// &nbsp; 
// &nbsp; outputs - profitMatrix - a random profit matrix.
//
void createProfit(int profitMatrix[20][20])
{
    for (
int i=1i<=19i++)
    {
 &
nbsp;for (int j=1j<=19j++)
 &
nbsp;{
     &
nbsp;profitMatrix[i][j]=rand()%800+100;
 &
nbsp;}
    }
}

// swap - exchanges two items
void swap(int &item1int &item2)
{
    
int temp=item1;
    
item1=item2;
    
item2=temp;

[عکس: matlabOpencv.gif]

« کلاس های آموزش پردازش تصویر با نرم افزار متلب »

جهت کسب اطلاعات بیشتر با شماره تلفن 09130130252 تماس حاصل فرمائید.


«جهت مشاهده سرفصل این دوره کلیک نمایید»
پاسخ
سپاس شده توسط
#5
سلام جناب مهندس ابراهیمی
بنده روش حل مسائل 8 وزیر و فروشنده دوره گرد با الگوریتم
SMA*
رو میخوام . البته اگه مقدور باشه سورس برنامه رو هم لطف کنید سپاسگذار میشم
پاسخ
سپاس شده توسط
#6
سلام 
خواهشا و لطفا و فوری فوری 
من حل tsp رو به زبان پاسکال می خوام فرقی هم نمی کنه به چه روشی حل بشه فقط سورس کد پاسکالش رو میخوام به اون کتابخانه هم رفتم و پاسکالش رو هم دانلود کردم اما چون نرم افزار پاسکال نداشتم نتونستم سورس کدش را ببینم خواهشا مثل اون سورس کد سی پلاس پلاسی که گذاشتید برای من هم پاسکالش را بگذارید یا به ایمیلم ایمیل کنید بخدا لازمش دارم برای یه کار فوری فوری 
مرسی
پاسخ
سپاس شده توسط


موضوعات مشابه ...
موضوع نویسنده پاسخ بازدید آخرین ارسال
  مسئله کشیش و آدم خوار ها & مسئله های مشابه مهرداد عباسی 1 4,826 04-01-2014, 05:53 PM
آخرین ارسال: مهرداد عباسی
  حل مسئله جورچین با الگوریتم ژنتیک bdb 3 7,718 05-24-2013, 06:00 PM
آخرین ارسال: bdb
  پیاده سازی مسئله 8 وزیر با استفاده از الگوریتم ABC sharokh 2 8,257 12-10-2012, 05:20 PM
آخرین ارسال: FATEMEH1369
  سورس کد مسئله هشت یا n وزیر با الگوریتم ژنتیک با #C مهرداد عباسی 18 50,988 11-23-2012, 10:21 AM
آخرین ارسال: مهدی ابراهیمی

پرش به انجمن:


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