Problem solving consists of using generic or ad hoc methods, in an orderly manner, for finding solutions to problems.
Computational problem
- Given a positive integer \(n\), find a nontrivial prime factor of \(n\).
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.
- For example, in the factoring problem, the instances are the integers \(n\), and solutions are prime numbers \(p\) that describe nontrivial prime factors of \(n\).
Types of computational problems
A decision problem is a computational problem where the answer for every instance is either yes or no.
- primality testing.
In a search problem, the answers can be arbitrary strings.
- For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.
A counting problem asks for the number of solutions to a given search problem.
An optimization problem asks for finding a "best possible" solution among the set of all possible solutions to a search problem.
In a function problem a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just "yes" or "no".
- One of the most famous examples is the travelling salesman problem.
Solution Space
In search algorithms, a candidate solution is a member of a set of possible solutions to a given problem.
The space of all candidate solutions, before any feasible points have been excluded, is called the feasible region, feasible set, search space, or solution space.
This is the set of all possible solutions that satisfy the problem's constraints.
