{"algorithm":"beam","about":["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."],"template":{"id":"downtown-grid","name":"Downtown grid","description":"Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"Pine & 1st","x":76,"y":156},{"id":"Pine & 2nd","x":283,"y":188},{"id":"Pine & 3rd","x":496,"y":189},{"id":"Pine & 4th","x":706,"y":160},{"id":"Pine & 5th","x":931,"y":161},{"id":"Main & 1st","x":68,"y":383},{"id":"Main & 2nd","x":268,"y":404},{"id":"Main & 3rd","x":518,"y":374},{"id":"Main & 4th","x":739,"y":393},{"id":"Main & 5th","x":946,"y":381},{"id":"Market & 1st","x":73,"y":597},{"id":"Market & 2nd","x":276,"y":620},{"id":"Market & 3rd","x":512,"y":609},{"id":"Market & 4th","x":704,"y":593},{"id":"Market & 5th","x":958,"y":591},{"id":"River & 1st","x":53,"y":842},{"id":"River & 2nd","x":274,"y":833},{"id":"River & 3rd","x":489,"y":826},{"id":"River & 4th","x":701,"y":833},{"id":"River & 5th","x":950,"y":829}],"edges":[{"from":"Pine & 1st","to":"Pine & 2nd","weight":2},{"from":"Pine & 2nd","to":"Pine & 1st","weight":2},{"from":"Pine & 1st","to":"Main & 1st","weight":2},{"from":"Main & 1st","to":"Pine & 1st","weight":2},{"from":"Pine & 2nd","to":"Pine & 3rd","weight":3},{"from":"Pine & 3rd","to":"Pine & 2nd","weight":3},{"from":"Pine & 2nd","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Pine & 2nd","weight":3},{"from":"Pine & 3rd","to":"Pine & 4th","weight":2},{"from":"Pine & 4th","to":"Pine & 3rd","weight":2},{"from":"Pine & 3rd","to":"Main & 3rd","weight":2},{"from":"Main & 3rd","to":"Pine & 3rd","weight":2},{"from":"Pine & 4th","to":"Pine & 5th","weight":3},{"from":"Pine & 5th","to":"Pine & 4th","weight":3},{"from":"Pine & 4th","to":"Main & 4th","weight":2},{"from":"Main & 4th","to":"Pine & 4th","weight":2},{"from":"Pine & 5th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Pine & 5th","weight":3},{"from":"Main & 1st","to":"Main & 2nd","weight":3},{"from":"Main & 2nd","to":"Main & 1st","weight":3},{"from":"Main & 1st","to":"Market & 1st","weight":3},{"from":"Market & 1st","to":"Main & 1st","weight":3},{"from":"Main & 2nd","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Main & 2nd","weight":4},{"from":"Main & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Main & 2nd","weight":2},{"from":"Main & 3rd","to":"Main & 4th","weight":4},{"from":"Main & 4th","to":"Main & 3rd","weight":4},{"from":"Main & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"Main & 3rd","weight":3},{"from":"Main & 4th","to":"Main & 5th","weight":3},{"from":"Main & 5th","to":"Main & 4th","weight":3},{"from":"Main & 4th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"Main & 4th","weight":2},{"from":"Main & 5th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Main & 5th","weight":2},{"from":"Market & 1st","to":"Market & 2nd","weight":2},{"from":"Market & 2nd","to":"Market & 1st","weight":2},{"from":"Market & 1st","to":"River & 1st","weight":2},{"from":"River & 1st","to":"Market & 1st","weight":2},{"from":"Market & 2nd","to":"River & 2nd","weight":2},{"from":"River & 2nd","to":"Market & 2nd","weight":2},{"from":"Market & 3rd","to":"Market & 4th","weight":3},{"from":"Market & 4th","to":"Market & 3rd","weight":3},{"from":"Market & 3rd","to":"River & 3rd","weight":3},{"from":"River & 3rd","to":"Market & 3rd","weight":3},{"from":"Market & 4th","to":"Market & 5th","weight":2},{"from":"Market & 5th","to":"Market & 4th","weight":2},{"from":"Market & 4th","to":"River & 4th","weight":3},{"from":"River & 4th","to":"Market & 4th","weight":3},{"from":"Market & 5th","to":"River & 5th","weight":2},{"from":"River & 5th","to":"Market & 5th","weight":2},{"from":"River & 1st","to":"River & 2nd","weight":3},{"from":"River & 2nd","to":"River & 1st","weight":3},{"from":"River & 2nd","to":"River & 3rd","weight":2},{"from":"River & 3rd","to":"River & 2nd","weight":2},{"from":"River & 3rd","to":"River & 4th","weight":2},{"from":"River & 4th","to":"River & 3rd","weight":2},{"from":"River & 4th","to":"River & 5th","weight":4},{"from":"River & 5th","to":"River & 4th","weight":4}],"details":{"vertices":20,"edges":60,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":4,"negativeWeights":false,"density":0.15789473684210525,"inDegree":{"min":2,"avg":3,"max":4},"outDegree":{"min":2,"avg":3,"max":4},"selfLoops":0,"components":1}},"problem":"How quick a route does a beam of three find from Pine & 1st to River & 5th, and how much less of the map does it look at than Dijkstra?","params":{"start":"Pine & 1st","goal":"River & 5th","width":3},"result":{"kind":"route","vertices":["Pine \u0026 1st","Pine \u0026 2nd","Main \u0026 2nd","Market \u0026 2nd","River \u0026 2nd","River \u0026 3rd","River \u0026 4th","River \u0026 5th"],"cost":17},"answer":"A beam of 3 finds a drive of 17 minutes from Pine & 1st to River & 5th. The quickest route takes 15, so the beam dropped the paths that led to it.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"dropped","label":"Reached only by dropped paths","color":"#64748B","shape":"dashed-square"},{"id":"on","label":"On a kept path","color":"#56B4E9","shape":"filled"},{"id":"end","label":"End of a kept path","color":"#E69F00","shape":"ring"},{"id":"error","label":"Dead end of the last kept paths","color":"#D55E00","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"kept","label":"On a kept path","color":"#56B4E9","shape":"thick"},{"id":"dropped","label":"On a dropped path","color":"#64748B","shape":"dotted"},{"id":"tree","label":"Route the beam found","color":"#009E73","shape":"thick"}],"panels":[{"id":"kept","title":"Kept paths, best first","kind":"list"},{"id":"numbers","title":"So far","kind":"numbers"}]},"steps":[{"say":"Start one path at Pine & 1st. 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 River & 5th comes first.","ops":[{"v":"Pine & 1st","state":"end"},{"panel":"kept","list":[{"key":"Pine & 1st","note":"0 + 0 = 0"}]},{"panel":"numbers","set":{"Paths kept":"1"}},{"panel":"numbers","set":{"Paths dropped":"0"}},{"panel":"numbers","set":{"Best kept path so far":"0 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"1"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 1: extending the kept paths by one edge makes 2 paths, no more than the width, so keep them all.","ops":[{"panel":"kept","list":[{"key":"Pine & 2nd","note":"2 + 7.2839 = 9.2839"},{"key":"Main & 1st","note":"2 + 7.7821 = 9.7821"}]},{"e":["Pine & 1st","Main & 1st"],"state":"kept"},{"e":["Pine & 1st","Pine & 2nd"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 2nd","state":"end"},{"v":"Main & 1st","state":"end"},{"panel":"numbers","set":{"Paths kept":"2"}},{"panel":"numbers","set":{"Paths dropped":"0"}},{"panel":"numbers","set":{"Best kept path so far":"2 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"3"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 2: extending the kept paths by one edge makes 4 paths. Keep the best 3 paths, ending at Pine & 3rd, Main & 2nd and Main & 2nd, and drop 1.","ops":[{"panel":"kept","list":[{"key":"Pine & 3rd","note":"5 + 6.1784 = 11.1784"},{"key":"Main & 2nd","note":"5 + 6.3272 = 11.3272"},{"key":"Main & 2nd","note":"5 + 6.3272 = 11.3272"}]},{"e":["Main & 1st","Market & 1st"],"state":"dropped"},{"v":"Market & 1st","state":"dropped"},{"e":["Main & 1st","Main & 2nd"],"state":"kept"},{"e":["Pine & 2nd","Main & 2nd"],"state":"kept"},{"e":["Pine & 2nd","Pine & 3rd"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Main & 2nd","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 3rd","state":"on"},{"v":"Pine & 3rd","state":"end"},{"v":"Main & 2nd","state":"end"},{"v":"Main & 2nd","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"1"}},{"panel":"numbers","set":{"Best kept path so far":"5 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"6"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 3: extending the kept paths by one edge makes 8 paths. Keep the best 3 paths, ending at Main & 3rd, Market & 2nd and Market & 2nd, and drop 5.","ops":[{"panel":"kept","list":[{"key":"Main & 3rd","note":"7 + 4.9401 = 11.9401"},{"key":"Market & 2nd","note":"7 + 5.5562 = 12.5562"},{"key":"Market & 2nd","note":"7 + 5.5562 = 12.5562"}]},{"e":["Pine & 3rd","Pine & 4th"],"state":"dropped"},{"v":"Pine & 4th","state":"dropped"},{"e":["Main & 2nd","Main & 3rd"],"state":"dropped"},{"e":["Main & 2nd","Main & 3rd"],"state":"dropped"},{"e":["Main & 2nd","Pine & 2nd"],"state":"dropped"},{"e":["Main & 2nd","Main & 1st"],"state":"dropped"},{"e":["Main & 2nd","Market & 2nd"],"state":"kept"},{"e":["Pine & 3rd","Main & 3rd"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Main & 2nd","state":"on"},{"v":"Main & 3rd","state":"on"},{"v":"Market & 2nd","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 3rd","state":"on"},{"v":"Main & 3rd","state":"end"},{"v":"Market & 2nd","state":"end"},{"v":"Market & 2nd","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"6"}},{"panel":"numbers","set":{"Best kept path so far":"7 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"9"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 4: extending the kept paths by one edge makes 7 paths. Keep the best 3 paths, ending at Market & 3rd, River & 2nd and River & 2nd, and drop 4.","ops":[{"panel":"kept","list":[{"key":"Market & 3rd","note":"10 + 3.8593 = 13.8593"},{"key":"River & 2nd","note":"9 + 5.3228 = 14.3228"},{"key":"River & 2nd","note":"9 + 5.3228 = 14.3228"}]},{"e":["Main & 3rd","Main & 4th"],"state":"dropped"},{"v":"Main & 4th","state":"dropped"},{"e":["Market & 2nd","Market & 1st"],"state":"dropped"},{"v":"Market & 1st","state":"dropped"},{"e":["Market & 2nd","Market & 1st"],"state":"dropped"},{"v":"Market & 1st","state":"dropped"},{"e":["Main & 3rd","Main & 2nd"],"state":"dropped"},{"e":["Main & 3rd","Market & 3rd"],"state":"kept"},{"e":["Market & 2nd","River & 2nd"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Main & 2nd","state":"on"},{"v":"Main & 3rd","state":"on"},{"v":"Market & 2nd","state":"on"},{"v":"Market & 3rd","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 3rd","state":"on"},{"v":"River & 2nd","state":"on"},{"v":"Market & 3rd","state":"end"},{"v":"River & 2nd","state":"end"},{"v":"River & 2nd","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"10"}},{"panel":"numbers","set":{"Best kept path so far":"10 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"12"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 5: extending the kept paths by one edge makes 6 paths. Keep the best 3 paths, ending at River & 3rd, River & 3rd and Market & 4th, and drop 3.","ops":[{"panel":"kept","list":[{"key":"River & 3rd","note":"11 + 3.6299 = 14.6299"},{"key":"River & 3rd","note":"11 + 3.6299 = 14.6299"},{"key":"Market & 4th","note":"13 + 2.6842 = 15.6842"}]},{"e":["Market & 3rd","River & 3rd"],"state":"dropped"},{"e":["River & 2nd","River & 1st"],"state":"dropped"},{"v":"River & 1st","state":"dropped"},{"e":["River & 2nd","River & 1st"],"state":"dropped"},{"v":"River & 1st","state":"dropped"},{"e":["Market & 3rd","Market & 4th"],"state":"kept"},{"e":["River & 2nd","River & 3rd"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Main & 2nd","state":"on"},{"v":"Main & 3rd","state":"on"},{"v":"Market & 2nd","state":"on"},{"v":"Market & 3rd","state":"on"},{"v":"Market & 4th","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 3rd","state":"on"},{"v":"River & 2nd","state":"on"},{"v":"River & 3rd","state":"on"},{"v":"River & 3rd","state":"end"},{"v":"River & 3rd","state":"end"},{"v":"Market & 4th","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"13"}},{"panel":"numbers","set":{"Best kept path so far":"11 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"15"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 6: extending the kept paths by one edge makes 7 paths. Keep the best 3 paths, ending at River & 4th, River & 4th and Market & 5th, and drop 4.","ops":[{"panel":"kept","list":[{"key":"River & 4th","note":"13 + 1.9608 = 14.9608"},{"key":"River & 4th","note":"13 + 1.9608 = 14.9608"},{"key":"Market & 5th","note":"15 + 1.875 = 16.875"}]},{"e":["River & 3rd","Market & 3rd"],"state":"dropped"},{"e":["River & 3rd","Market & 3rd"],"state":"dropped"},{"e":["Market & 4th","River & 4th"],"state":"dropped"},{"e":["Market & 4th","Main & 4th"],"state":"dropped"},{"v":"Main & 4th","state":"dropped"},{"e":["Market & 4th","Market & 5th"],"state":"kept"},{"e":["River & 3rd","River & 4th"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Main & 2nd","state":"on"},{"v":"Main & 3rd","state":"on"},{"v":"Market & 2nd","state":"on"},{"v":"Market & 3rd","state":"on"},{"v":"Market & 4th","state":"on"},{"v":"Market & 5th","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 3rd","state":"on"},{"v":"River & 2nd","state":"on"},{"v":"River & 3rd","state":"on"},{"v":"River & 4th","state":"on"},{"v":"River & 4th","state":"end"},{"v":"River & 4th","state":"end"},{"v":"Market & 5th","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"17"}},{"panel":"numbers","set":{"Best kept path so far":"13 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"17"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}}]},{"say":"Step 7: extending the kept paths by one edge makes 6 paths. Keep the best 3 paths, ending at River & 5th, River & 5th and River & 5th, and drop 3. A kept path reaches River & 5th, at 17 minutes, so the beam stops.","ops":[{"panel":"kept","list":[{"key":"River & 5th","note":"17 + 0 = 17"},{"key":"River & 5th","note":"17 + 0 = 17"},{"key":"River & 5th","note":"17 + 0 = 17"}]},{"e":["River & 4th","Market & 4th"],"state":"dropped"},{"e":["River & 4th","Market & 4th"],"state":"dropped"},{"e":["Market & 5th","Main & 5th"],"state":"dropped"},{"v":"Main & 5th","state":"dropped"},{"e":["Market & 5th","River & 5th"],"state":"kept"},{"e":["River & 4th","River & 5th"],"state":"kept"},{"v":"Main & 1st","state":"on"},{"v":"Main & 2nd","state":"on"},{"v":"Main & 3rd","state":"on"},{"v":"Market & 2nd","state":"on"},{"v":"Market & 3rd","state":"on"},{"v":"Market & 4th","state":"on"},{"v":"Market & 5th","state":"on"},{"v":"Pine & 1st","state":"on"},{"v":"Pine & 2nd","state":"on"},{"v":"Pine & 3rd","state":"on"},{"v":"River & 2nd","state":"on"},{"v":"River & 3rd","state":"on"},{"v":"River & 4th","state":"on"},{"v":"River & 5th","state":"on"},{"v":"River & 5th","state":"end"},{"v":"River & 5th","state":"end"},{"v":"River & 5th","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"20"}},{"panel":"numbers","set":{"Best kept path so far":"17 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"15 min"}},{"panel":"numbers","set":{"Vertices looked at":"19"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"20"}},{"e":["Pine & 1st","Pine & 2nd"],"state":"tree"},{"e":["Pine & 2nd","Main & 2nd"],"state":"tree"},{"e":["Main & 2nd","Market & 2nd"],"state":"tree"},{"e":["Market & 2nd","River & 2nd"],"state":"tree"},{"e":["River & 2nd","River & 3rd"],"state":"tree"},{"e":["River & 3rd","River & 4th"],"state":"tree"},{"e":["River & 4th","River & 5th"],"state":"tree"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"goal := where[\"River & 5th\"]\nscore := func(e *gograph.Edge[string], soFar float64) float64 {\n\tp := where[e.Destination().Label()]\n\treturn soFar + e.Weight() + math.Hypot(p[0]-goal[0], p[1]-goal[1])/speed\n}\n\nroute, minutes, err := path.Beam(g, \"Pine & 1st\", \"River & 5th\", 3, score)\nif err != nil {\n\treturn err // path.ErrUnreachable when every kept path runs into a dead end\n}\nfmt.Println(minutes)\nfor _, v := range route {\n\tfmt.Println(v.Label())\n}"}
