I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.
The Traveling Salesman problem (TSP) is famous. Given a list of cities and the distances in between them, the task is to find the shortest possible tour that starts at a city, visits each city exactly once and returns to a starting city. A particular tour can be described as list of all cities [c1,c2, c3, ... ,cn] ordered by the position in which they are visited with the assumption that you return from the last city to the start.This is a hard problem, that is, there is no known efficient solution for this problem and we are not expecting one any time soon. Your task is to analyze the following brute force approach to solving the problem:
Consider the following algorithm for solving the TSP:
n = number of cities m = n x n matrix of distances between cities min = (infinity) for all possible tours do: find the length of the tour if length < min: min = length store tour
State the worst-case (big-O) complexity of this algorithm in terms of (number of cities)?You may assume that matrix lookup is one step O(1). For deriving big-O here, you need not count the if-statement or the for-loop conditional (i.e., testing to see when the for-loop is done), or any of the initializations at the start of the algorithm.
So far I know that there are 2 statements that will be executed after the if statement and I think there n! permutations of tours. Am I correct so far. How would I figure out the amounts of steps for "find the length of tour"?