Beam search
Looks for a route from one vertex to another while keeping only the few best partial paths at each step, so its memory and time stay bounded, at the cost of sometimes missing the best route.
Time complexity O(L·w·(L + d log w)), gograph function path.Beam.
How it works
Beam search grows paths from the start one edge at a time. At each step it extends every path it kept by each edge that doesn't go back to a vertex already on it, ranks the new paths by a score, and keeps only the best few, the width of the beam. The rest are dropped for good. It stops at the first step that keeps a path ending at the goal.
Since it never holds more than the width, its memory and time stay bounded however large the graph is. That is the trade: a path dropped early may have been the start of the best route, so the route found can be slower, and when every kept path runs into a dead end, there is no route at all. It is used where a full search is too big: speech and translation decoders, planners and puzzle solvers.
The score on this page is the minutes so far plus the straight-line guess of the time left from the A* page, so a path that heads toward the goal ranks first. A nil score ranks by the minutes so far alone, which at the same width usually finds slower routes or none, since it can't tell which way the goal is.
path.Beam takes the width and the score, which gets the edge and the cost so far and returns the rank, lower first. Paths with the same score keep the order they were made in. A width below 1 returns ErrInvalidWidth, and a beam whose kept paths never reach the goal returns ErrUnreachable. With L edges on the route and d the most edges out of a vertex, it costs O(L·w·(L + d log w)) for a width of w.
San Francisco streets
The main streets of San Francisco from the Embarcadero to Van Ness Avenue and the Mission, from OpenStreetMap, with the freeways that cross SoMa. Each intersection is named after its streets, one-way streets go one way, and each edge is the minutes to drive it at the speed limit, or at 22 to 40 km/h by road type where the map has no limit.
A directed, weighted graph with 248 vertices and 548 edges.
Map data © OpenStreetMap contributors.
How quick a route does a beam of three find from The Embarcadero & Mission St to 16th St & S Van Ness Ave, and how much less of the map does it look at than Dijkstra?
A beam of 3 finds a drive of 6.42 minutes from The Embarcadero & Mission St to 16th St & S Van Ness Ave. That's the quickest route, the one Dijkstra finds.
Step by step
- Start one path at The Embarcadero & Mission St. Each step extends every kept path by one edge, ranks the new paths, and keeps the best 3. The rank is the minutes so far plus the straight-line guess of the time left from the A* page, so a path that heads toward 16th St & S Van Ness Ave comes first.
- Step 1: extending the kept paths by one edge makes 2 paths, no more than the width, so keep them all.
- Step 2: extending the kept paths by one edge makes 3 paths, no more than the width, so keep them all.
- Step 3: extending the kept paths by one edge makes 5 paths. Keep the best 3 paths, ending at The Embarcadero near Washington St, 1st St & Howard St and The Embarcadero & Harrison St, and drop 2.
- Step 4: extending the kept paths by one edge makes 6 paths. Keep the best 3 paths, ending at The Embarcadero near Clay St, The Embarcadero & Washington St and New Montgomery St & Howard St, and drop 3.
- Step 5: extending the kept paths by one edge makes 4 paths. Keep the best 3 paths, ending at The Embarcadero near Clay St, The Embarcadero near Steuart St and 3rd St & Howard St, and drop 1.
18 more steps lead to the last one:
- Step 24: extending the kept paths by one edge makes 3 paths, no more than the width, so keep them all. A kept path reaches 16th St & S Van Ness Ave, at 6.42 minutes, so the beam stops.
Use it in Go
goal := where["16th St & S Van Ness Ave"]
score := func(e *gograph.Edge[string], soFar float64) float64 {
p := where[e.Destination().Label()]
return soFar + e.Weight() + math.Hypot(p[0]-goal[0], p[1]-goal[1])/speed
}
route, minutes, err := path.Beam(g, "The Embarcadero & Mission St", "16th St & S Van Ness Ave", 3, score)
if err != nil {
return err // path.ErrUnreachable when every kept path runs into a dead end
}
fmt.Println(minutes)
for _, v := range route {
fmt.Println(v.Label())
}
Example graphs
- New York streets, 295 vertices and 669 edges
- London streets, 274 vertices and 598 edges
- San Francisco streets, 248 vertices and 548 edges
- Rasht streets, 298 vertices and 568 edges
- School run, 6 vertices and 13 edges
- Delivery area, 8 vertices and 12 edges
- Downtown grid, 20 vertices and 60 edges
- One-way city, 45 vertices and 88 edges
- Metro region, 100 vertices and 346 edges
More in Shortest paths
- Dijkstra: Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
- A*: Finds the quickest route from one vertex to another, looking first where a guess of the time left says the goal is, so it settles far fewer vertices than Dijkstra.
- Bidirectional search: Finds the quickest route from one vertex to another by searching forward from the start and backward from the goal at once, until the two searches meet.
- k shortest paths: Finds the k quickest routes from one vertex to another that don't repeat a vertex, quickest first, the way a navigation app offers a few routes.
- Multi-source Dijkstra: Finds the nearest of several sources for every vertex, and the distance from it, in one search.
- k-center: Chooses k centers so that the vertex farthest from its nearest center is as near as it can make it.
- Bellman-Ford: Finds the shortest distance from a start vertex to every other vertex, even with negative weights, and reports a negative cycle when the start can reach one.
- Floyd-Warshall: Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.