Hybrid backtrack/lookahead search technique for constraint-satis

Details Hybrid backtrack/lookahead search technique for constraint-satis Hybrid backtrack/lookahead search technique for constraint-satis

1992-02-12

1993-07-13

Fleming, Michael R.

G06F 1518

Patent

active

052281159

ABSTRACT:
A method of solving a constraint-satisfaction problem with a data processor includes the steps of (a) providing a search tree structure (10) representing a plurality (N) of variables (X), the search tree structure having a plurality of levels; (b) searching (L) shallow levels of the search tree structure by employing a backtrack search method wherein (L) is less than or equal to a specified value H; and (c) searching (M) remaining, deeper, levels of the search tree structure by employing a lookahead search method. The step of searching (L) shallow levels of the search tree structure includes a step of binding a set of X.sub.1 through X.sub.H variables each to an element from its domain such that no constraints are violated. The step of searching (M) remaining, deeper, levels of the search tree structure includes the steps of, given the bindings for the set of variables X.sub.1 through X.sub.H, determining for each variable X.sub.i, H<i.ltoreq.N a list of feasible values any one of which could be assigned to X.sub.i ; and storing the lists of feasible values in a Feasible.sub.-- Value table data structure.

REFERENCES:
Artificial Intelligence, vol. 41, No. 3, Jan. 1990, Amsterdam NL, pp. 273-312, "Enhancement Schemes for Constraint Processing: Backjumping . . . ", Rina Dechter.
Journal of the ACM, vol. 12, No. 4, Oct. 1965, New York, US, pp. 516-524, "Backtrack Programming", Solomon Golomb, et al.
"Parallel Lookahead Technique for Constraint Satisfaction", IBM Technical Discl. Bulletin, vol. 31, No. 10, Mar. 1989.
"Estimating the Size of a Backtrack Search During the Search Operation", IBM Technical Disclosure Bulletin, vol. 30, No. 8, Jan. 1988.
"Efficient Search Technique" IBM Tech. Discl. Bulletin, vol. 30, No. 1, Jun. 1987.
A. K. Mackworth, "Consistency in Networks of Relations", Artificial Intelligence, vol. 8, pp. 99-118, 1977.
R. M. Haralick and L. G. Shapiro, "The Consistent Labeling Problem: Part I", IEEE Trans. on Pattern Analysis & Maching Intelligence, vol. PAMI-1 No. 2, Apr. 1979, pp. 173-184.
R. M. Haralick & L. G. Shapiro, "The Consistent Labeling Problem: Part II", IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 2, May 1980, pp. 193-203.
B. A. Nudel, "Consistent-Labeling Problems and Their Algorithms: Expected-Complexities and Theory Based Heuristics", Artificial Intelligence (Special Issue on Search & Heuristics), vol. 21, pp. 135-178, 1983.
E. C. Freuder, "A Sufficient Condition for Backtrack-Free Search", Journal of the ACM, vol. 29, No. 1, 1982, pp. 24-32.
J. R. Bitner and E. M. Reinhold, "Backtrack Programming Techniques", Comm. of the ACM, vol. 18, pp. 651-656, 1975.
R. M. Haralick & G. L. Elliott, "Increasing Tree Search Efficiency for Constraint Satisfaction Problems", Artificial Intelligence, pp. 263-313, 1980.
S. Golomb & L. Baumert, "Backtrack Programming", Jrnl. of the ACM, vol. 12, 1965, pp. 516-524.
D. E. Knuth, "Estimating the Efficiency of Backtrack Programs", Mathematics of Computation, vol. 29, 1975, pp. 121-136.

Affiliated with

Also associated with

Rating

Hybrid backtrack/lookahead search technique for constraint-satis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hybrid backtrack/lookahead search technique for constraint-satis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid backtrack/lookahead search technique for constraint-satis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2319083