Name
Abstract | ||
|---|---|---|
In constraint satisfaction, a general rule is to tackle the hardest part of a search problem first. In this paper, we introduce a parameter (tau) that measures the constrainedness of a search problem. This parameter represents the probability of a problem being feasible. A value of tau = 0 corresponds to an over-constrained problem and no states are expected to be solutions. A value of tau = 1 corresponds to an under-constrained problem and every state is a solution. This parameter can also be used in heuristics to guide search. To achieve this parameter, a simple random or systematic sampling is carried out to compute the tightnesses of each constraint. New heuristics are developed to classify the constraints from the tightest constraint to the loosest constraint and to remove redundant constraints in constraint satisfaction problems. These heuristics may accelerate the search due to inconsistencies can be found earlier and the absence of such redundant constraints eliminate unnecessary checking and save storage space. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30498-2_13 | ADVANCES IN ARTIFICIAL INTELLIGENCE - IBERAMIA 2004 |
Keywords | Field | DocType |
constraint satisfaction problems,constrainedness,heuristics | Constraint satisfaction,Mathematical optimization,Local consistency,Computer science,Constraint graph,Algorithm,Constraint satisfaction problem,Constraint satisfaction dual problem,Constraint logic programming,Hybrid algorithm (constraint satisfaction),Binary constraint | Conference |
Volume | ISSN | Citations |
3315 | 0302-9743 | 1 |
PageRank | References | Authors |
0.45 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| miguel a salido | 1 | 318 | 38.58 |
| Federico Barber | 2 | 176 | 24.25 |