6.034 Artificial Intelligence - Recitations, fall 2004 online slides on search
	Example 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ <--->| 8 |<--->| 9 |<--->|!1!|<--->| 1 |<--->| 3 |<--->| 2 |<--->| 1 |<--->|*G*| +---+ +---+ +---+ +---+ +---+ +---+ +---+ 1 +---+ Current state s has estimated cost to reach the goal of H(s) = 1 Select neighbor s' with H(s') = 1, but c(s, a, s') + H(s') = 1 + 1 $>$ 1 Update H(s) to be 3 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ <--->| 8 |<--->| 9 |<--->| 2 |<--->|!1!|<--->| 3 |<--->| 2 |<--->| 1 |<--->|*G*| +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ <--->| 8 |<--->| 9 |<--->|!2!|<--->| 3 |<--->| 3 |<--->| 2 |<--->| 1 |<--->|*G*| +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ <--->| 8 |<--->| 9 |<--->| 4 |<--->|!3!|<--->| 3 |<--->| 2 |<--->| 1 |<--->|*G*| +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ 1 +---+ <--->| 8 |<--->| 9 |<--->| 4 |<--->| 4 |<--->|!3!|<--->| 2 |<--->| 1 |<--->|*G*| +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+