03.2 Breadth-First Search//Uniform-Cost Search

Question 1

function Breadth-First-Search (problem) returns a solution or failure
node ← Node(…)
if problem.Is-Goal(node.State) then return Solution(node)

frontier ← a … as the only element
reached ← …

Answer 1

State=problem.Initial-State, Path-Cost=0

FIFO queue with node

{node.State}

Question 2

loop do
if Is-Empty(frontier) then …
node ← Pop(frontier) // chooses a shallowest node in frontier for each child in Expand(problem, node) do
s ← child.State
if problem.Is-Goal(s) then return Solution(child)
if s is not in reached then
…
frontier ← Add(child,frontier)

Answer 2

return failure

add s to reached

Question 3

Auxiliary Algorithm: Expand

function Expand (problem, node) yields nodes
s ← …
for each action in problem.Actions(s) do
s′ ← …
cost ← …
yield Node(…)

Answer 3

node.State

problem.Result(s, action)

node.Path-Cost + problem.Action-Cost(s, action, s′)

State=s′, Parent=node, Action=action, Path-Cost=cost

Question 4

Performance of BFS

• the branching factor b (maximum number of successors of any node)
• the depth d (depth of the shallowest goal node, where root is at depth 0),
  -the maximum length m of any path in the state space

Assess it on the performance metrics.

Answer 4

Completeness: Yes, if depth d and branching factor b are finite.

Optimality: Yes, if cost is equal per step; not optimal in general.

Time complexity: The worst case is that each node has b successors. The number of explored nodes sums up to
b+b2+b3+···+bd =O(bd)

Space complexity: All explored nodes are O(bd−1) and all nodes in the frontier are O(bd )

Question 5

When all step costs are equal, breadth-first is optimal because it …

Uniform-cost search is optimal for any step costs, as …
This is realized by …ordered by g.

Answer 5

always expands the shallowest nodes.

it expands the node with the lowest path cost g(n) = n.Path-Cost.

storing the frontier as a priority queue