Max is More than Min: Solving Maximization Problems with Heuristic Search

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