1. Implement a genetic algorithm to find a solution to the Traveling Salesman Pr
ID: 3749171 • Letter: 1
Question
1. Implement a genetic algorithm to find a solution to the Traveling Salesman Problem for the following distance matrix 7 19715 18 105 4 1316 3 10 711 Instructions There are 15 cities indicated by 1-15. The distance from city 1 to city 1 is nothing. The distance from city 2 to city 1 is 1. The distance from city 3 to city 1 is 10, and so forth. Write the algorithm in pseudo code or in any notation you want that finds the shortest route to take between the cities. . You do not need to implement the algorithm in a programming language. You are just defining and describing a solution to the Traveling Salesman Problem using the information in the chartExplanation / Answer
The algorithm for finding the solution of travelling salesman problem can be as follows:
1. Select a row with a minimum distance between cities.
2. Select the cell with a minimum value and with the help of the column, get the corresponding city.
3. Look at the row corresponding to the identified(from the column) city in step 2, and again look for the minimum distance cell.
4.Repeat step 2 and 3 till all the cities get covered.
At any step if we get mutiple choice than we need to select the option which gives us the minimum distance out of all the options.
For example
As per the given picture in the question , there are mutiple rows that conatin 1 and there are rows which have multiple entry of minimum distance (i.e 1). So our selection will be in such a way that in the next step we should get the minimum distance possible.
Suppose if we choose row 15 in step 1, and in step 2 we have two choices 11 and 14.if we choose 11, the minimum distance we will be getting in that row is 5 and if we choose 14, again the minimum distance in that row is 5, so in this case we can choose any one of them but in case if we get a difference, we can go for the minimum.
The same approach can be used to obtain the shortest path between two cities.In this case we will be fixing the start and end points as per the requested cities. Also in this case we can start a two way search(applying the steps from both the sities) from both the cities and the moment we get a common city, we can stop the search.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.