18 juillet 20193 août 2020 Patrick Meyer We consider the greedy algorithm that always choose to jump to the closest unexplored vertex to solve the TSP. Which of the following statements is true? The solution found by a greedy algorithm is always optimal. The solution found by a greedy algorithm may or may not be optimal. The solution found by a greedy algorithm is never optimal. Which of the following routes can be obtained when applying a greedy algorithm that jumps to the closest vertex and starts from vertex v0? v0 → v1 → v2 → v3 → v4. v0 → v4 → v1 → v3 → v2. v0 → v3 → v1 → v4 → v2. Consider the problem of finding a longest path in a given weighted graph, starting at vertex u. To solve it, we can adopt the greedy approach of systematically choosing an unexplored edge {v, v'} of maximum weight from the current vertex we are in, v, then jumping to the corresponding vertex v', until there are no such edges left. Which of the following statements are true? This greedy algorithm is optimal (it always outputs the longest path). This greedy algorithm outputs a path starting at u. This greedy algorithm always finishes (it cannot iterate endlessly). A Pareto optimal is... a solution that minimizes both speed and correctness. an optimal trade-off between speed and correctness. a solution that maximises correctness, irrespective of speed. a solution that maximizes both speed and correctness. We consider the use of a backtracking algorithm to solve the TSP. Which of the following statements are true? On a weighted graph in which all weights are equal, backtracking will be at least as costly as a bruteforce search. If interrupted before the end, a solution estimated by backtracking will always be inferior to the true answer. The order in which vertices are explored has an important influence on overall execution time. Time is Up!
