2. Graph search strategy

14th, Sept.

2.1. State space

• From initial state to objective through medium states
• Assumptions:
  • The agent has perfect knowledge of the state space (full observability)
  • The agent has a set of actions that have known deterministic effects
  • Some states are goal staes, which the agent wants to reach
  • A solution is a sequence of actions that will get the agent from its current state to a goal state
• Eg: Sentence parsing
  • Input string (initial state)
  • Substitute according to regulations
  • Output if the string is a sentence (objective)
• Eg: Judge if a snippet is in C language
• Eg: Traveling salesman problem (TSP)
  • Can be formalized with string
• Eg: Missionary and wild man

2.2. Tricolor Algorithms

• Reference
• And abstract description of graph traversal
• Graph nodes are assigned one of three colors that can change over time
  • White undiscovered
  • Black reachable and done
  • Gray discovered but not done

2.3. Basic Graph Search Algorithm

Breadth first search (BFS)

• Illustration
• Pseudocode

// let s be the source node
frontier = new Queue()
mark root visited (set root.distance = 0)
frontier.push(root)
while frontier not empty {
    Vertex v = frontier.pop()
    for each successor v' of v {
    if v' unvisited {
        frontier.push(v')
        mark v' visited (v'.distance = v.distance + 1)
    }
    }
}

• Application

Depth first search (DFS)

• Illustration
• Pseudocode

DFS(Vertex v) {
    mark v visited
    set color of v to gray
    for each successor v' of v {
    if v' not yet visited {
        DFS(v')
    }
    }
    set color of v to black
}

• Application

Uniform cost search (Dijkstra’s algorithm)

Hill-climbing method

• Manhattan distance or L^1 norm
• Search for the node who has the smallest L^1 norm (greedy algorithm) to the target.
• Can be applied to any problem where the current state allows for an accurate evaluation function.
• Application on TSP.

2.4. Heuristic Search

• For every node, define a cost function:
• Heuristic function , which takes a node n and returns a non-negative real number that is an estimate of the path cost from node n to a goal node.
• Basic search algorithm can be attributed to heuristic search:
  • BFS:
  • DFS:

algorithm

• A* is implemented by treating the frontier as a priority queue ordered by .
• Proposition (Admissibility of A) A always finds an optimal path, if one exists, and the first path found to a goal is optimal, if
  • the branching factor is finite (each node has only a finite number of neighbors),
  • arc costs are greater than some , and
  • is a lower bound on the actual minimum cost of the lowest-cost path from n to a goal node.

2.5. Influencial Factors of Speed of A*

• Extended node number
• Computation cost of h(x)