17 juillet 20193 août 2020 Patrick Meyer A bruteforce algorithm... is an algorithm that finds solutions by testing all possibilities exhaustively. guaranteed to find exact solutions. is an algorithm that finds the least complex solution without checking if it is correct. A backtracking algorithm for the TSP... iteratively examines the lengths of routes and immediately aborts examination of a route that is longer than the shortest found so far. is guaranteed to find the shortest route. randomly explores only a subset of all routes and outputs the shortest route of the subset, but is not guaranteed to find the shortest route among all possible ones. We consider using a backtracking algorithm for the TSP. Which of the following are true? The complexity of backtracking may be linear for some graphs. The order in which vertices are explored has an important influence on overall execution time. Backtracking is based on a BFS. Time is Up!
