Browse Prior Art Database

Parallel Lookahead Technique for Constraint Satisfaction

IP.com Disclosure Number: IPCOM000034581D
Original Publication Date: 1989-Mar-01
Included in the Prior Art Database: 2005-Jan-27

Publishing Venue

IBM

Related People

Authors:
Natarajan, KS [+details]

Abstract

Constraint satisfaction problems can be solved with improved efficiency in a multiprocessor data handling system by using the Forward Checker Algorithm and scheduling multiple processors in parallel for its execution. In the model of the parallel lookahead tree search algorithm for solutions to a constrains satisfaction problem, variables x1, x2,..., xn are represented by integers 1 through N. "Current" is an integer representing the current level of tree search and is incremented at each level. The tree root is defined Level 1. At Level i, variable Xi, Xi + 1, ..., XN remain to be bound. Associated with each variable Xi is a list fo feasible values, any one of which can be assigned to Xi, and an array of lists of feasible values is a "Feasible_Value" table.