October 10, 2006
Weightage = 20%
Order of visiting nodes
Depth = 0 : A
Depth = 1 : ABCD
Depth = 2 : ABECACBFNDADCHA
Depth = 3 : ABEIBCFNDABABCDCBECAFIG
Depth = 0 : A
Depth = 1 : ADCB
Depth = 2 : ADHCACDNFBABCEA
Depth = 3 : ADHNDCNFBADADCBCDHCANG
Yes, the algorithm is guaranteed to terminate without a CLOSED list as long there exists a path from to the goal node. This is because the algorithm iteratively searches paths of longer lengths. It cannot go down a loop infinitely. If the shortest path to the goal has length L, eventually it will start exploring all paths of length L and find the solution.
The graph after N is expanded.
The estimate is computed by summing up the two lowest allowed values in each row in the cost matrix, and dividing the sum by two. For segments that are known to be in the tour the corresponding cost has to be included. Likewise for segments that have to be excluded, the corresponding cost has to be left out. In the given problem cost of DE, which is 70, is included twice, and cost of AB (10) is not included.
Estimated cost = [(AC + AD) + (BE + BC) + (CA + CD) + (DE + DA) + (ED + EB)]/2
= [(20 + 30) + (30 + 40) + (20 + 30) + (70 + 30) + (70 + 30)]/2
A higher estimate can be found by recognizing that A C D are forming a cycle of length three, or recognizing that in the chosen links nodes C and D have three degrees, and replacing one of these costs by a higher one from that row.
Properties of estimating function
One way of implanting GAs for TSP
Path or Order representation = list the cities in the order visited.
Crossover - select a subtour (substring) from one parent and arrange the remaining cities in the order of the other parent. For example, given two parent tours
P1 = (2,4,7,1,5,9,8,3.6) and
P2 = (4,5,7,2,6,8,1,9,3)
For the above example choosing the subsequences from fourth to seventh city gives the children.
C1 = (x,x,x,1,5,9,8,x,x) and
C2 = (x,x,x,2,6,8,1,x,x)
the remaining cities for C1
are arranged in order as in P2 = (4,
C1 = (1,5,9,8,4,7,2,6,3) and
C2 = (2,6,8,1,4,7,5,9,3)
AD + BD <= AC + BC [marks 1]
Do try this one.