Tree and graph search

Runs breadth-first, depth-first, depth-limited, iterative deepening, uniform-cost, greedy best-first, A*, and weighted A* search on a graph, one step at a time, with the state space, the search tree, and the frontier side by side.

Lecture reference: Solving Problems by Searching · slides 27–43
Lecture reference: Uninformed Search · slides 3–44
Lecture reference: Informed Search · slides 7–38

Problem 20 states · 23 edges

Start: Arad
Goal: Bucharest
h(n): Straight-line distance to Bucharest

Successor order

Alphabetical As listed

A* search example. f(n) = g(n) + h(n) under every node, from 366=0+366 at Arad to 418=418+0 at Bucharest.

Informed Search · slides 17–22

Edit graph

Check this heuristic Compare strategies

Strategy A* search

Strategy

Frontier: Priority queue ordered by f(n) = g(n) + h(n)

Goal test

As in the tree search outline.

Expansion limit

Nodes taken off the frontier before the run stops.

Repeated states Tree search No check: every child goes on the frontier. Solving Problems by Searching · slide 28 Path check A child whose state is already on its path from the root is not added. Uninformed Search · slide 32 Graph search Explored states are not added again; with a priority queue, a cheaper path replaces a frontier node. Solving Problems by Searching · slide 36

Step 1 of 7

Initialize the frontier with Arad.

State space with h(n)

Search tree

Labels

Frontier

1 node Priority queue ordered by f(n) = g(n) + h(n)

next Arad 366=0+366

Expansion order

0 of 6 nodes taken off the frontier

With focus in the tool: ← → previous and next step, Home End first and last step, Space play or pause.

Result

Solution Solution: Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest (cost 418). 6 nodes taken off the frontier, 5 expanded, 16 generated.

Taken off the frontier: 6
Expanded: 5
Generated: 16
Largest frontier: 11

Cheapest path This is a cheapest path (cost 418).

Questions from the slides

Properties of depth-first search: complete?

Uninformed Search · slide 32

Show answer

How can we fix the greedy problem?

Informed Search · slide 15

Show answer

A* gone wrong?

Informed Search · slide 27

Show answer