|
Department
of |
|
Susan L. EpsteinThe CUNY Graduate School, Department
of Computer Science and Hunter College, Department
of Computer Science
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Home Publications Collaborators Courses Media Appearances Contact
|
|
GEOMETRIC PROBLEMS (CSP)A geometric problem is constructed by scattering a set of points at random on the Cartesian plane — each point becomes a variable in the problem; a constraints is formed between any pair of variables within some specified distance (D) of each other, with additional constraints added to connect the constraint graph, which is ridden with tightly connected sets of vertices. A geometric problem is described here as <n, k, D, t>. -vt after the parameters indicates that the problems in the file have varying tightness, -vs means varying solvability and -u means that all problems are unsolvable (over-constrained). The results below come from experiments using ACE with variable-ordering heuristic mean domain/dynamic degree. Results using a mixture of heuristics (Advisors) will be reported soon. Results reported were averaged over ACE runs on the first 100 problems in each file. #PROBLEMS indicates how many problems are available on file CONSTRAINT CHECKS indicates the average number of constraint checks. VISITED NODES indicates the average number of nodes visited during search.
|
