Please Answer ALL THE QUESTIONS Artificial I ntelligence Assignment #2 1. I mple
ID: 2246372 • Letter: P
Question
Please Answer ALL THE QUESTIONS
Explanation / Answer
One of the algorithm for finding the solution of tsp 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 mutiplr 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.