Performance of linear-space search algorithms. (English) Zbl 1013.68502
Summary: Search algorithms that use space linear in the search depth are widely employed in practice to solve difficult problems optimally, such as planning and scheduling. In this paper, we study the average-case performance of linear-space search algorithms, including depth-first branch-and-bound (DFBnB), iterative-deepening (ID), and recursive best-first search (RBFS). To facilitate our analyses, we use a random tree \(T (b, d)\) that has mean branching factor \(b\), depth \(d\), and node costs that are the sum of the costs of the edges from the root to the nodes. We prove that the expected number of nodes expanded by DFBnB on a random tree is no more than \(bd\) times the expected number of nodes expanded by best-first search (BFS) on the same tree, which usually requires space that is exponential in depth \(d\). We also show that DFBnB is asymptotically optimal when BFS runs in exponential time, and ID and RBFS are asymptotically optimal when the edge costs of \(T (b, d)\) are integers. If \(bp_0\) is the expected number of children of a node whose costs are the same as that of their parent, then the expected number of nodes expanded by these three linear-space algorithms is exponential when \(bp_0 < 1\), at most \(O(d^4)\) when \(bp_0 = 1\), and at most quadratic when \(bp_0 > 1\). In addition, we study the heuristic branching factor of \(T (b, d)\) and the effective branching factor of BFS, DFBnB, ID, and RBFS on \(T (b, d)\). Furthermore, we use our analytic results to explain a surprising anomaly in the performance of these algorithms, and to predict the existence of a complexity transition in the asymmetric traveling salesman problem.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 90C27 | Combinatorial optimization |
References:
| [1] | Balas, E.; Toth, P., Branch and bound methods, (Lawler, E. L.; etal., The Traveling Salesman Problem (1985), John Wiley and Sons: John Wiley and Sons Essex), 361-401 · Zbl 0568.90068 |
| [2] | Binmore, K. G., (Mathematical Analysis (1982), Cambridge University Press: Cambridge University Press New York) · Zbl 0484.26002 |
| [3] | Chakrabarti, P. P.; Ghose, S.; Acharya, A.; de Sarkar, S. C., Heuristic search in restricted memory, Artif. Intell., 41, 197-221 (1989) · Zbl 0687.68040 |
| [4] | Cheeseman, P.; Kanefsky, B.; Taylor, W. M., Where the really hard problems are, (Proceedings IJCAI-91. Proceedings IJCAI-91, Sydney, Australia (1991)), 331-337 · Zbl 0747.68064 |
| [5] | Crawford, J. M.; Auton, L. D., Experimental results on the crossover point in satisfiability problems, (Proceedings AAAI-93. Proceedings AAAI-93, Washington, DC (1993)), 21-27 |
| [6] | Dechter, A., A probabilistic analysis of branch-and-bound search, (Tech. Report UCLA-ENG-81-39 (1981), Cognitive Systems Lab, School of Engineering and Applied Science, University of California: Cognitive Systems Lab, School of Engineering and Applied Science, University of California Los Angeles, CA) |
| [7] | Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of \(A^∗\), J. ACM, 32, 505-536 (1985) · Zbl 0631.68075 |
| [8] | Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1971) · Zbl 0092.16002 |
| [9] | Erdös, P.; Graham, R. L., On a linear diophantine problem of frobenius, Acta Arithmatica, 21, 399-408 (1972) · Zbl 0246.10010 |
| [10] | Fuller, S. H.; Gaschnig, J. G.; Gillogly, J. J., Analysis of the alpha-beta pruning algorithm, (Tech. Report (1973), Carnegie-Mellon University, Computer Science Department: Carnegie-Mellon University, Computer Science Department Pittsburgh, PA) |
| [11] | Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York) · Zbl 0411.68039 |
| [12] | Gaschnig, J. G., Performance measurement and analysis of certain search algorithms, (Tech. Report CMU-CS-79-124. Tech. Report CMU-CS-79-124, Ph.D. Thesis (1979), Computer Science Department, Carnegie-Mellon University: Computer Science Department, Carnegie-Mellon University Pittsburgh, PA) |
| [13] | Ginsberg, M. L.; Harvey, W. D., Iterative broadening, Artif. Intell., 55, 367-383 (1992) |
| [14] | Hammersley, J. M., Postulates for subadditive processes, Ann. Probability, 2, 652-680 (1974) · Zbl 0303.60044 |
| [15] | Harris, T., (The Theory of Branching Processes (1963), Springer: Springer Berlin) · Zbl 0117.13002 |
| [16] | Hart, T. P.; Nilsson, N. J.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 4, 100-107 (1968) |
| [17] | Huberman, B. A.; Hogg, T., Phase transitions in artificial intelligence systems, Artif. Intell., 33, 155-171 (1987) |
| [18] | Huyn, N.; Dechter, R.; Pearl, J., Probabilistic analysis of the complexity of \(A^∗\), Artif. Intell., 15, 241-254 (1980) · Zbl 0447.68068 |
| [19] | Ibaraki, T., Enumerative Approaches to Combinatorial Optimization—Part I, (Annals of Operations Research, 10 (1987), Scientific: Scientific Basel, Switzerland) |
| [20] | Karp, R. M.; Pearl, J., Searching for an optimal path in a tree with random costs, Artif Intell., 21, 99-117 (1983) · Zbl 0507.68034 |
| [21] | Kingman, J. F.C., The first birth problem for an age-dependent branching process, Ann. Probability, 3, 790-801 (1975) · Zbl 0325.60079 |
| [22] | Korf, R. E., Depth-first iterative-deepening: An optimal admissible tree search, Artif. Intell., 27, 97-109 (1985) · Zbl 0573.68030 |
| [23] | Korf, R. E., Real-time heuristic search, Artif. Intell., 42, 189-211 (1990) · Zbl 0718.68082 |
| [24] | Korf, R. E., Linear-space best-first search, Artif. Intell., 62, 41-78 (1993) · Zbl 0778.68079 |
| [25] | Kumar, V., Search branch-and-bound, (Shapiro, S. C., Encyclopedia of Artificial Intelligence (1992), Wiley-Interscience: Wiley-Interscience New York), 1468-1472 |
| [26] | Kumar, V.; Nau, D. S.; Kanal, L., A general branch-and-bound formulation for and/or graph and game tree search, (Kanal, L.; Kumar, V., Search in Artificial Intelligence (1988), Springer-Verlag: Springer-Verlag New York), 91-130 |
| [27] | Langley, P., Systematic and nonsystematic search strategies, (Proceedings first International Conference on AI Planning Systems. Proceedings first International Conference on AI Planning Systems, College Park, MD (1992)), 145-152 |
| [28] | Larrabee, T.; Tsuji, Y., Evidence for a satisfiability threshold for random 3CNF formulas, (Working Notes of AAAI 1993 Spring Symposium: AI and NP-Hard Problems. Working Notes of AAAI 1993 Spring Symposium: AI and NP-Hard Problems, Stanford, CA (1993)), 112-118 |
| [29] | Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. R.; Shmoys, D. B., (The Traveling Salesman Problem (1985), John Wiley and Sons: John Wiley and Sons Essex) · Zbl 0562.00014 |
| [30] | Lawler, E. L.; Wood, D. E., Branch-and-bound methods: a survey, Operations Research, 14, 699-719 (1966) · Zbl 0143.42501 |
| [31] | Mahanti, A.; Ghosh, S.; Nau, D. S.; Pal, A. K.; Kanal, L. N., Performance of \(IDA^∗\) on trees and graphs, (Proceedings AAAI-92. Proceedings AAAI-92, San Jose, CA (1992)), 539-544 · Zbl 0887.68018 |
| [32] | McDiarmid, C. J.H., Probabilistic analysis of tree search, (Gummett, G. R.; Welsh, D. J.A., Disorder in Physical Systems (1990), Oxford Science), 249-260 · Zbl 0738.60084 |
| [33] | McDiarmid, C. J.H.; Provan, G. M.A., An expected-cost analysis of backtracking and non-backtracking algorithms, (Proceedings IJCAI-91. Proceedings IJCAI-91, Sydney, Australia (1991)), 172-177 · Zbl 0745.68108 |
| [34] | Mitchell, D.; Selman, B.; Levesque, H., Hard and easy distributions of SAT problems, (Proceedings AAAI-92. Proceedings AAAI-92, San Jose, CA (1992)), 459-465 |
| [35] | Niven, I.; Zuckerman, H. S., (An Introduction to the Theory of Numbers (1980), John Wiley and Sons: John Wiley and Sons New York) · Zbl 0431.10001 |
| [36] | Papadimitriou, C. H.; Steiglitz, K., (Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0503.90060 |
| [37] | Patrick, B. G., An analysis of iterative-deepening-\(A^∗\), (Ph.D. Thesis (1991), Computer Science Department, McGill University: Computer Science Department, McGill University Montreal, Que) |
| [38] | Patrick, B. G.; Almulla, M.; Newborn, M. M., An upper bound on the complexity of iterative-deepening-\(A^∗\), Ann. Math. Artif. Intell., 5, 265-278 (1992) · Zbl 1034.68556 |
| [39] | Pearl, J., (Heuristics (1984), Addison-Wesley: Addison-Wesley Reading, MA) |
| [40] | Pearl, J., Branching factor, (Shapiro, S. C., Encyclopedia of Artificial Intelligence (1992), Wiley-Interscience: Wiley-Interscience New York), 127-128 |
| [41] | Pohl, I., Practical and theoretical considerations in heuristic search algorithms, (Elcock, E. W.; Michie, D., Machine Intelligence, 8 (1977), Wiley: Wiley New York), 55-72 |
| [42] | Purdom, P. W., Search rearrangement backtracking and polynomial average time, Artif. Intell., 21, 117-133 (1983) |
| [43] | Ratner, D.; Warmuth, M., Finding a shortest solution for the \(n\) × \(n\) extension of the 15-puzzle is intractable, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 168-172 |
| [44] | Rényi, A., (Probability Theory (1970), North-Holland: North-Holland Amsterdam) · Zbl 0206.18002 |
| [45] | Russell, S., Efficient memory-bounded search methods, (Proceedings ECAI-92. Proceedings ECAI-92, Vienna, Austria (1992)) |
| [46] | Sarkar, U. K.; Chakrabarti, P. P.; Ghose, S.; DeSarkar, S. C., Reducing reexpansions in iterative-deepening search by controlling cutoff bounds, Artif. Intell., 50, 207-221 (1991) · Zbl 0764.68157 |
| [47] | Sen, A. K.; Bagchi, A., Fast recursive formulations for best-first search that allow controlled use of memory, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 297-302 · Zbl 0707.68077 |
| [48] | Smith, D. R., Random trees and the analysis of branch and bound procedures, J. ACM, 31, 163-188 (1984) · Zbl 0625.68032 |
| [49] | Stone, H. S.; Sipala, P., The average complexity of depth-first search with backtracking and cutoff, IBM J. Research Development, 30, 242-258 (1986) · Zbl 0636.68041 |
| [50] | Taylor, L. A.; Korf, R. E., Pruning duplicate nodes in depth-first search, (Proceedings AAAI-93. Proceedings AAAI-93, Washington, DC (1993)), 756-761 |
| [51] | Vempaty, N. R.; Kumar, V.; Korf, R. E., Depth-first vs best-first search, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)), 434-440 |
| [52] | Wah, B. W., \(MIDA^∗\), an \(IDA^∗\) search with dynamic control, (Tech. Report UILU-ENG-91-2216 CRHC-91-9 (1991), Center for Reliable and High-Performance Computing Coordinated Science Lab, College of Engineering, University of Illinois: Center for Reliable and High-Performance Computing Coordinated Science Lab, College of Engineering, University of Illinois Urbana Champaign-Urbana, IL) |
| [53] | Wah, B. W.; Yu, C. F., Stochastic modeling of branch-and-bound algorithms with best-first search, IEEE Trans. Software Engineering, 11, 922-934 (1985) · Zbl 0569.68027 |
| [54] | Williams, C. P.; Hogg, T., Extending deep structure, (Proceedings AAAI-93. Proceedings AAAI-93, Washington, DC (1993)), 152-157 |
| [55] | Zhang, W., Truncated branch-and-bound: a case study on the asymmetric TSP, (Working Notes of AAAI 1993 Spring Symposium: AI and NP-Hard Problems. Working Notes of AAAI 1993 Spring Symposium: AI and NP-Hard Problems, Stanford, CA (1993)), 160-166 |
| [56] | Zhang, W., Analyses of linear-space search algorithms and applications, (Ph.D. Thesis (1994), Computer Science Department, University of California at Los Angeles: Computer Science Department, University of California at Los Angeles Los Angeles, CA) |
| [57] | Zhang, W.; Korf, R. E., An average-case analysis of branch-and-bound with applications: summary of results, (Proceedings AAAI-92. Proceedings AAAI-92, San Jose, CA (1992)), 545-550 |
| [58] | Zhang, W.; Korf, R. E., Depth-first vs. best-first search: New results, (Proceedings AAAI-93. Proceedings AAAI-93, Washington, DC (1993)), 769-775 |
| [59] | Zhang, W.; Pemberton, J. C., Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems, (Tech. Report UCLA-CSD-940003 (1994), Computer Science Department, University of California: Computer Science Department, University of California Los Angeles, CA) |
| [60] | Zhang, W.; Pemberton, J. C., Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems—initial results, (Proceedings AAAI-94. Proceedings AAAI-94, Seattle, WA (1994)) |
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.
