Question

The solution to the Traveling Salesperson Problem using Exhaustive Search is 0 (_ _) ? Ž Z Z

Answer 1

ANSWER

1) correct option is O(n!)

EXPLANATION:

when we exhaustive search, let say we have n cities, then taking 1 city as the starting point, we will have to produce as many as (n-1)! permutations of all other cities,we will have to look for the cost of each of the (n-1)! permutations and keep track of the minimum costing permutation of all,then finally we will return the permutation with the minimum cost, so we can clearly see, in exhaustive search, the complexity will rise up to O(n!) .

2) correct option is O(NM)

EXPLANATION:

suppose text=AAAABABSASSDSSHSSSAAAABAAAAAABAAAAAA (of length N)

Pattern = AAAAA (of length M)

so in brute force it compares pattern to each string of length M ,one by one, leading to total number of comparisions to rise up to = M*(N-M+1)

STEP 1:

text = AAAABABSASSDSSHSSSAAAABAAAAAABAAAAAA (of length N)

Pattern = AAAAA (of length M)

STEP 2:

text = AAAABABSASSDSSHSSSAAAABAAAAAABAAAAAA (of length N)

Pattern = AAAAA (of length M)

STEP 3:

text = AAAABABSASSDSSHSSSAAAABAAAAAABAAAAAA (of length N)

Pattern = AAAAA (of length M)

similarly.....it will have total M(N-M+1) comparisons, where N >M,

M(N-M+1) = MN - M² + M (for complexity calculation we consider only the upper bound)

so, worst case complexity will be = O(MN),

THANK YOU....!!!