Best-First Search

• idea: expand “best” node according to the evaluation function f(n)
• types of best-first search algorithms
  • greedy search
  • A* search

Types of Cost Functions

• heuristic function
  • h(n) = estimated cost from state n to a goal state
  • admissible heuristic function
    • h(n) = estimated cost from state n to a goal state that never overestimates the true cost
• total cost function
  • g(n) = cost from initial state to state n
• combined cost function
  • f(n) = g(n) + h(n)
  • f(n) = estimated cost of the cheapest solution through n

Greedy Search

• idea: expand node based on heuristic function h(n)
• like depth-first search where it follows a single path towards goal and backs up when reached dead end
• not optimal & incomplete

Uniform-Cost Search

• idea: expand node based on total cost function g(n)
• optimal & complete
• but can be very inefficient

A* Search

• idea: expand node based on f(n) where f(n) = g(n) + h(n)
• optimal & complete if h(n) is a admissible heuristic
• monotonicity
  • an attribute of f(n) that along any path from root, the f-cost never decreases
  • holds true for almost all admissible heuristics
• non-monotonicity
  • example: let’s say state n is the parent of n’, a non-monotonicity heuristic is when f(n) > f(n’)
• non-monotonicity to monotonicity
  • pathmax equation - f(n’) = max(f(n), g(n’) + h(n’))

Heuristic Functions

• Effects of Heuristic Accuracy and Performance
  • effective branching factor b*
    • if number of nodes expanded by A* is N and solution depth is d
    • then b* is the branching factor that a uniform tree of depth d would have to have in order to contain N nodes
    • thus, N = 1 + b* + (b*)² + … (b*)ᵈ
    • e.g. if A ⃰ finds a solution at depth 5 using 52 nodes, then b* = 1.91
  • dominates
    • h2 dominates h1 if A* using h2 expands fewer nodes
  • hence, it is always better to use heuristic function with higher values, as long as they don’t overestimate
• Inventing Heuristic Functions
  • problem: finding the best heuristic
  • relaxed problem - a problem with less restrictions on the operators
  • composite heuristic
    • if a collection of heuristics contains no single dominating heuristic, we could define
    • h(n) = max(h1(n), …, hₓ(n))
  • features
    • selecting and weighting the possible features of a state in order to evaluate the heuristic function

Heuristics For Constraint Satisfaction Problems (CSP)

• constraint satisfaction problems consists of:
  • a set of variables that can take on values from a given domain
  • a set of constraints that specify properties of the solution
• Choosing Next Variable to Assign Value
  • most-constrained-variable heuristic
    • used with forward checking
    • variable with fewest possible values is chosen to have value assigned
  • most-constraining-variable heuristic
    • assign value to variable that is involved in the largest number of constraints on other unassigned variables
• Choosing Value to be Assigned to Variable
  • least-constraining-value heuristic
    • choose value that rules out the smallest number of values in variables connected to the current variable by constraints

Memory Bound Search

• Iterative Deepening A* Search (IDA*)
  • similar to regular iterative deepening from chapter 3
  • a depth-first search modified to use f-cost limit
  • optimal and complete
  • has some difficulties in certain problem spaces that can be traced back to using too little memory
• Simplified Memory-Bounded A* Search (SMA*)
  • makes use of all the available memory to carry out search
  • SMA ⃰ has the following properties
    • will utilize whatever memory is made available to it
    • avoids repeated states as far as its memory allows
    • is complete if available memory is sufficient to store the shallowest solution path
    • is optimal if enough memory is available to store the shallowest optimal solution path. otherwise, it returns the best solution that can be reached with the available memory
    • when enough memory is available for the entire search tree, the search is optimally efficient
  • when space runs out, drop nodes that are unpromising

Iterative Improvement Hill-Climbing Algorithms

• Hill-Climbing Search
  • general idea: start with a complete configuration and to make modifications to improve its quality
  • make moves in direction of increasing value. It does not maintain a search tree, and it does not look beyond the immediate neighbors of the current state.
  • Hill climbing is often called “greedy local search” because it grabs a good neighbor state without thinking ahead about where to go next
  • 3 drawbacks:
    • local maxima - algorithm would halt thinking it is the global maxima
    • plateaux - search would conduct random walk
    • ridges - steep sloping sides
  • variants of hill-climbing algorithms
    • stochastic hill-climbing
      • chooses at random from the uphill moves, the probability of selection can vary with the steepness of the uphill move
    • first choice hill climbing
      • implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state
    • random-restart hill-climbing
      • conducts a series of hill-climbing searches from random initial states
      • can use a fixed number of iterations or continue until the best saved result no longer improved for a certain number of iterations
• Simulated Annealing
  • general idea: to escape local maxima allow search to take downhill steps

Iterative Improvements in Constraint Satisfaction Problems

• heuristic repair
  • assign values to all variables, then apply modifications to move towards solution
• min-conflicts heuristic
  • select value that results in the minimum number of conflicts with other variables