Question

For which of the following situations would it be best to use a heuristic in order to find a solution that runs in a reasonable amount of time? Appending a value to a list of elements, which requires no list elements be examined. Option A,Appending a value to a list of n elements, which requires no list elements be examined. A Finding the fastest route that visits every location among locations, which requires possible routes be examined. Option B,Finding the fastest route that visits every location among n locations, which requires n! possible routes be examined. B Performing a binary search for a score in a sorted list of scores, which requires that fewer than scores be examined. Option C,Performing a binary search for a score in a sorted list of n scores, which requires that fewer than n scores be examined. C Performing a linear search for a name in an unsorted database of people, which requires that up to entries be examined.

Answer 1

Option B — the route that must visit every one of n locations (the traveling-salesman–type problem).

Reason: that problem has factorial (or otherwise superexponential / NP-hard) growth in possible routes, so brute force becomes infeasible quickly and heuristics/approximation algorithms are used to get good solutions in reasonable time. The other tasks are already efficient (append: O(1); binary search: O(log n)) or at worst linear (unsorted linear search: O(n)), where either exact algorithms or different data structures (indexes, hashing) are the better remedy than a heuristic.