Skip to main content
main-content

Über dieses Buch

This 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.

Inhaltsverzeichnis

Frontmatter

1. State-Space Search for Problem Solving

Abstract
Search is the primary technique used in Computer Science and Operations Research for solving computation-intensive combinatorial optimization problems, typically those in the NP-hard class [35]. The goal of a search is to quickly find an optimal or near-optimal solution from a finite or infinite but countable set of solutions. The size of the solution space of an NP-hard problem is exponential in term of the problem size in the worst case. Even in an average case, a search algorithm typically explores an exponential number of solutions in order to find an optimal one.
Weixiong Zhang

2. Algorithms for Combinatorial Optimization

Abstract
Given a search space, a search algorithm is a strategy for determining the order in which the nodes are explored. This chapter mainly focuses on search algorithms based on the branch-and-bound paradigm for solving combinatorial optimization problems exactly, i.e., for finding optimal solutions. Specifically, this chapter considers best-first search, depth-first branch-and-bound, and other search algorithms that can be viewed as nontrivial and nonstraightforward extensions of these two algorithms, including iterative deepening [74], recursive best-first search [75] and best-first search using bounded search [16, 127].
Weixiong Zhang

3. Complexity of State-Space Search for Optimal Solutions

Abstract
In the worst case, a state-space search algorithm must explore every node in a state space. Thus the worst-case complexity is linear in the size of the state space. On the other hand, if the lower-bound cost function used by the algorithm is exact, the complexity is linear in the length of the path from the initial node to a goal node. However, these extreme cases rarely occur and thus convey little information about the actual performance of an algorithm. Average-case complexity is therefore a more realistic performance measure. This chapter considers an average-case complexity of a state-space search algorithm. The main purpose of an average-case analysis is to find the relationship between the average-case complexity and the accuracy of lower-bound cost functions used by a search algorithm.
Weixiong Zhang

4. Computational Complexity Transitions

Abstract
The results of Chapter 3 show that the average-case complexity of state-space search algorithms based on branch-and-bound paradigm on random trees experiences a dramatic transition, from exponential to polynomial. This phenomenon is analogous to a phase transitionof a physical or Artificial system [51, 47, 146]. A phase transition is a dramatic change to some problem property as some order parameter changes across a critical point. The simplest example of a phase transition is that in which water changes from a liquid phase to a solid phase when the temperature drops below the freezing point.
Weixiong Zhang

5. Algorithm Selection

Abstract
The complexity measure of search algorithms used in Chapters 3 and 4 is the total number of nodes expanded or generated. However, space and running time are two more practical and important measures for choosing a search algorithm to find an optimal solution of a given problem. We continue our investigation below by taking into account the space and time complexity. The purpose is to provide some guidelines for algorithm selection.
Weixiong Zhang

6. A Study of Branch-and-Bound on the Asymmetric Traveling Salesman Problem

Abstract
One of the approaches for optimally solving the asymmetric Traveling Salesman Problem (ATSP) is branch-and-bound subtour elimination using the assignment problem as a lower-bound cost function [10, 7]. This chapter studies the complexity of branch-and-bound subtour elimination on the asymmetric Traveling Salesman Problem. In Section 6.1, we first examine two-decade old arguments about the expected complexity of branch-and-bound subtour elimination, and shows that the branch-and-bound subtour elimination cannot find an optimal solution to the asymmetric Traveling Salesman Problem in polynomial time on average. This partially settles this long-standing debate on the expected complexity of branch-and-bound on the asymmetric Traveling Salesman Problem. Section 6.4 then compares depth-first branch-and-bound against local search, and shows that depth-first branch-and-bound significantly outperforms a local search algorithm.
Weixiong Zhang

7. State-Space Transformation for Approximation and Flexible Computation

Abstract
Most combinatorial optimization problems are NP-hard, and require computation exponential to the problem size. How can we solve difficult tree-search problems approximately, using the analytical results of their average-case complexity? The answer to this question leads to a new approximation approach, the topic of this chapter. This new method makes use of the complexity transitions of branch-and-bound on incremental random trees, and is referred to as ε-transformation.
Weixiong Zhang

8. Forward Pruning for Approximation and Flexible Computation, Part I: Single-Agent Combinatorial Optimization

Abstract
One of the straightforward methods for speeding up the process of searching for a solution in the large state space of a complex problem is to prune some search alternatives before exploring them. Search methods that use such a pruning mechanism can be categorized as forward pruning methods. Forward pruning can be found in both single-agent and multiagent problemsolving domains. This chapter focuses on single-agent forward pruning, and the next chapter considers forward pruning for multiple-agent game search.
Weixiong Zhang

9. Forward Pruning for Approximation and Flexible Computation, Part II: Multiagent Game Playing

Abstract
The idea of forward pruning is also used in search extension or selective search in multi-agent adversary games. Selective search selectively explores some promising search lines decper than a fixed depth. The most promising search avenues are identified as the ones that have the greatest impact on the decision of the next move. Selective search is one of the major contributing factors in the success of the IBM Deep Blue chess program [3] and the Chinook checkers program [130]. In principle, extending some search branches can be equivalently viewed as eliminating other branches permanently. Therefore, selective search can be viewed as forward pruning. A recent analysis also suggests that forward pruning is effective in the game of bridge [135].
Weixiong Zhang

Backmatter

Weitere Informationen