Branch & Sample: A simple strategy for constraint satisfaction. (English) Zbl 0677.68102
Summary: Many constraint satisfaction problems have too many solutions for exhaustive generation. Optimization techniques may help in selecting a small number of solutions for consideration, but a reasonable measure of optimality is not always at hand. A simple algorithm called Branch & Sample is suggested as an alternative to optimization. Combining breadth- first and depth-first search Branch & Sample finds solutions distributed over the search tree. The aim is to obtain a limited set of solutions that corresponds well to the intuitive notion of a representative, uniformly scattered sample. A precise definition of this notion is discussed in relation to the algorithm whose effect is illustrated by two geometric design problems. The performance of the algorithm is evaluated and it is concluded that Branch & Sample is applicable to certain types of problems, and refinements can extend the scope of application.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T99 | Artificial intelligence |
| 68P10 | Searching and sorting |
| 68U99 | Computing methodologies and applications |
Keywords:
backtracking; combinatorial explosion; similarity function; automated design; constraint satisfactionReferences:
| [1] | P. Galle,Computer methods in architectural problem solving: Critique and proposals. Journal of Architectural and Planning Research 6, 1 (Spring 1989). |
| [2] | P. Galle,A Formalized Concept of Sketching in Automated Floor Plan Design (With an appendix, ”Abstraction as a Tool of Automated Floor Plan Design”, reprinted from Environment and Planning B 1986), DIKU, Department of Computer Science, University of Copenhagen, diss., DIKU-report* no. 87/3 (1987 a). |
| [3] | P. Galle,A Basic Problem Definition Language for Automated Floor Plan Design, DIKU, Department of Computer Science, University of Copenhagen, diss., DIKU-report* no. 87/4 (1987 b). |
| [4] | E. M. Reingold, J. Nievergelt, and N. Deo,Combinatorial Algorithms: Theory and Practice, Prentice-Hall, Englewood Cliffs, New Jersey (1977). · Zbl 0367.68032 |
| [5] | N. J. Nilsson,Principles of Artificial Intelligence, Tioga Publishing Co., Palo Alto, Calif. (1980). · Zbl 0422.68039 |
| [6] | E. Rich,Artificial Intelligence, McGraw-Hill, Singapore (1983). |
| [7] | E. L. Lawler and D. E. Wood,Branch-and-bound methods: a survey, Operations Research 14, 699–719 (1966). · Zbl 0143.42501 · doi:10.1287/opre.14.4.699 |
| [8] | L. B. Kovács,Combinatorial Methods of Discrete Programming, Akadémiai Kiadó, Budapest (1980). |
| [9] | D. S. Nau, V. Kumar, and L. Kanal,General branch and bound, and its relation to A* and AO*, Artificial Intelligence 23, 29–58 (1984). · Zbl 0537.68064 · doi:10.1016/0004-3702(84)90004-3 |
| [10] | A. Nozari and E. E. Enscore Jr.,Computerized facility layout with graph theory, Computers and Industrial Engineering 5, 3, (1981), 183–193. · doi:10.1016/0360-8352(81)90004-8 |
| [11] | T. Jespersen,Datamatstottet pladsdisponering til bygningsdesign (in Danish), DIKU, Department of Computer Science, University of Copenhagen, unpublished thesis no. 86-2-2 (1986). |
| [12] | P. Galle,Branch & Sample: Systematic Combinatorial Search without Optimization, DIKU, Department of Computer Science, University of Copenhagen, diss., DIKU-report* no. 87/5 (1987 c). |
| [13] | R. Rammal, G. Toulouse, and M. A. Virasoro,Ultrametricity for physicists, Reviews of Modern Physics 58, 3, 765–788 (1986). · doi:10.1103/RevModPhys.58.765 |
| [14] | J. R. Bitner and E. M. Reingold,Backtrack programming techniques, Communications of the ACM 18, 11, 651–656 (November 1975). · Zbl 0313.68026 · doi:10.1145/361219.361224 |
| [15] | A. K. Mackworth,Consistency in networks of relations, Artificial Intelligence 8, 99–118 (1977). · Zbl 0341.68061 · doi:10.1016/0004-3702(77)90007-8 |
| [16] | P. W. Purdom, Jr., C. A. Brown, and E. L. Robertson,Backtracking with multi-level dynamic search rearrangement, Acta Informatica 15, 99–113 (1981). · doi:10.1007/BF00288958 |
| [17] | M. Bruynooghe,Solving combinatorial search problems by intelligent backtracking, Information Processing Letters 12, 1, 36–39 (Feb. 1981). · doi:10.1016/0020-0190(81)90074-0 |
| [18] | E. C. Freuder,A sufficient condition for backtrack-free search, Journal of the ACM 29, 1, 24–32 (Jan. 1982). · Zbl 0477.68063 · doi:10.1145/322290.322292 |
| [19] | E. C. Freuder,A sufficient condition for backtrack-bounded search, Journal of the ACM 32, 4, 755–761 (Oct. 1985). · Zbl 0633.68096 · doi:10.1145/4221.4225 |
| [20] | W. A. Kornfeld,Combinatorially implosive algorithms, Communications of the ACM 25, 10, 734–738 (Oct. 1982). · Zbl 0491.68061 · doi:10.1145/358656.358678 |
| [21] | B. Nudel,Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics, Artificial Intelligence 21, 135–178 (1983). · doi:10.1016/S0004-3702(83)80008-3 |
| [22] | R. Dechter and J. Pearl,The cycle-cutset method for improving search performance in AI applications, Proc. 3rd IEEE Conference on Artificial Intelligence Applications, Orlando, FL., 224–230 (1987). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
