A Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- problem](x)+h(x) op Terminates if Nodes[problem] is empty then return failure when node < Remove-Best(Nodes[problem], f) state←- State(noe) remove any n from Nodes[problem] such that State(n )= state Expanded[problem]<Expanded[problem]u(state) new-nodes < Expand(node, problem) for each new-node in new-nodes unless State (new-node) is in Expanded[problem then Nodes[problem]<Enqueue(Nodes[problem], new-node, if Goal-Testiproblem] applied to state(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 2002 A米 Search Function A*(problem, h) returns the best solution or failure Problem pre-initialized f(×)←- pRoblem](x)+h(x) Dynamic loop do if Nodes[ problem] is empty then return failure Programming node +Remove-Best(Nodes[problem f) Principle state← State( node) remove any n from Nodes[problem] such that State(n)= state Expanded[problem]<Expanded[problem]u(state) new-nodes <Expand(node, problem) for each new-node in new-nodes unless State(new-node)is in Expanded [problem] then Nodes[problem]<Enqueue(Nodes[problem], new-node, if Goal-Test[problem] applied to State(node) succeeds then return node end 3/17/2004 copyright Brian Williams, 20023/17/2004 copyright Brian Williams, 2002 15 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Terminates when . . . 3/17/2004 copyright Brian Williams, 2002 16 A* Search Function A*(problem, h) returns the best solution or failure. Problem pre-initialized. f(x) ← g[problem](x) + h(x) loop do if Nodes[problem] is empty then return failure node ← Remove-Best(Nodes[problem], f) state ← State(node) remove any n from Nodes[problem] such that State(n) = state Expanded[problem] ← Expanded[problem] ∪ {state} new-nodes ← Expand(node, problem) for each new-node in new-nodes unless State(new-node) is in Expanded[problem] then Nodes[problem] ← Enqueue(Nodes[problem], new-node, f ) if Goal-Test[problem] applied to State(node) succeeds then return node end Dynamic Programming Principle . .