Search your notes, the web, or the library to summarize each of the following mechanisms in 2 to 5 lines. It is very important to list your references.

Glossary 7, unlike other glossaries, requires you to define techniques. Such questions can typically appear in an exam such as the PhD qualifier in this department. Please provide as much detail as possible. Note that each item is graded with 3 points to reflect the importance of providing detailed explanations.

More generally, when asked about a technique, you should provide as much detail as possible:

• data structures it needs
• mechanism
• formal properties: termination, soundness, completeness, optimality (when applicable), complexity, other?
• list of (positive and negative) features with respect to other mechanisms such as:
  • the type of applications where the technique is appropriate to use,
  • the situations under which the techique's behavior degenerates,
  • etc.

1. Anytime algorithm
2. Binary search (for optimization)
3. Branch and bound search (for optimization)
4. Breakout methd (in local search)
5. Credit-based backtrack search
6. ERA
7. Genetic algorithms
8. Greedy local search
9. Least commitment principal
10. Limited discrepancy search
11. Random walk
12. Restart strategy
13. Simulated annealing
14. Tabu search