Algorithms & Efficiency | AP CSP Daily Practice Day 14
Share
Practice Question
Why B is Correct
This is the Traveling Salesperson Problem, a classic example of an intractable problem. With 15 locations, there are 15! (factorial) = over 1.3 trillion possible routes to check.
A heuristic is an approach that finds a "good enough" solution without guaranteeing the optimal answer. For this problem, heuristics like "nearest neighbor" (always go to the closest unvisited location) can find reasonable routes very quickly.
Why Other Answers Are Wrong
While 15 seems small, 15 factorial equals 1,307,674,368,000 routes. Even checking 1 million routes per second would take over 15 days.
Adding one location multiplies the possibilities by (n+1). Going from 15 to 16 locations increases routes by 16x, not by a fixed amount.
Parallel computing can check routes faster, but the total number of routes remains the same. You still need to check 1.3 trillion routes (just faster).
Problems with factorial or exponential growth are called "intractable" - they cannot be solved optimally in reasonable time. The AP exam expects you to recognize when heuristics are the practical solution.
Completed the 14-Day Rotation!
Great job finishing all 14 practice questions. The rotation starts again tomorrow!
Book Tutoring View All Questions