## State-Space Search: Algorithms, Complexity, Extensions, and ApplicationsThis book is about problem solving. Specifically, it is about heuristic state-space search under branch-and-bound framework for solving com binatorial optimization problems. The two central themes of this book are the average-case complexity of heuristic state-space search algorithms based on branch-and-bound, and their applications to developing new problem-solving methods and algorithms. Heuristic state-space search is one of the fundamental problem-solving techniques in Computer Science and Operations Research, and usually constitutes an important component of most intelligent problem-solving systems. The search algorithms considered in this book can be classified into the category of branch-and-bound. Branch-and-bound is a general problem-solving paradigm, and is one of the best techniques for optimally solving computation-intensive problems, such as scheduling and planning. The main search algorithms considered include best-first search, depth first branch-and-bound, iterative deepening, recursive best-first search, and space-bounded best-first search. Best-first search and depth-first branch-and-bound are very well known and have been used extensively in Computer Science and Operations Research. One important feature of depth-first branch-and-bound is that it only requires space this is linear in the maximal search depth, making it very often a favorable search algo rithm over best-first search in practice. Iterative deepening and recursive best-first search are the other two linear-space search algorithms. Iterative deepening is an important algorithm in Artificial Intelligence, and plays an irreplaceable role in building a real-time game-playing program. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

II | 1 |

III | 2 |

V | 4 |

VI | 7 |

VII | 9 |

VIII | 10 |

IX | 11 |

X | 13 |

LVI | 107 |

LVII | 108 |

LIX | 109 |

LX | 110 |

LXI | 112 |

LXII | 114 |

LXIV | 115 |

LXV | 116 |

XI | 14 |

XII | 16 |

XIII | 18 |

XIV | 19 |

XV | 20 |

XVI | 23 |

XVII | 25 |

XVIII | 27 |

XIX | 31 |

XX | 34 |

XXI | 35 |

XXII | 37 |

XXIII | 40 |

XXIV | 41 |

XXV | 45 |

XXVI | 51 |

XXVII | 52 |

XXVIII | 57 |

XXX | 58 |

XXXI | 61 |

XXXII | 62 |

XXXIII | 63 |

XXXV | 67 |

XXXVI | 69 |

XXXVII | 70 |

XXXVIII | 77 |

XXXIX | 81 |

XL | 82 |

XLI | 83 |

XLII | 84 |

XLIV | 86 |

XLV | 87 |

XLVI | 89 |

XLVII | 91 |

XLVIII | 92 |

XLIX | 93 |

LI | 94 |

LII | 96 |

LIII | 103 |

LIV | 104 |

LV | 106 |

LXVI | 117 |

LXVII | 118 |

LXVIII | 120 |

LXIX | 123 |

LXX | 124 |

LXXI | 126 |

LXXIII | 128 |

LXXIV | 130 |

LXXV | 132 |

LXXVII | 136 |

LXXVIII | 139 |

LXXIX | 141 |

LXXX | 142 |

LXXXI | 144 |

LXXXII | 145 |

LXXXIII | 146 |

LXXXV | 147 |

LXXXVI | 148 |

LXXXIX | 149 |

XC | 150 |

XCIII | 156 |

XCIV | 161 |

XCV | 163 |

XCVI | 164 |

XCVII | 165 |

XCIX | 167 |

C | 168 |

CI | 170 |

CIII | 172 |

CIV | 173 |

CV | 175 |

CVIII | 177 |

CIX | 178 |

CXI | 180 |

CXII | 181 |

CXIII | 182 |

CXIV | 185 |

CXV | 186 |

CXVI | 187 |

197 | |

### Common terms and phrases

actual-value pruning alpha-beta pruning and-bound assignment problem assignment problem solution asymmetric Traveling Salesman asymptotically optimal ATSP average number average-case complexity beam search branch-and branching factor branching process Chapter child node combinatorial optimization combinatorial optimization problems complete forward pruning complete tour complexity transitions computation DFBnB distinct intercity distances e-transformation edge costs expected complexity expected number exponential Figure find an optimal included arcs incremental random tree iterative deepening iterative e-DFBnB leaf node Lemma log-normal distribution lower bound minimax minimax value node costs node with cost nodes expanded nodes whose costs NP-hard number of children number of cities number of distinct number of nodes optimal goal cost optimal goal node optimal solution polynomial probability problem instances pruning algorithm recursive best-first search root node search depth search tree simulated annealing solution quality solved space-bounded best-first search state-space tree subproblems subtree tabu search Theorem total number Traveling Salesman Problem truncated depth-first branch-and-bound upper bound variables

### Popular passages

Page 188 - P. Cheeseman, B. Kanefsky, and WM Taylor. Where the really hard problems are.

Page 188 - JM Crawford and LD Auton. Experimental results on the crossover point in satisfiability problems.

Page 194 - Fast recursive formulations for best-first search that allow controlled use of memory. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 (Detroit, MI, Aug.), 297-302.

Page 188 - S. Ghose, A. Acharya, and SC de Sarkar, Heuristic search in restricted memory, Artificial Intelligence, Vol.

Page 195 - S. Zilberstein and SJ Russell. Optimal composition of real-time systems. Artificial Intelligence, 82:181-213, 1996.