Traveling salesman problem
This is the problem:
A student is employed as a courier in a firm with n points where he has to deliver products on time.
The salary of the courier is fixed and does not depend on the length of the journey. To estimate the total cost of the journeys. The task is to find the following travel route,
which passes through each point only once and whose total cost of travelling around the points is the lowest,
i.e. so that the student makes more profit. The starting and end point of the student's journey is always the first point.
The data is written in the text file 'U3.txt'. The first line of the file is an integer n (5 ≤ n ≤
50), indicating the size of the square matrix. The following lines contain the matrix K(n,n), which lists
the cost of travel between individual points, where K[i,j]=K[j,i] and represents the cost of travel between points i and j. Derive
the results listing the points in the order in which they were visited and the cost of the journey.
Data:
5
0 1 3 4 2
1 0 4 2 6
3 4 0 7 1
4 2 7 0 7
2 6 1 7 0
Results:
1, 5, 3, 2, 4, 1 = 13
Code is in the pictures attached, over the char limit for the message.
The code outputs these results:
Minimum cost: 13
Path: 5 -> 4 -> 3 -> 2 -> 1 -> 1
How do i need to alter the code so that it outputs the results in this state: 1, 5, 3, 2, 4, 1
13 Replies
'pretty much the required result'
Aka just wrong?
the numbers are all there but ye its wrong
after altering the code a bit i got to these results
Path: 1 -> 5 -> 3 -> 4 -> 2 -> 1
if 4 is swapped places with 2 its the result im looking for but its still wrong
You made it sound like it's a printing order problem. But it's your main algo that's wrong, correct?
yes, my bad, changed the post
Is it just that you didn't fix the first point to be 1?
if i fix the first and last point to be 1 this is the outputted result: Path: 1 -> 5 -> 4 -> 3 -> 2 -> 1; when it should be 1, 5, 3, 2, 4, 1
You should debug your code and look at why your code is picking 5 > 4, because that is very expensive
I think your cost is wrong
You're only adding cost at the final step ... That cannot be right
I also don't think you're even adding the right cost at that point
the minimum cost matches up with the problems solution minCost, however the path doesnt, so im confused to say the least, the problem requires me to use a recursive function which im not too familiar with
What even is your Array.Copy doing?
you're just copying something to itself
forgot i left that there, was testing things and forgot to remove it
I suggest you print out the path and the cost everytime you complete a path, and also print out when ever the 'best' path is updated.
since n is 5 isnt there 120 different paths it can take ?
you've got 1...1, and ... has 4! combinations, right?
either way, 120 not that many to have a quick look over