Heuristic search and planning model real-world problems as graphs, where each node represents a unique state or configuration of the problem, and each edge represents an operator that changes one state to another state. The task is to find a shortest or lowest-cost path between the initial state and a goal state in such a graph, which corresponds to a sequence of operators to solve the given problem instance with minimum cost.

A* is the standard algorithm for a single-agent heuristic search or planning problem. However, A* stores all nodes generated during the search and can run out of the available memory on common heuristic search and planning domains in a few minutes. Therefore, A* usually cannot solve hard problems. On the other hand, the memory requirement of iterative-deepening-A* (IDA*) is only linear in the search depth. However, on a domain where many distinct paths exist between the same pair of nodes, IDA* may generate too many duplicate nodes and hence run for a prohibitively long time.

In this dissertation, we provide three new algorithms, A*+IDA*, A*+BFHS, and IDUCHS, for solving problems that cannot be solved by A* due to memory limitations, nor IDA* due to the existence of many distinct paths between the same pair of nodes. We show that A*+IDA* is the state-of-the-art algorithm on the classic benchmark 24-Puzzle, while A*+BFHS and IDUCHS can generate significantly fewer nodes than A*, hence solving more problems than A* given the same memory limitations.

The NP-hard number-partitioning problem is to separate a multiset S of

n positive integers into k subsets, such that the largest sum of the

integers assigned to any subset is minimized. The classic application

is scheduling a set of n jobs with different run times onto k

identical machines such that the makespan, the time to complete the

schedule, is minimized. The two-way number-partitioning decision

problem is one of the original 21 problems Richard Karp proved

NP-complete. It is also one of Garey and Johnson's six fundamental

NP-complete problems, and the only one involving numbers.

This thesis explores algorithms for solving multi-way

number-partitioning problems optimally. We explore previously existing

algorithms as well as our own algorithms: sequential number

partitioning (SNP), a branch-and-bound algorithm; binary-search

improved bin completion (BSIBC), a bin-packing algorithm; cached

iterative weakening (CIW), an iterative weakening algorithm; and a

variant of CIW, low cardinality search (LCS). We show experimentally

that for high precision random problem instances, SNP, CIW and LCS are

all state of the art algorithms depending on the values of n and k.

All three outperform previous algorithms by multiple orders of

magnitude in terms of run time.

Bidirectional heuristic search is a well-known technique for solving pathfinding problems. The goal in a pathfinding problem is to find paths---often of lowest cost---between nodes in a graph. Many real-world problems, such as finding the quickest route between two points in a map or measuring the similarity of DNA sequences, can be modeled as pathfinding problems.

Bidirectional brute-force search does simultaneous brute-force searches forward from the initial state and backward from the goal states, finding solutions when both intersect. The idea of adding a heuristic to guide search is an old one, but has not seen widespread use and is generally believed to be ineffective.

I present an intuitive explanation for the ineffectiveness of front-to-end bidirectional heuristic search. Previous work has examined this topic, but mine is the first comprehensive explanation for why most front-to-end bidirectional heuristic search algorithms will usually be outperformed by either unidirectional heuristic or bidirectional brute-force searches. However, I also provide a graph wherein bidirectional heuristic search does outperform both other approaches, as well as real-world problem instances from the road navigation domain. These demonstrate that there can be no general, formal proof of the technique's ineffectiveness.

I tested my theory in a large number of popular search domains, confirming its predictions. One of my experiments demonstrates that a commonly-repeated explanation for the ineffectiveness of bidirectional heuristic search---that it spends most of its time proving solution optimality---is in fact wrong, and that with a strong heuristic a bidirectional heuristic search tends to find optimal solutions very late in a search.

Finally, I introduce state-of-the-art solvers for the four-peg Towers of Hanoi with arbitrary initial and goal states, and peg solitaire, using disk-based, bidirectional algorithms. The Towers of Hanoi solver is a bidirectional brute-force solver which, as my theory predicts, outperforms a unidirectional heuristic solver. The peg solitaire solver is a bidirectional heuristic algorithm with novel heuristics. While my theory demonstrates that bidirectional heuristic search is generally ineffective, the peg solitaire domain demonstrates several caveats to my theory that this algorithm takes advantage of.

We study an extension of the well-known bin-packing problem to multiple dimensions, resulting in the "vector packing" problem. The problem is to find the minimum number of multidimensional bins to pack a set of vectors into without exceeding the bin capacity in any dimension of any bin. While we use approximate methods to inform our search, we ultimately return optimal solutions. This work is an attempt to extend the results of [Kor03] to multiple dimensions and combine it with some new techniques. A hybrid DFBnB algorithm which searches in two separate problem spaces is used as the final algorithm. Our hybrid algorithm also uses a heuristic to assist the search, and an approximate algorithm to initially bound the cost of an optimal solution. The resulting algorithm can be run on vector-packing problems with any number of dimensions, and good results are shown for up to five-dimensional problems. An attempt is also made to define a method to compare these results with future algorithms, as consensus on appropriate test suites for vector-packing problems seems to be lacking.

We have found two admissible heuristics that we use within a branch and bound framework

to compute optimal solutions to the Orienteering Problem on both complete and incomplete

graphs. Our approach exponentially outperforms naive methods in terms of both node

expansions and runtime. A detailed description of our heuristics and overall algorithm are

provided. Finally, we analyze the performance of our approach on a variety problem of

instances.