 |  |  |
Differences
This shows you the differences between two versions of the page.
|
about:fixed [2010/10/29 01:41] rim |
about:fixed [2023/02/15 12:46] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Fixed complexity problems ====== | ||
| - | Fixed complexity problems are problems in which the only requirement is to find a suitable set of values for a fixed set of parameters. Problems falling into this class include | ||
| - | * Many continuous optimisation problems, where the aim is simply to find real-number values for a set of parameters x1,...,xn that optimise the value of some function f(x1,...,xn) | ||
| - | * Some discrete optimisation problems, where the aim is again to find integer values for a set of parameters x1,...,xn that optimise the value of some function f(x1,...,xn) | ||
| - | * Even many combinatorial problems can be cast in this light | ||
| - | * Linear regression, where the aim is to find a fixed set of linear coefficients relating the variables under consideration | ||
| - | * Simple propositional learning problems generally fall into this class | ||
| - | |||
| - | **Methods for solving such problems include** | ||
| - | * Complete search (depth, breadth first,....) | ||
| - | * Heuristic search (A*, branch and bound,....) | ||
| - | * Stochastic search (simulated annealing, tabu search, genetic algorithms) | ||
| - | |||
| - | While this isn't the primary focus of research in the structural complexity lab, we do some research in these areas from time to time; we tend to be more interested in | ||
| - | * Dynamic problems, where the optimal solution changes with time (so we have done some work on dynamic travelling salesman problems, dynamic ant clustering,...) | ||
| - | * Problems belonging to a family of problems, so tough versions can be solved incrementally from first solving simpler ones | ||