فروشنده دوره‌گرد

اگر مساله برای 4 یا 5 روستا طراحی شود، راه‌حل دستی آن چندان دشوار نخواهد بود، اما اگر تعداد روستاها بیش از 10 باشد، آن‌وقت این مساله در زمره مسائل «بسیار دشوار برای حل» قرار خواهد گرفت و بنابراین ارائه یک الگوریتم مناسب برای برنامه‌نویسان اجتناب‌ناپذیر است.

ورودی با یک عدد int مثبت تکی (تعداد روستاها) آغاز می‌شود و روی خطی که حاکی از تعداد حالت‌های آزمون است با یک خط خالی (جاخالی) ادامه می‌یابد.

پس اولین خط هر حالت تست شامل 0< 100<n است که تعداد روستاهای موجود روی نقشه است. برای هر روستا خط ادامه می‌یابد. ادامه خط شامل 2 عدد حقیقی متوالی برای مرتب کردن روستاهاست.

میان هر حالت پی‌در‌پی در آزمایش، یک خط خالی وجود دارد.

برنامه شما برای هر حالت آزمایشی باید یک عدد حقیقی تک به دو مکان اعشاری را چاپ کند:

- طول حداقل مجموع خط‌های جوهری که با تمام روستاها ارتباط دارد.

- خروجی هر دو حالت متوالی باید توسط یک خط خالی جدا شود.

1

3

1.0 1.0

2.0 2.0

2.0 4.0

3.41

A(1.0,1.0)

B(2.0,2.0)

C(2.0,4.0)

ما کشیدن گراف را آغاز می‌کنیم. طول یال AB برابر 41/1 است این مقدار از فرمول زیر به‌دست می‌آید:‌

sqrt(math.pow(b(x)-a(x),2)+math.pow(b(y)-a(y),2

فرمول محاسبه طول بردار برای بردارهای دیگر به‌‌ترتیب برای AC برابر 16/3 و برای BC برابر 2 است. بسیار خب، ما یک گراف وزن‌دار داریم و با توجه به صورت مساله این‌طور برداشت می‌شود که باید تمام شهرها به‌هم وصل شوند (یعنی پیدا کردن یک دور در یک گراف که از همه رئوس بگذرد که در اصطلاح به آن دور همیلتونی می‌گویند) و باید کمترین میزان مصرف جوهر (یا راه پیموده‌شده) را داشته ‌باشیم، پس باید در این گراف کوتاه‌ترین دور را حساب کنیم. پس راه‌حل مساله پیدا کردن کوتاه‌ترین دور همیلتونی است.

شبه کد این برنامه بدین صورت درمی‌آید:

struct{

double x;

double y;

}point;

struct{

point self;

dictionary«point,double» connectedPoint;

}edge;

point points[n];

edge edges[n];

double calculatelength(point p1,point p2){

return sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2));

}

void initializeEdges(point[] points,point current){

edge _edge;

edge.point = current;

foreach(point p in points){

_edge.connectedPoint.add
(p,calculatelength(current,p));

}

}

double calculateShortestPath();

foreach(point p in points){

initializeEdges(points.where(_point=»_point!=p),p);

}

caculateShortesPath();

امیربهاءالدین سبط‌الشیخ