Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

Sequential Search Algorithms

• Is the search space a tree or a graph?

• The space of a 0/1 integer program is a tree, while that of an 8-puzzle is a graph.

• This has important implications for search since unfolding a graph into a tree can have significant overheads.

Sequential Search Algorithms

• Two examples of unfolding a graph into a tree.

Depth-First Search Algorithms

• Applies to search spaces that are trees.

• DFS begins by expanding the initial node and generating its successors. In each subsequent step, DFS expands one of the most recently generated nodes.

• If there exists no success, DFS backtracks to the parent and explores an alternate child.

• Often, successors of a node are ordered based on their likelihood of reaching a solution. This is called directed DFS.

•