Search and Optimization
Motivation: A substantial fraction of problems encountered in industry can be formulated as search and optimization problems over a very large space of possible solutions. Examples range from software for solution of logistic problems such as the relocation of goods, over software for web server caching, to software capable of beating Kasparov at chess. Many of these search and optimization problems, but not all, are hard, in the sense that no worst case efficient
algorithm that always finds the optimal solution is known. For these problems, heuristic techniques are often capable of finding satisfactory solutions.
Goal: The goal of this course is to gain experience in
- identifying easy problems which can be solved efficiently and optimally in the worst case.
- identifying hard problems for which this is not the case.
- using algorithmic techniques for dealing with the former and heuristic techniques for dealing with the latter.
Topics: Algorithms for flow and linear programming. The complexity
classes P and NP. NP-hardness and completeness. Analysis of exponential
search procedures. Branch and bound and alpha-beta search. Approximation
algorithms. Local search based heuristics.
Evaluation
Oral examination, 13-scale
Lecturers
Peter Bro Miltersen and Sven Skyum
Credits
2 points/10 ECTS
Semester
Spring