AAAI Publications, Seventh Annual Symposium on Combinatorial Search

Font Size: 
Max is More than Min: Solving Maximization Problems with Heuristic Search
Roni Tzvi Stern, Scott Kiesel, Rami Puzis, Ariel Felner, Wheeler Ruml

Last modified: 2014-07-02

Abstract


Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding the longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems — optimal, suboptimal, and bounded suboptimal - and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and a discovered close relationships between Dijkstra's algorithm, weighted A*, and depth-first search. This work demonstrates that MAX problems demand their own heuristic search algorithms, which are worthy objects of study in their own right.

Keywords


Heuristic search, optimization, maximization

Full Text: PDF