Heuristic Search for m Best Solutions with Applications to Graphical Models Rina Dechter and Natalia Flerova Bren school of Information and Computer Sciences University of California Irvine Abstract The paper focuses on finding the m best solutions to a combinatorial optimization problems using Best First or Branch and Bound search We are interested in graphical model optimization tasks e g Weighted CSP which can be formulated as finding the m best solutionpaths in a weighted search graph Specifically we present m A extending the well known A to the m best problem and prove that all A s properties are maintained including soundness and completeness of mA dominance with respect to improved heuristics and most significantly optimal efficiency compared with any other search algorithm that use the same heuristic function We also present and analyse m B B an extension of a Depth First Branch and Bound algorithm to the task of finding the m best solutions Finally for graphical models a hybrid of A and a variable elimination scheme yields an algorithm which has the best complexity bound compared with earlier known m best algorithms 1 Introduction Depth First Branch and Bound B B and Best First Search BFS are the most widely used search schemes for finding optimal solutions In this paper we explore the extension of such search algorithms to finding the m best optimal solutions We apply such algorithms to optimization tasks over graphical models such as weighted CSPs and most probable explanation MPE over probabilistic networks arising in many applications e g in procurement auction problems biological sequence alignment and finding m most likely haplotype configurations Most of the paper s analysis focuses on Best First Search whose behavior for the task of finding a single optimal solution is well understood The algorithm is known to be sound and complete when guided by an admissible i e lower bound for minimization task heuristic evaluation function Most significantly it is efficiently optimal any node it expands must be expanded by any other exact search algorithm having the same heuristic function if both use the same tie breaking rule 4 Best First Search and its most famous variant A are also known to require significant memory The most popular alternative to BFS is Depth First Branch and Bound whose most attractive feature compared with BFS is that it can be executed with linear memory Yet when the search space is a graph it can exploit memory to improve its performance by flexibly trading space and time Highly efficient B B and BFS algorithms for finding an optimal solution over graphical models were developed recently These algorithms explore the AND OR search tree or the context minimal AND OR search graph of the graphical model 3 they use heuristic evaluation functions generated either by the mini bucket scheme or through soft arc consistency schemes 9 12 and they proved to be most effective as demonstrated in recent evaluations 2 Clearly an extension of a BFS or B B to the m best task over a general search space graph for optimal path finding tasks is applicable to graphical models when searching its AND OR search space 3 The main contribution of this paper Section 3 is in presenting m A an extension of the A for finding the m best solutions and in showing that all its properties extend to the m best case In particular we prove that m A is sound and complete and is efficiently optimal In Section 4 we discuss extensions of Branch and Bound to the m best task Subsequently in Section 5 we discuss anchoring the algorithms for searching graphical models AND OR search spaces We show that a hybrid of A and a variable elimination scheme denoted BEGreedy m BF yields a best complexity algorithm compared with earlier work on graphical models Preliminary empirical evaluation shed light on the algorithm s performance We assume without loss of generality that the optimization task at hand is minimization 2 Background Let A be a general search algorithm for finding an optimal solution path over a search space defined implicitly by a set of states the nodes in the graph operators that map states to states having costs or weights the directed weighted arcs a starting state n0 and a set of goal states The task is to find the least cost solution path from the start node to a goal 10 where the cost of a solution path is the sum of the weights or the product of the weights on its arcs The two primary search strategies for finding an optimal solution are Best First Search BF S e g A and Depth First Branch and Bound search B B In this paper we explore extensions of both schemes for finding the m best solutions for any integer m Best first search BFS seems to be the most suitable algorithm to be extended to m best task It explores the search space using a heuristic evaluation function f n which for every node n estimates the best cost solution path passing through n The algorithm maintains a list of nodes that are candidates for expansions often called OPEN or frontier At each iteration a node in the frontier having a minimal f is selected for expansion moved to another list called CLOSED or explored set and its child nodes are places in OPEN each associated with its own evaluation function When a goal node is selected for expansion the algorithm terminates and outputs the solution found It is known that when f n is a lower bound on the optimal cost path that goes through n the algorithm terminates with an optimal solution The algo rithm s properties were extensively studied 10 11 In particular up to some tie breaking rule the algorithm is efficiently optimal Namely any node expanded by BF S is expanded by any other search algorithm guaranteed to find an optimal solution 4 If provided with a consistent also called monotonic heuristic the algorithm expands nodes in frontiers of monotonically increasing evaluation function and it expands every node just once 10 This later property is of utmost importance because it frees the algorithm from the need to check for duplicates when the search space is a graph We focus on the well known BF S variant called A where the heuristic evaluation function is expressed as the sum f n g n h n in which for any node n g n is minimal cost from the root n0 to n along the current path and h n underestimates h n the optimal cost from n to a goal node The implicit directed search space graph is G N E We denote by g n the cost from the root to n along path and by c n1 n2