Idea Solution:

If the TSP problem is solved by using a dynamic problem algorithm.There are at most O(n*2n) sub problems and each one takes linear time to solve. The total running time is, therefore, O(n2*2n. The time complexity is much less than O(n!) but still exponential. So although it is faster, it is still infeasible for any large n, and it has huge memory requirements for the table.

Views: 29

Reply to This


© 2019   Created by Muhammad Anwar Tahseen.   Powered by

Badges  |  Report an Issue  |  Terms of Service