# Complete Search

Bart Massey

## Strengths and Weaknesses Of Computers

• Strengths

• Simple operations fast!!!

• Completely deterministic

• Completely reliable

• Huge perfectly reliable storage

• Never get tired

• Weaknesses

• Complex to use

• Can't scale arbitrarily

## Combinatorial Search Graphs

• Define graph by adjacency list function

``````f(v) -> neighbors of v
``````
• This allows a compact representation of an arbitrarily large graph

• Motivation: real problems with graph structure are like this

## Complete Search Spaces

• Vertices are "partial solutions", neighbors are incremental extension of solutions

• Explore neighbors systematically from a starting vertex

• Seek one of set of goal vertices representing total solutions

• Turns an undirected graph into a tree of partial solutions

• Can keep a closed list or by construction to stop looping

• Breadth-first or depth-first works

## Skiena: General DFS For Graphs

• Depth-first with no closed list gives reasonable memory usage

• Gives an algorithm parameterized by graph functions

• Sort of a strange formulation

• Simple graph examples: subsets, permutations

• Note that general permutations form a tree with n! vertices

## Paths In A Highway Graph

• Construct partial solutions (paths from start) until a path including a goal node is hit

• Search graph is graph of paths, not cities

• Dijkstra SSSP constructs graph such that closed list summarizes shortest paths

• This is essentially dynamic programming

## Complete Search Has Issues

• Guaranteed to give a solution when one exists

• On large instances, will run too long to wait

• Closed list will use too much memory to be feasible

## Heuristics For Complete Search

• "Value ordering": order the extensions such that a "good" one is selected first

• "Variable ordering": decide what to extend next so that a good candidate is selected first

## Sudoku

• Nodes are partial solutions

• Start is given puzzle

• Standard solution is to (1) select a cell to fill, (2) try the legal values for that cell, recurse to solve the whole board

• Good solvers are careful about variable and value ordering

## Improving Dijkstra SSSP: A*

• Idea: select next node to expand based on estimate of distance to goal

• But this breaks Dijkstra SSSP: node farther from origin might be expanded first

• Solution: admissible estimate; choose a node that provably won't be too far away from origin, so that if goal is found early it still is shortest

## How To A*

``````To a-star search for solution:
L <- new empty "stop list" of visited states
H <- new empty min-heap
insert (start, 0) into H with priority h(start)
while H is not empty
s <- dequeue min from H
insert s into L
if s is a goal state:
return the reverse of the path from s to the
null state following the parent links
for each s' resulting from a legal move on s:
if s' is in L:
continue
insert (s', g(s)) into H with priority g(start)+h(start)
fail
``````
• Note that this is Dijkstra when h(s) = 0

• When h(s) is the true distance to the goal, this becomes a linear search

• Can prove that when a goal is dequeued it is on a shortest path

• Worst-case running time is same as Dijkstra, but better h can make big improvements

## Highway Search: A* By Euclidean Distance

• For highway search, we can choose h(city) to be the Euclidean distance from city to goal

• This is admissible, since no highway can get you there shorter

• Travel time?