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

[kia749]

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

[manvaputra]

دوست عزیز سلام برای اینطور مسائل اگر الگوریتم برنامه رو بدونین راحت میشه پیاده سازیش کرد!

[kpour2001]

Problem: Determine an optimal tour in a weighted, directed graph. The weights are nonnegative numbers.
Inputs: a weighted, directed graph, and n, the number of vertices in the graph. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W [i] [j] is the weight on the edge from ith vertex to the jth vertex.
Outputs: a variable minlength, whose value is the length of an optimal tour, and a two-dimensional array P from which an optimal tour can be constructed. P has its rows indexed from 1 to n and its columns indexed by all subsets of V − {v1}. P [i] [A] is the index of the first vertex after vi on a shortest path from vi to v1 that passes through all the vertices in A exactly once.
void travel (int n,
const number W [] [],
index P [] [],
number & minlength)
{
index i, j, k;
number D [1 .. n] [subset of V - {v1}];

for (i = 2; i <= n; i++)
D [i] [⊘] = W[i] [1];
for (k = 1; k <= n - 2; k++)
for (all subsets A ⊆ V - {v1} containing k vertices)
for (i such that i ≠ 1 and vi is not in A){
D [i] [A] = minimum (W [i] [j] + D [j [A - {vj}]);
j: [vj ∊ A
P[i] [A] = value of j that gave the minimum;
}
D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]);
2 ≤ j ≤ n
P[1] [V - {v1}] = value of j that gave the minimum;
minlength = D[1] [V - {v1
}
}

[vcldeveloper]

این مسئله قبلا به دفعات در بخش الگوریتم ها توضیح داده شده.
به علت نامرتبط بودن با دلفی، منتقل میشه به بخش الگوریتم ها.