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 method (in local search)
5. Credit-based backtrack search
6. ERA
7. Genetic algorithms
8. Greedy local search
9. Hill climbing
10. Least commitment principal
11. Limited discrepancy search
12. Random walk
13. Restart strategy
14. Simulated annealing
15. Tabu search