In AP Computer Science Principles, an optimization problem is a problem whose goal is finding the "best" solution among many possible solutions, such as the shortest path from A to B (EK AAP-4.A.2). It contrasts with a decision problem, which only asks a yes/no question.
An optimization problem asks for the best answer, not just an answer. The CED's go-to example is pathfinding. "Is there a path from A to B?" is a decision problem (yes or no). "What is the shortest path from A to B?" is an optimization problem, because now you're hunting for the best option among possibly thousands of valid paths.
The "best" is measured by something you're trying to maximize or minimize, like shortest distance, lowest cost, or highest score. Here's the catch that makes this term matter in Topic 3.17: many optimization problems have so many possible solutions that checking every single one would take longer than the age of the universe. The algorithm exists, it just doesn't run in reasonable time. That's exactly when AP CSP says a heuristic, an approach that finds a good enough answer quickly, becomes the smart move.
This term lives in Topic 3.17 (Algorithmic Efficiency) in Unit 3: Algorithms and Programming, under learning objective 3.17.A. That objective asks you to do two things: explain the difference between algorithms that run in reasonable time and those that don't, and identify when a heuristic solution is more appropriate. Optimization problems are the setup for both. EK AAP-4.A.2 explicitly defines the optimization vs. decision problem pair, so the exam expects you to classify a scenario as one or the other. And because brute-forcing an optimization problem (try every arrangement, every route, every combination) often explodes into unreasonable time, optimization problems are the classic situation where you justify using a heuristic instead.
Keep studying AP Computer Science Principles Unit 3
Decision Problem (Unit 3)
These two are defined side by side in EK AAP-4.A.2 and tested as a pair. A decision problem answers yes/no ("Is there a path?"), while an optimization problem ranks the options ("What's the shortest path?"). Same situation, different question.
Heuristic (Unit 3)
When an optimization problem has too many possible solutions to check them all in reasonable time, a heuristic trades the guaranteed best answer for a good answer you can actually compute. Optimization problems are the main reason heuristics exist in the AP CSP framework.
Approximate Solution (Unit 3)
An approximate solution is what a heuristic hands you. It's not provably the best arrangement or the shortest route, but for a hard optimization problem, "close to best, found fast" beats "perfect, found never."
Algorithm (Unit 3)
An optimization problem is a problem (a general task), and an algorithm is a solution method. EK AAP-4.A.1 makes this distinction explicit. Sorting is a problem; sorting the list (2,3,1,7) is an instance; the steps you use to sort it are the algorithm.
This shows up in multiple-choice questions, usually in one of two flavors. The first is classification. You get a scenario like "a developer creates an algorithm to determine if a network of computers can communicate" and have to label it as a decision problem or an optimization problem. The trick is to look at what the question asks for. Yes/no means decision; "best," "shortest," "fastest," or "optimal" means optimization. The second flavor is justification. For example, why would a developer use a genetic algorithm to arrange 50 components on a circuit board instead of trying every possible arrangement? The answer is that the number of arrangements is astronomically large, so checking them all doesn't run in reasonable time, and a heuristic finds a good-enough arrangement quickly. There's no FRQ-style coding task built around this term; it's tested conceptually, in line with how the exam scopes algorithmic efficiency overall.
A decision problem has a yes/no answer, like "Is there a path from A to B?" An optimization problem asks for the best solution among many, like "What is the SHORTEST path from A to B?" The same real-world situation can produce both kinds of problems, so don't classify by topic. Classify by what the question is asking for. If any valid answer satisfies it, it's a decision problem. If you have to compare options to find the best one, it's optimization.
An optimization problem asks for the best solution among many, such as the shortest path from A to B, while a decision problem only asks a yes/no question (EK AAP-4.A.2).
To classify a problem on the exam, look at the question being asked, not the topic. Words like "shortest," "best," or "optimal" signal optimization; "is there" or "does it exist" signals a decision problem.
Many optimization problems can't be solved by checking every possibility because the number of options grows so fast that brute force doesn't run in reasonable time.
When an optimization problem can't be solved exactly in reasonable time, a heuristic that finds an approximate (good enough) solution is the appropriate choice, which is exactly what LO 3.17.A asks you to recognize.
A problem is the general task, an instance includes specific input, and the algorithm is the method that solves it. Optimization problems are one category of problem, alongside decision problems.
It's a problem with the goal of finding the best solution among many possible ones, like the shortest path from A to B. The College Board defines it in EK AAP-4.A.2 under Topic 3.17, Algorithmic Efficiency.
A decision problem has a yes/no answer ("Is there a path from A to B?"), while an optimization problem searches for the best answer ("What is the shortest path from A to B?"). The same scenario can be phrased either way, so always check what the question actually asks for.
No. For many optimization problems, checking every possible solution would take an unreasonable amount of time, so a heuristic that produces an approximate, good-enough solution is the better choice. Recognizing those situations is part of LO 3.17.A.
Because the number of possible solutions explodes. Arranging just 50 components on a circuit board has more possible orderings than could ever be checked one by one, so a genetic algorithm searches for a near-optimal arrangement in reasonable time instead.
Yes. It comes straight from EK AAP-4.A.2, and multiple-choice questions ask you to classify a scenario as one or the other, or to explain why a heuristic fits a hard optimization problem. You won't have to solve an optimization problem mathematically.
Connect this key term to the AP exam workflow: review the course, practice questions, and check related study tools.
Review units, study guides, and course resources.
Check this vocabulary in multiple-choice context.
Apply key concepts in written AP responses.
Estimate the exam score you are working toward.
Review the highest-yield facts before practice.
Put the full course together before test day.