A dynamic constraint-directed ordered search algorithm for solving constraint satisfaction problems

ABSTRACT

Many engineering problems such as Job Shop Scheduling can be categorized as constraint satisfaction problems. We propose the Dynamic Constraint-directed Ordered Search (DCOS) to solve such problems. DCOS repeatedly re-arranges the search order of the variables and eliminates its local inconsistencies by using a low order network consistency algorithm. As a result, it reduces the width of the search tree. The reduction of the width of the search tree causes the decrease in the number of backtrackings required to find the solution. We have applied DCOS to the Graph Coloring Problem and the Zebra Problem with a second order network consistency algorithm and obtained almost-backtrack-free searches for both cases.

REFERENCES

• BIT 76: James R. Bitner , Edward M. Reingold, Backtrack programming techniques, Communications of the ACM, v.18 n.11, p.651-656, Nov. 1975 [doi>10.1145/361219.361224]
• DEC 86: Dechter, R., "Learning whiler Searching in Constraint Satisfaction Problems", Technical Report gCSD-860049, Computer Science Dept, UCLA, 1986.
• DEC 87: Dechter, R., "An Integrated Strategy for Improved Backtrack", Technical Report R-77, Computer Science Dept, UCLA, January 1987.
• FRE 78: Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
• FRE 82: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• MAC 77: Mackworth, A.K., "Consistency in Networks of Relations", Artificial Intelligence 8, 1977, 99-118.
• MAC 85: Alan K. Mackworth , Eugene C. Freuder, The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, v.25 n.1, p.65-74, Jan. 1985 [doi>10.1016/0004-3702(85)90041-4]
• MON 74: Montanari, U., "Networks of Constraints: Fundamental Properties and Applications to Picture Processing", Information Sciences 7, 95-132, 1974.
• PUR 81: Purdom, P.W. Jr., Brown, C.A., and Robertson, E.L., "Backtracking with Multi-Level Dynamic Search Rearrangement'', Acta Informatica 15, 99-113, 1981.
• STO 86: Stone, H.S., "Efficient Search Techniques -- An Empirical Study of the N-Queens Problem", RC 120557 (#54343), IBM T.J. Watson Research Center, Yorktown Heights, NY, 8/6/86.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Design