C#
C#

help

Root Question Message

Kryca
Kryca2/11/2023
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
phaseshift
phaseshift2/11/2023
'pretty much the required result'
Aka just wrong?
Kryca
Kryca2/11/2023
the numbers are all there but ye its wrong
Kryca
Kryca2/11/2023
after altering the code a bit i got to these results
Kryca
Kryca2/11/2023
Path: 1 -> 5 -> 3 -> 4 -> 2 -> 1
Kryca
Kryca2/11/2023
if 4 is swapped places with 2 its the result im looking for but its still wrong
phaseshift
phaseshift2/11/2023
You made it sound like it's a printing order problem. But it's your main algo that's wrong, correct?
Kryca
Kryca2/11/2023
yes, my bad, changed the post
phaseshift
phaseshift2/11/2023
Is it just that you didn't fix the first point to be 1?
Kryca
Kryca2/11/2023
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
phaseshift
phaseshift2/11/2023
You should debug your code and look at why your code is picking 5 > 4, because that is very expensive
phaseshift
phaseshift2/11/2023
I think your cost is wrong
phaseshift
phaseshift2/11/2023
You're only adding cost at the final step ... That cannot be right
phaseshift
phaseshift2/11/2023
I also don't think you're even adding the right cost at that point
Kryca
Kryca2/11/2023
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
phaseshift
phaseshift2/11/2023
What even is your Array.Copy doing?
phaseshift
phaseshift2/11/2023
you're just copying something to itself
Kryca
Kryca2/11/2023
forgot i left that there, was testing things and forgot to remove it
phaseshift
phaseshift2/11/2023
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.
Kryca
Kryca2/11/2023
since n is 5 isnt there 120 different paths it can take ?
phaseshift
phaseshift2/11/2023
you've got 1...1, and ... has 4! combinations, right?
phaseshift
phaseshift2/11/2023
either way, 120 not that many to have a quick look over
ContactFrequently Asked QuestionsJoin The DiscordBugs & Feature RequestsTerms & Privacy