Give precise formulations for each of the
following as constraint satisfaction problems:
1. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.
2. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.
3. Hamiltonian tour: given a network of cities connected by roads, choose an order to visit all cities in a country without repeating any.
1. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.
2. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.
3. Hamiltonian tour: given a network of cities connected by roads, choose an order to visit all cities in a country without repeating any.
Give precise formulations for each of the
following as constraint satisfaction problems:
1. Rectilinear floor-planning: find non-overlapping places in a large
rectangle for a number of smaller rectangles.
2. Class scheduling: There is a fixed number of professors and
classrooms, a list of classes to be offered, and a list of possible
time slots for classes. Each professor has a set of classes that he
or she can teach.
3. Hamiltonian tour: given a network of cities connected by roads,
choose an order to visit all cities in a country without
repeating any.