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
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Parallel Lookahead Technique for Constraint Satisfaction

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. If a specific binding decision is made for free variable Xi, the effect is to constrain the value of remaining free variables and a revised Feasible_Value table is computed. When procedure Look_Ahead_Search is first called, Current is set to 1 for variable Xi, and at the ith level variable Xi is assigned. The algorithm begins with no variable having any of its values inconsistent with previously assigned variable value pairs. The algorithm selects the next value from the list of feasible values for the current variable, which is guaranteed consistent with all previously assigned variable value pairs. The Parallel Lookahead algorithm tries to check whether any remaining free variables would become infeasible, i.e., have no value consistent with the current variable value pair. If each free variable has consistent values, it copies all consistent variable value pairs into the Feasible_Value table for the next level. If every free variable has some value in the table consistent with the current pair, then the tree search advances to the next variable.

Should there be some free variable having no value in the tabl...