Browse Prior Art Database

New Search Algorithm Based on Compiled Constraints

IP.com Disclosure Number: IPCOM000105438D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 46K

Publishing Venue

IBM

Related People

Lee, HS: AUTHOR [+3]

Abstract

It is an expanded search algorithm, called Constraint Compiled Graph (CCG search algorithm, for finding global solutions of the labelling problems, where constrains are n-ary and are not necessarily decomposable into binary constraints.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 62% of the total text.

New Search Algorithm Based on Compiled Constraints

      It is an expanded search algorithm, called Constraint Compiled
Graph (CCG search algorithm, for finding global solutions of the
labelling problems, where constrains are n-ary and are not
necessarily decomposable into binary constraints.

      Previous augmentations of backtrack search techniques such as
forward checking[*] have focused on improvements utilizing only
binary constraints.  With n-ary constraints, however, it is very time
consuming to retrieve them.  This invention extends the state of the
art with an algorithm that effectively utilizes n-ary constraints
within the forward checking paradigm.

      To support processing n-ary constraints and expedite the search
process, the CCG search algorithm precompiles all constraints, given
and derived into a Constraint Compiled Graph, as an alternative to
decomposing them into binary constraints, which is not in general
possible.

      CCGs are graph data structures enabling efficient search, by
facilitating retrieval of constraints and their domain-variable
arguments.  They consist of nodes and arcs.  In CCGs, constraints are
embedded in nodes in such a manner that retrieval of relevant
constraints when given a variable is just a matter of traversing
pointers along arcs.  Similarly, finding related variables given an
n-ary constraint is also a matter of traversing pointers.  As a
result, a considerable amount of time needed for finding relat...