# 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?