Hyper-arc consistency in a contraint satisfaction network
US7085748B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 16, 2001 |
| Grant date | Aug 1, 2006 |
| Priority date | — |
| Expiry date | Jul 21, 2023 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/11
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for solving a constraint satisfaction problem includes receiving a set of variables having respective input domains and a set of relations among the variables, and building a network of one or more hyper-arcs representative of the set of relations, each hyper-arc corresponding to one of the relations and linking nodes in the network corresponding to the variables that are subject to the relation. For each of the hyper-arcs, the variables are assembled in a hierarchy based on the relation corresponding to the hyper-arc. The input domains of the variables in the hierarchy are reduced, so as to determine respective output domains of the variables that are consistent with the relations.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.