Generate and Test Algorithm

A Generate and Test Algorithm is a Search Algorithm that generates and tests candidates.

• AKA: Generate-and-Test Algorithm, Candidate Generate-and-Test Algorithm.
• See: Backtracking Algorithm, Constraint Satisfaction Problem Algorithm(CSP).

---

---

References

2008

• (Jones, 2008) ⇒ M. Tim Jones. (2008). “Artificial Intelligence: A Systems Approach." Jones & Bartlett. ISBN:0763773379
  • Generate and Test is the simplest of the algorithms to identify a solution for a CSP. In this algorithm, each of the possible solutions is attempted (each value enumerated for each variable) and then tested for the solution. Since testing each combination of variable within the domain of each value can be extremely slow and inefficient, heuristics can be applied to avoid those combination that are outside of the solution space.

2002

• (Schmidt, 2002a) ⇒ Charles F. Schmidt. (2002). “ARTIFICIAL INTELLIGENCE AND SEARCH." Course: Computation and Cognition.
  • The basic components that are involved in search are:
    • Some way of representing the information that is available at the start of the search, this is usually referred to as the start state and is often symbolized as s0;
    • Some way of advancing the search by generating new information from the given information, these ways of generating new information are often referred to as generators or operators, and, they are thought of as partial functions which take the agent from one state of information to another;
    • Some way of representing the goal as a test that can be evaluated against the agent's state of information at each point in its search.
  • The search procedure is typically referred to as generate and test.

---