Properties of A Properties of A Complete Yes.unless there are infinitely many nodes with() Space Keeps all nodes in memory Properties of A' Properties of A Complete??Yes, unle there are infinitely many nodes with() thereare infinitely many nodes with( Lime?? mExponential inrelativer inlngthofso Space??Keeps all nodes in memory <C Properties of A Proof of lemma:Consistency Complete??Yes.unless there are infinitely many nodes with f<f(G Aheuristic if Time??Exponential in [relative error in h x length of soln.] hn)≤cdm,a,n)+hM .we have c(n.a.n) a+h f Le(n)is nondecreasing alng any path.Properties of A∗ Complete?? Chapter 4, Sections 1–2 25 Properties of A∗ Complete?? Yes, unless there are infinitely many nodes with f ≤ f(G) Time?? Chapter 4, Sections 1–2 26 Properties of A∗ Complete?? Yes, unless there are infinitely many nodes with f ≤ f(G) Time?? Exponential in [relative error in h × length of soln.] Space?? Chapter 4, Sections 1–2 27 Properties of A∗ Complete?? Yes, unless there are infinitely many nodes with f ≤ f(G) Time?? Exponential in [relative error in h × length of soln.] Space?? Keeps all nodes in memory Optimal?? Chapter 4, Sections 1–2 28 Properties of A∗ Complete?? Yes, unless there are infinitely many nodes with f ≤ f(G) Time?? Exponential in [relative error in h × length of soln.] Space?? Keeps all nodes in memory Optimal?? Yes—cannot expand fi+1 until fi is finished A ∗ expands all nodes with f(n) < C ∗ A ∗ expands some nodes with f(n) = C ∗ A ∗ expands no nodes with f(n) > C ∗ Chapter 4, Sections 1–2 29 Proof of lemma: Consistency A heuristic is consistent if n c(n,a,n’) h(n’) h(n) G n’ h(n) ≤ c(n, a, n 0 ) + h(n 0 ) If h is consistent, we have f(n 0 ) = g(n 0 ) + h(n 0 ) = g(n) + c(n, a, n 0 ) + h(n 0 ) ≥ g(n) + h(n) = f(n) I.e., f(n) is nondecreasing along any path. Chapter 4, Sections 1–2 30