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?