{"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":"metro-region","name":"Metro region","description":"A hundred towns, T1 to T100, where T stands for town, numbered row by row from the top left with ten to a row. Two fast motorways cross at T45: one runs from T41 to T50, the other through T5, T15 and on down to T95. Local roads join neighboring towns, a few of them one way, and each edge is the travel time in minutes.","family":"road","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"T1","x":58,"y":56},{"id":"T2","x":157,"y":56},{"id":"T3","x":257,"y":62},{"id":"T4","x":359,"y":61},{"id":"T5","x":454,"y":61},{"id":"T6","x":547,"y":50},{"id":"T7","x":653,"y":55},{"id":"T8","x":750,"y":63},{"id":"T9","x":847,"y":67},{"id":"T10","x":941,"y":64},{"id":"T11","x":55,"y":156},{"id":"T12","x":155,"y":153},{"id":"T13","x":263,"y":148},{"id":"T14","x":362,"y":149},{"id":"T15","x":452,"y":149},{"id":"T16","x":540,"y":162},{"id":"T17","x":640,"y":150},{"id":"T18","x":740,"y":149},{"id":"T19","x":835,"y":164},{"id":"T20","x":936,"y":162},{"id":"T21","x":59,"y":247},{"id":"T22","x":164,"y":250},{"id":"T23","x":252,"y":253},{"id":"T24","x":358,"y":265},{"id":"T25","x":450,"y":259},{"id":"T26","x":559,"y":262},{"id":"T27","x":639,"y":254},{"id":"T28","x":739,"y":257},{"id":"T29","x":852,"y":264},{"id":"T30","x":940,"y":254},{"id":"T31","x":69,"y":350},{"id":"T32","x":157,"y":346},{"id":"T33","x":258,"y":362},{"id":"T34","x":353,"y":356},{"id":"T35","x":453,"y":356},{"id":"T36","x":558,"y":359},{"id":"T37","x":640,"y":360},{"id":"T38","x":742,"y":352},{"id":"T39","x":848,"y":361},{"id":"T40","x":940,"y":356},{"id":"T41","x":62,"y":457},{"id":"T42","x":161,"y":455},{"id":"T43","x":254,"y":448},{"id":"T44","x":345,"y":449},{"id":"T45","x":444,"y":455},{"id":"T46","x":544,"y":449},{"id":"T47","x":652,"y":460},{"id":"T48","x":737,"y":448},{"id":"T49","x":849,"y":448},{"id":"T50","x":946,"y":449},{"id":"T51","x":58,"y":546},{"id":"T52","x":150,"y":550},{"id":"T53","x":258,"y":540},{"id":"T54","x":354,"y":548},{"id":"T55","x":445,"y":540},{"id":"T56","x":554,"y":553},{"id":"T57","x":652,"y":547},{"id":"T58","x":750,"y":552},{"id":"T59","x":842,"y":550},{"id":"T60","x":948,"y":542},{"id":"T61","x":56,"y":637},{"id":"T62","x":158,"y":648},{"id":"T63","x":259,"y":653},{"id":"T64","x":356,"y":639},{"id":"T65","x":444,"y":639},{"id":"T66","x":556,"y":652},{"id":"T67","x":653,"y":639},{"id":"T68","x":748,"y":655},{"id":"T69","x":840,"y":655},{"id":"T70","x":948,"y":649},{"id":"T71","x":63,"y":740},{"id":"T72","x":163,"y":738},{"id":"T73","x":249,"y":742},{"id":"T74","x":352,"y":752},{"id":"T75","x":450,"y":753},{"id":"T76","x":544,"y":748},{"id":"T77","x":655,"y":753},{"id":"T78","x":748,"y":736},{"id":"T79","x":840,"y":747},{"id":"T80","x":939,"y":747},{"id":"T81","x":57,"y":841},{"id":"T82","x":157,"y":844},{"id":"T83","x":249,"y":843},{"id":"T84","x":347,"y":837},{"id":"T85","x":447,"y":841},{"id":"T86","x":541,"y":847},{"id":"T87","x":637,"y":834},{"id":"T88","x":738,"y":839},{"id":"T89","x":836,"y":848},{"id":"T90","x":942,"y":833},{"id":"T91","x":54,"y":940},{"id":"T92","x":164,"y":939},{"id":"T93","x":256,"y":931},{"id":"T94","x":354,"y":946},{"id":"T95","x":446,"y":949},{"id":"T96","x":542,"y":935},{"id":"T97","x":654,"y":937},{"id":"T98","x":750,"y":948},{"id":"T99","x":848,"y":935},{"id":"T100","x":933,"y":937}],"edges":[{"from":"T1","to":"T2","weight":7},{"from":"T2","to":"T1","weight":7},{"from":"T1","to":"T11","weight":6},{"from":"T11","to":"T1","weight":6},{"from":"T2","to":"T3","weight":6},{"from":"T3","to":"T2","weight":6},{"from":"T2","to":"T12","weight":7},{"from":"T3","to":"T4","weight":5},{"from":"T4","to":"T3","weight":5},{"from":"T3","to":"T13","weight":9},{"from":"T13","to":"T3","weight":9},{"from":"T4","to":"T5","weight":7},{"from":"T5","to":"T4","weight":7},{"from":"T4","to":"T14","weight":8},{"from":"T14","to":"T4","weight":8},{"from":"T5","to":"T6","weight":4},{"from":"T6","to":"T5","weight":4},{"from":"T5","to":"T15","weight":2},{"from":"T15","to":"T5","weight":2},{"from":"T6","to":"T7","weight":4},{"from":"T7","to":"T6","weight":4},{"from":"T6","to":"T16","weight":5},{"from":"T16","to":"T6","weight":5},{"from":"T7","to":"T8","weight":4},{"from":"T8","to":"T7","weight":4},{"from":"T17","to":"T7","weight":8},{"from":"T8","to":"T9","weight":5},{"from":"T9","to":"T8","weight":5},{"from":"T8","to":"T18","weight":7},{"from":"T18","to":"T8","weight":7},{"from":"T9","to":"T10","weight":7},{"from":"T10","to":"T9","weight":7},{"from":"T10","to":"T20","weight":6},{"from":"T20","to":"T10","weight":6},{"from":"T11","to":"T12","weight":9},{"from":"T12","to":"T11","weight":9},{"from":"T21","to":"T11","weight":6},{"from":"T11","to":"T22","weight":10},{"from":"T22","to":"T11","weight":10},{"from":"T12","to":"T13","weight":4},{"from":"T13","to":"T12","weight":4},{"from":"T12","to":"T22","weight":4},{"from":"T22","to":"T12","weight":4},{"from":"T13","to":"T22","weight":7},{"from":"T22","to":"T13","weight":7},{"from":"T13","to":"T14","weight":5},{"from":"T14","to":"T15","weight":6},{"from":"T15","to":"T14","weight":6},{"from":"T14","to":"T24","weight":9},{"from":"T24","to":"T14","weight":9},{"from":"T15","to":"T16","weight":4},{"from":"T16","to":"T15","weight":4},{"from":"T15","to":"T25","weight":2},{"from":"T25","to":"T15","weight":2},{"from":"T15","to":"T26","weight":9},{"from":"T26","to":"T15","weight":9},{"from":"T16","to":"T17","weight":9},{"from":"T17","to":"T16","weight":9},{"from":"T16","to":"T26","weight":8},{"from":"T26","to":"T16","weight":8},{"from":"T17","to":"T26","weight":7},{"from":"T26","to":"T17","weight":7},{"from":"T17","to":"T18","weight":9},{"from":"T18","to":"T17","weight":9},{"from":"T17","to":"T27","weight":9},{"from":"T27","to":"T17","weight":9},{"from":"T17","to":"T28","weight":11},{"from":"T28","to":"T17","weight":11},{"from":"T18","to":"T19","weight":7},{"from":"T19","to":"T18","weight":7},{"from":"T18","to":"T28","weight":6},{"from":"T28","to":"T18","weight":6},{"from":"T19","to":"T20","weight":8},{"from":"T20","to":"T19","weight":8},{"from":"T29","to":"T19","weight":9},{"from":"T19","to":"T30","weight":10},{"from":"T30","to":"T19","weight":10},{"from":"T20","to":"T30","weight":9},{"from":"T30","to":"T20","weight":9},{"from":"T21","to":"T22","weight":8},{"from":"T22","to":"T21","weight":8},{"from":"T21","to":"T31","weight":7},{"from":"T31","to":"T21","weight":7},{"from":"T22","to":"T32","weight":6},{"from":"T32","to":"T22","weight":6},{"from":"T23","to":"T24","weight":5},{"from":"T24","to":"T23","weight":5},{"from":"T23","to":"T33","weight":8},{"from":"T33","to":"T23","weight":8},{"from":"T24","to":"T25","weight":9},{"from":"T25","to":"T24","weight":9},{"from":"T24","to":"T34","weight":6},{"from":"T25","to":"T26","weight":6},{"from":"T26","to":"T25","weight":6},{"from":"T25","to":"T35","weight":2},{"from":"T35","to":"T25","weight":2},{"from":"T27","to":"T36","weight":10},{"from":"T36","to":"T27","weight":10},{"from":"T27","to":"T37","weight":6},{"from":"T37","to":"T27","weight":6},{"from":"T28","to":"T37","weight":10},{"from":"T37","to":"T28","weight":10},{"from":"T28","to":"T29","weight":5},{"from":"T29","to":"T28","weight":5},{"from":"T38","to":"T28","weight":8},{"from":"T30","to":"T29","weight":6},{"from":"T29","to":"T39","weight":9},{"from":"T39","to":"T29","weight":9},{"from":"T30","to":"T40","weight":8},{"from":"T40","to":"T30","weight":8},{"from":"T31","to":"T42","weight":9},{"from":"T42","to":"T31","weight":9},{"from":"T32","to":"T33","weight":6},{"from":"T33","to":"T32","weight":6},{"from":"T32","to":"T42","weight":4},{"from":"T42","to":"T32","weight":4},{"from":"T33","to":"T34","weight":4},{"from":"T34","to":"T33","weight":4},{"from":"T33","to":"T43","weight":9},{"from":"T43","to":"T33","weight":9},{"from":"T34","to":"T35","weight":5},{"from":"T35","to":"T34","weight":5},{"from":"T34","to":"T44","weight":4},{"from":"T44","to":"T34","weight":4},{"from":"T35","to":"T36","weight":7},{"from":"T36","to":"T35","weight":7},{"from":"T35","to":"T45","weight":2},{"from":"T45","to":"T35","weight":2},{"from":"T35","to":"T46","weight":7},{"from":"T46","to":"T35","weight":7},{"from":"T37","to":"T36","weight":4},{"from":"T46","to":"T36","weight":9},{"from":"T37","to":"T38","weight":8},{"from":"T38","to":"T37","weight":8},{"from":"T37","to":"T47","weight":8},{"from":"T47","to":"T37","weight":8},{"from":"T38","to":"T39","weight":6},{"from":"T39","to":"T38","weight":6},{"from":"T38","to":"T48","weight":4},{"from":"T48","to":"T38","weight":4},{"from":"T39","to":"T40","weight":7},{"from":"T40","to":"T39","weight":7},{"from":"T39","to":"T49","weight":5},{"from":"T49","to":"T39","weight":5},{"from":"T40","to":"T50","weight":4},{"from":"T50","to":"T40","weight":4},{"from":"T41","to":"T42","weight":2},{"from":"T42","to":"T41","weight":2},{"from":"T41","to":"T51","weight":4},{"from":"T42","to":"T43","weight":3},{"from":"T43","to":"T42","weight":3},{"from":"T42","to":"T52","weight":7},{"from":"T52","to":"T42","weight":7},{"from":"T43","to":"T44","weight":2},{"from":"T44","to":"T43","weight":2},{"from":"T43","to":"T53","weight":8},{"from":"T53","to":"T43","weight":8},{"from":"T44","to":"T53","weight":11},{"from":"T53","to":"T44","weight":11},{"from":"T44","to":"T45","weight":3},{"from":"T45","to":"T44","weight":3},{"from":"T44","to":"T54","weight":7},{"from":"T54","to":"T44","weight":7},{"from":"T45","to":"T46","weight":3},{"from":"T46","to":"T45","weight":3},{"from":"T45","to":"T55","weight":2},{"from":"T55","to":"T45","weight":2},{"from":"T46","to":"T47","weight":3},{"from":"T47","to":"T46","weight":3},{"from":"T56","to":"T46","weight":7},{"from":"T47","to":"T48","weight":3},{"from":"T48","to":"T47","weight":3},{"from":"T47","to":"T57","weight":5},{"from":"T57","to":"T47","weight":5},{"from":"T48","to":"T49","weight":2},{"from":"T49","to":"T48","weight":2},{"from":"T48","to":"T58","weight":7},{"from":"T58","to":"T48","weight":7},{"from":"T49","to":"T50","weight":2},{"from":"T50","to":"T49","weight":2},{"from":"T49","to":"T59","weight":4},{"from":"T50","to":"T60","weight":6},{"from":"T60","to":"T50","weight":6},{"from":"T51","to":"T52","weight":9},{"from":"T52","to":"T51","weight":9},{"from":"T51","to":"T61","weight":8},{"from":"T61","to":"T51","weight":8},{"from":"T52","to":"T61","weight":8},{"from":"T61","to":"T52","weight":8},{"from":"T52","to":"T53","weight":6},{"from":"T53","to":"T52","weight":6},{"from":"T52","to":"T62","weight":7},{"from":"T62","to":"T52","weight":7},{"from":"T53","to":"T54","weight":7},{"from":"T54","to":"T53","weight":7},{"from":"T54","to":"T55","weight":6},{"from":"T55","to":"T54","weight":6},{"from":"T54","to":"T64","weight":4},{"from":"T64","to":"T54","weight":4},{"from":"T55","to":"T56","weight":6},{"from":"T55","to":"T65","weight":3},{"from":"T65","to":"T55","weight":3},{"from":"T55","to":"T66","weight":10},{"from":"T66","to":"T55","weight":10},{"from":"T56","to":"T57","weight":7},{"from":"T57","to":"T56","weight":7},{"from":"T57","to":"T58","weight":6},{"from":"T58","to":"T57","weight":6},{"from":"T67","to":"T57","weight":6},{"from":"T57","to":"T68","weight":10},{"from":"T68","to":"T57","weight":10},{"from":"T58","to":"T59","weight":8},{"from":"T59","to":"T58","weight":8},{"from":"T58","to":"T68","weight":4},{"from":"T68","to":"T58","weight":4},{"from":"T59","to":"T60","weight":8},{"from":"T60","to":"T59","weight":8},{"from":"T59","to":"T69","weight":9},{"from":"T69","to":"T59","weight":9},{"from":"T60","to":"T70","weight":7},{"from":"T70","to":"T60","weight":7},{"from":"T61","to":"T62","weight":4},{"from":"T62","to":"T61","weight":4},{"from":"T61","to":"T71","weight":8},{"from":"T71","to":"T61","weight":8},{"from":"T62","to":"T63","weight":9},{"from":"T62","to":"T72","weight":4},{"from":"T72","to":"T62","weight":4},{"from":"T63","to":"T64","weight":8},{"from":"T64","to":"T63","weight":8},{"from":"T63","to":"T73","weight":4},{"from":"T73","to":"T63","weight":4},{"from":"T63","to":"T74","weight":10},{"from":"T74","to":"T63","weight":10},{"from":"T64","to":"T65","weight":7},{"from":"T65","to":"T64","weight":7},{"from":"T64","to":"T74","weight":4},{"from":"T74","to":"T64","weight":4},{"from":"T65","to":"T66","weight":4},{"from":"T66","to":"T65","weight":4},{"from":"T65","to":"T75","weight":2},{"from":"T75","to":"T65","weight":2},{"from":"T66","to":"T67","weight":8},{"from":"T67","to":"T66","weight":8},{"from":"T66","to":"T76","weight":5},{"from":"T76","to":"T66","weight":5},{"from":"T66","to":"T77","weight":11},{"from":"T77","to":"T66","weight":11},{"from":"T68","to":"T67","weight":8},{"from":"T67","to":"T77","weight":8},{"from":"T77","to":"T67","weight":8},{"from":"T68","to":"T78","weight":7},{"from":"T78","to":"T68","weight":7},{"from":"T69","to":"T79","weight":5},{"from":"T79","to":"T69","weight":5},{"from":"T71","to":"T72","weight":9},{"from":"T72","to":"T71","weight":9},{"from":"T71","to":"T81","weight":5},{"from":"T81","to":"T71","weight":5},{"from":"T72","to":"T82","weight":8},{"from":"T82","to":"T72","weight":8},{"from":"T73","to":"T74","weight":7},{"from":"T74","to":"T73","weight":7},{"from":"T73","to":"T83","weight":7},{"from":"T83","to":"T73","weight":7},{"from":"T75","to":"T74","weight":6},{"from":"T75","to":"T76","weight":8},{"from":"T76","to":"T75","weight":8},{"from":"T75","to":"T85","weight":2},{"from":"T85","to":"T75","weight":2},{"from":"T76","to":"T77","weight":4},{"from":"T77","to":"T76","weight":4},{"from":"T76","to":"T86","weight":6},{"from":"T86","to":"T76","weight":6},{"from":"T77","to":"T78","weight":7},{"from":"T78","to":"T77","weight":7},{"from":"T77","to":"T87","weight":4},{"from":"T87","to":"T77","weight":4},{"from":"T78","to":"T89","weight":8},{"from":"T89","to":"T78","weight":8},{"from":"T79","to":"T89","weight":6},{"from":"T89","to":"T79","weight":6},{"from":"T80","to":"T90","weight":4},{"from":"T90","to":"T80","weight":4},{"from":"T81","to":"T82","weight":4},{"from":"T82","to":"T81","weight":4},{"from":"T81","to":"T91","weight":4},{"from":"T91","to":"T81","weight":4},{"from":"T82","to":"T83","weight":8},{"from":"T83","to":"T82","weight":8},{"from":"T82","to":"T92","weight":4},{"from":"T92","to":"T82","weight":4},{"from":"T82","to":"T93","weight":10},{"from":"T93","to":"T82","weight":10},{"from":"T83","to":"T84","weight":5},{"from":"T84","to":"T83","weight":5},{"from":"T83","to":"T93","weight":9},{"from":"T93","to":"T83","weight":9},{"from":"T84","to":"T93","weight":11},{"from":"T93","to":"T84","weight":11},{"from":"T84","to":"T85","weight":6},{"from":"T85","to":"T84","weight":6},{"from":"T84","to":"T94","weight":5},{"from":"T94","to":"T84","weight":5},{"from":"T85","to":"T86","weight":5},{"from":"T86","to":"T85","weight":5},{"from":"T85","to":"T95","weight":3},{"from":"T95","to":"T85","weight":3},{"from":"T86","to":"T95","weight":10},{"from":"T95","to":"T86","weight":10},{"from":"T86","to":"T87","weight":4},{"from":"T87","to":"T86","weight":4},{"from":"T86","to":"T96","weight":7},{"from":"T96","to":"T86","weight":7},{"from":"T87","to":"T96","weight":10},{"from":"T96","to":"T87","weight":10},{"from":"T87","to":"T88","weight":6},{"from":"T88","to":"T87","weight":6},{"from":"T87","to":"T97","weight":5},{"from":"T97","to":"T87","weight":5},{"from":"T88","to":"T89","weight":5},{"from":"T89","to":"T88","weight":5},{"from":"T88","to":"T98","weight":9},{"from":"T98","to":"T88","weight":9},{"from":"T89","to":"T90","weight":4},{"from":"T90","to":"T89","weight":4},{"from":"T89","to":"T99","weight":7},{"from":"T99","to":"T89","weight":7},{"from":"T90","to":"T100","weight":4},{"from":"T100","to":"T90","weight":4},{"from":"T91","to":"T92","weight":4},{"from":"T92","to":"T91","weight":4},{"from":"T92","to":"T93","weight":7},{"from":"T93","to":"T92","weight":7},{"from":"T94","to":"T95","weight":4},{"from":"T95","to":"T94","weight":4},{"from":"T95","to":"T96","weight":4},{"from":"T96","to":"T95","weight":4},{"from":"T96","to":"T97","weight":7},{"from":"T97","to":"T96","weight":7},{"from":"T97","to":"T98","weight":6},{"from":"T98","to":"T97","weight":6},{"from":"T98","to":"T99","weight":7},{"from":"T99","to":"T98","weight":7},{"from":"T99","to":"T100","weight":6},{"from":"T100","to":"T99","weight":6}],"details":{"vertices":100,"edges":346,"directed":true,"weighted":true,"acyclic":false,"weightMin":2,"weightMax":11,"negativeWeights":false,"density":0.03494949494949495,"inDegree":{"min":1,"avg":3.46,"max":5},"outDegree":{"min":1,"avg":3.46,"max":6},"selfLoops":0,"components":1}},"problem":"How quick a route does a beam of three find from T45 to T100, and how much less of the map does it look at than Dijkstra?","params":{"start":"T45","goal":"T100","width":3},"result":{"kind":"route","vertices":["T45","T55","T65","T75","T85","T86","T87","T88","T89","T90","T100"],"cost":37},"answer":"A beam of 3 finds a drive of 37 minutes from T45 to T100. That's the quickest route, the one Dijkstra finds.","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 T45. 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 T100 comes first.","ops":[{"v":"T45","state":"end"},{"panel":"kept","list":[{"key":"T45","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":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"1"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 1: extending the kept paths by one edge makes 4 paths. Keep the best 3 paths, ending at T55, T46 and T35, and drop 1.","ops":[{"panel":"kept","list":[{"key":"T55","note":"2 + 11.0214 = 13.0214"},{"key":"T46","note":"3 + 10.9335 = 13.9335"},{"key":"T35","note":"2 + 13.2033 = 15.2033"}]},{"e":["T45","T44"],"state":"dropped"},{"v":"T44","state":"dropped"},{"e":["T45","T35"],"state":"kept"},{"e":["T45","T46"],"state":"kept"},{"e":["T45","T55"],"state":"kept"},{"v":"T35","state":"on"},{"v":"T45","state":"on"},{"v":"T46","state":"on"},{"v":"T55","state":"on"},{"v":"T55","state":"end"},{"v":"T46","state":"end"},{"v":"T35","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"1"}},{"panel":"numbers","set":{"Best kept path so far":"2 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"5"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 2: extending the kept paths by one edge makes 11 paths. Keep the best 3 paths, ending at T65, T47 and T56, and drop 8.","ops":[{"panel":"kept","list":[{"key":"T65","note":"5 + 10.0326 = 15.0326"},{"key":"T47","note":"6 + 9.6991 = 15.6991"},{"key":"T56","note":"8 + 9.4524 = 17.4524"}]},{"e":["T35","T25"],"state":"dropped"},{"v":"T25","state":"dropped"},{"e":["T35","T46"],"state":"dropped"},{"e":["T55","T54"],"state":"dropped"},{"v":"T54","state":"dropped"},{"e":["T55","T66"],"state":"dropped"},{"v":"T66","state":"dropped"},{"e":["T35","T36"],"state":"dropped"},{"v":"T36","state":"dropped"},{"e":["T35","T34"],"state":"dropped"},{"v":"T34","state":"dropped"},{"e":["T46","T35"],"state":"dropped"},{"e":["T46","T36"],"state":"dropped"},{"v":"T36","state":"dropped"},{"e":["T45","T35"],"state":"dropped"},{"v":"T35","state":"dropped"},{"e":["T46","T47"],"state":"kept"},{"e":["T55","T56"],"state":"kept"},{"e":["T55","T65"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T46","state":"on"},{"v":"T47","state":"on"},{"v":"T55","state":"on"},{"v":"T56","state":"on"},{"v":"T65","state":"on"},{"v":"T65","state":"end"},{"v":"T47","state":"end"},{"v":"T56","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"9"}},{"panel":"numbers","set":{"Best kept path so far":"5 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"13"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 3: extending the kept paths by one edge makes 8 paths. Keep the best 3 paths, ending at T75, T66 and T48, and drop 5.","ops":[{"panel":"kept","list":[{"key":"T75","note":"7 + 9.0552 = 16.0552"},{"key":"T66","note":"9 + 8.2798 = 17.2798"},{"key":"T48","note":"9 + 9.2296 = 18.2296"}]},{"e":["T47","T57"],"state":"dropped"},{"v":"T57","state":"dropped"},{"e":["T65","T64"],"state":"dropped"},{"v":"T64","state":"dropped"},{"e":["T56","T57"],"state":"dropped"},{"v":"T57","state":"dropped"},{"e":["T47","T37"],"state":"dropped"},{"v":"T37","state":"dropped"},{"e":["T56","T46"],"state":"dropped"},{"e":["T55","T56"],"state":"dropped"},{"v":"T56","state":"dropped"},{"e":["T47","T48"],"state":"kept"},{"e":["T65","T66"],"state":"kept"},{"e":["T65","T75"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T46","state":"on"},{"v":"T47","state":"on"},{"v":"T48","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T66","state":"on"},{"v":"T75","state":"on"},{"v":"T75","state":"end"},{"v":"T66","state":"end"},{"v":"T48","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"14"}},{"panel":"numbers","set":{"Best kept path so far":"7 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"18"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 4: extending the kept paths by one edge makes 9 paths. Keep the best 3 paths, ending at T85, T49 and T76, and drop 6.","ops":[{"panel":"kept","list":[{"key":"T85","note":"9 + 8.6791 = 17.6791"},{"key":"T49","note":"11 + 8.6926 = 19.6926"},{"key":"T76","note":"14 + 7.5769 = 21.5769"}]},{"e":["T75","T76"],"state":"dropped"},{"e":["T48","T58"],"state":"dropped"},{"v":"T58","state":"dropped"},{"e":["T75","T74"],"state":"dropped"},{"v":"T74","state":"dropped"},{"e":["T48","T38"],"state":"dropped"},{"v":"T38","state":"dropped"},{"e":["T66","T67"],"state":"dropped"},{"v":"T67","state":"dropped"},{"e":["T66","T77"],"state":"dropped"},{"v":"T77","state":"dropped"},{"e":["T48","T49"],"state":"kept"},{"e":["T66","T76"],"state":"kept"},{"e":["T75","T85"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T46","state":"on"},{"v":"T47","state":"on"},{"v":"T48","state":"on"},{"v":"T49","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T66","state":"on"},{"v":"T75","state":"on"},{"v":"T76","state":"on"},{"v":"T85","state":"on"},{"v":"T85","state":"end"},{"v":"T49","state":"end"},{"v":"T76","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"20"}},{"panel":"numbers","set":{"Best kept path so far":"9 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"26"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 5: extending the kept paths by one edge makes 9 paths. Keep the best 3 paths, ending at T95, T86 and T50, and drop 6.","ops":[{"panel":"kept","list":[{"key":"T95","note":"12 + 8.5346 = 20.5346"},{"key":"T86","note":"14 + 7.0464 = 21.0464"},{"key":"T50","note":"13 + 8.5526 = 21.5526"}]},{"e":["T49","T59"],"state":"dropped"},{"v":"T59","state":"dropped"},{"e":["T76","T77"],"state":"dropped"},{"v":"T77","state":"dropped"},{"e":["T85","T84"],"state":"dropped"},{"v":"T84","state":"dropped"},{"e":["T49","T39"],"state":"dropped"},{"v":"T39","state":"dropped"},{"e":["T76","T86"],"state":"dropped"},{"e":["T76","T75"],"state":"dropped"},{"e":["T65","T66"],"state":"dropped"},{"e":["T66","T76"],"state":"dropped"},{"v":"T76","state":"dropped"},{"v":"T66","state":"dropped"},{"e":["T49","T50"],"state":"kept"},{"e":["T85","T86"],"state":"kept"},{"e":["T85","T95"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T46","state":"on"},{"v":"T47","state":"on"},{"v":"T48","state":"on"},{"v":"T49","state":"on"},{"v":"T50","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T75","state":"on"},{"v":"T85","state":"on"},{"v":"T86","state":"on"},{"v":"T95","state":"on"},{"v":"T95","state":"end"},{"v":"T86","state":"end"},{"v":"T50","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"26"}},{"panel":"numbers","set":{"Best kept path so far":"12 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"32"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 6: extending the kept paths by one edge makes 9 paths. Keep the best 3 paths, ending at T96, T87 and T60, and drop 6.","ops":[{"panel":"kept","list":[{"key":"T96","note":"16 + 6.8503 = 22.8503"},{"key":"T87","note":"18 + 5.4908 = 23.4908"},{"key":"T60","note":"19 + 6.9252 = 25.9252"}]},{"e":["T95","T94"],"state":"dropped"},{"v":"T94","state":"dropped"},{"e":["T50","T40"],"state":"dropped"},{"v":"T40","state":"dropped"},{"e":["T86","T76"],"state":"dropped"},{"v":"T76","state":"dropped"},{"e":["T86","T96"],"state":"dropped"},{"e":["T95","T86"],"state":"dropped"},{"e":["T86","T95"],"state":"dropped"},{"e":["T50","T60"],"state":"kept"},{"e":["T86","T87"],"state":"kept"},{"e":["T95","T96"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T46","state":"on"},{"v":"T47","state":"on"},{"v":"T48","state":"on"},{"v":"T49","state":"on"},{"v":"T50","state":"on"},{"v":"T55","state":"on"},{"v":"T60","state":"on"},{"v":"T65","state":"on"},{"v":"T75","state":"on"},{"v":"T85","state":"on"},{"v":"T86","state":"on"},{"v":"T87","state":"on"},{"v":"T95","state":"on"},{"v":"T96","state":"on"},{"v":"T96","state":"end"},{"v":"T87","state":"end"},{"v":"T60","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"32"}},{"panel":"numbers","set":{"Best kept path so far":"16 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"37"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 7: extending the kept paths by one edge makes 9 paths. Keep the best 3 paths, ending at T88, T77 and T97, and drop 6.","ops":[{"panel":"kept","list":[{"key":"T88","note":"24 + 3.8235 = 27.8235"},{"key":"T77","note":"22 + 5.8406 = 27.8406"},{"key":"T97","note":"23 + 4.888 = 27.888"}]},{"e":["T87","T97"],"state":"dropped"},{"e":["T96","T86"],"state":"dropped"},{"e":["T60","T70"],"state":"dropped"},{"v":"T70","state":"dropped"},{"e":["T96","T87"],"state":"dropped"},{"e":["T60","T59"],"state":"dropped"},{"v":"T59","state":"dropped"},{"e":["T87","T96"],"state":"dropped"},{"e":["T46","T47"],"state":"dropped"},{"e":["T49","T50"],"state":"dropped"},{"e":["T48","T49"],"state":"dropped"},{"e":["T45","T46"],"state":"dropped"},{"e":["T50","T60"],"state":"dropped"},{"e":["T47","T48"],"state":"dropped"},{"v":"T60","state":"dropped"},{"v":"T50","state":"dropped"},{"v":"T48","state":"dropped"},{"v":"T47","state":"dropped"},{"v":"T49","state":"dropped"},{"v":"T46","state":"dropped"},{"e":["T87","T77"],"state":"kept"},{"e":["T87","T88"],"state":"kept"},{"e":["T96","T97"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T75","state":"on"},{"v":"T77","state":"on"},{"v":"T85","state":"on"},{"v":"T86","state":"on"},{"v":"T87","state":"on"},{"v":"T88","state":"on"},{"v":"T95","state":"on"},{"v":"T96","state":"on"},{"v":"T97","state":"on"},{"v":"T88","state":"end"},{"v":"T77","state":"end"},{"v":"T97","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"38"}},{"panel":"numbers","set":{"Best kept path so far":"24 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"40"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 8: extending the kept paths by one edge makes 8 paths. Keep the best 3 paths, ending at T89, T98 and T87, and drop 5.","ops":[{"panel":"kept","list":[{"key":"T89","note":"29 + 2.3063 = 31.3063"},{"key":"T98","note":"29 + 3.2119 = 32.2119"},{"key":"T87","note":"28 + 5.4908 = 33.4908"}]},{"e":["T77","T76"],"state":"dropped"},{"v":"T76","state":"dropped"},{"e":["T77","T78"],"state":"dropped"},{"v":"T78","state":"dropped"},{"e":["T88","T98"],"state":"dropped"},{"e":["T77","T67"],"state":"dropped"},{"v":"T67","state":"dropped"},{"e":["T77","T66"],"state":"dropped"},{"v":"T66","state":"dropped"},{"e":["T87","T77"],"state":"dropped"},{"v":"T77","state":"dropped"},{"e":["T88","T89"],"state":"kept"},{"e":["T97","T87"],"state":"kept"},{"e":["T97","T98"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T75","state":"on"},{"v":"T85","state":"on"},{"v":"T86","state":"on"},{"v":"T87","state":"on"},{"v":"T88","state":"on"},{"v":"T89","state":"on"},{"v":"T95","state":"on"},{"v":"T96","state":"on"},{"v":"T97","state":"on"},{"v":"T98","state":"on"},{"v":"T89","state":"end"},{"v":"T98","state":"end"},{"v":"T87","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"43"}},{"panel":"numbers","set":{"Best kept path so far":"29 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"43"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 9: extending the kept paths by one edge makes 9 paths. Keep the best 3 paths, ending at T90, T99 and T99, and drop 6.","ops":[{"panel":"kept","list":[{"key":"T90","note":"33 + 1.8288 = 34.8288"},{"key":"T99","note":"36 + 1.4896 = 37.4896"},{"key":"T99","note":"36 + 1.4896 = 37.4896"}]},{"e":["T87","T77"],"state":"dropped"},{"v":"T77","state":"dropped"},{"e":["T89","T79"],"state":"dropped"},{"v":"T79","state":"dropped"},{"e":["T87","T86"],"state":"dropped"},{"e":["T89","T78"],"state":"dropped"},{"v":"T78","state":"dropped"},{"e":["T98","T88"],"state":"dropped"},{"e":["T97","T87"],"state":"dropped"},{"e":["T89","T90"],"state":"kept"},{"e":["T89","T99"],"state":"kept"},{"e":["T98","T99"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T75","state":"on"},{"v":"T85","state":"on"},{"v":"T86","state":"on"},{"v":"T87","state":"on"},{"v":"T88","state":"on"},{"v":"T89","state":"on"},{"v":"T90","state":"on"},{"v":"T95","state":"on"},{"v":"T96","state":"on"},{"v":"T97","state":"on"},{"v":"T98","state":"on"},{"v":"T99","state":"on"},{"v":"T90","state":"end"},{"v":"T99","state":"end"},{"v":"T99","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"49"}},{"panel":"numbers","set":{"Best kept path so far":"33 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"46"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}}]},{"say":"Step 10: extending the kept paths by one edge makes 6 paths. Keep the best 3 paths, ending at T100, T80 and T100, and drop 3. A kept path reaches T100, at 37 minutes, so the beam stops.","ops":[{"panel":"kept","list":[{"key":"T100","note":"37 + 0 = 37"},{"key":"T80","note":"37 + 3.3304 = 40.3304"},{"key":"T100","note":"42 + 0 = 42"}]},{"e":["T99","T89"],"state":"dropped"},{"e":["T99","T98"],"state":"dropped"},{"e":["T95","T96"],"state":"dropped"},{"e":["T96","T97"],"state":"dropped"},{"e":["T98","T99"],"state":"dropped"},{"e":["T85","T95"],"state":"dropped"},{"e":["T97","T98"],"state":"dropped"},{"v":"T98","state":"dropped"},{"v":"T96","state":"dropped"},{"v":"T97","state":"dropped"},{"v":"T95","state":"dropped"},{"e":["T90","T80"],"state":"kept"},{"e":["T90","T100"],"state":"kept"},{"e":["T99","T100"],"state":"kept"},{"v":"T45","state":"on"},{"v":"T55","state":"on"},{"v":"T65","state":"on"},{"v":"T75","state":"on"},{"v":"T80","state":"on"},{"v":"T85","state":"on"},{"v":"T86","state":"on"},{"v":"T87","state":"on"},{"v":"T88","state":"on"},{"v":"T89","state":"on"},{"v":"T90","state":"on"},{"v":"T99","state":"on"},{"v":"T100","state":"on"},{"v":"T100","state":"end"},{"v":"T80","state":"end"},{"v":"T100","state":"end"},{"panel":"numbers","set":{"Paths kept":"3"}},{"panel":"numbers","set":{"Paths dropped":"52"}},{"panel":"numbers","set":{"Best kept path so far":"37 min"}},{"panel":"numbers","set":{"Quickest route, by Dijkstra":"37 min"}},{"panel":"numbers","set":{"Vertices looked at":"48"}},{"panel":"numbers","set":{"Dijkstra settles to reach goal":"100"}},{"e":["T45","T55"],"state":"tree"},{"e":["T55","T65"],"state":"tree"},{"e":["T65","T75"],"state":"tree"},{"e":["T75","T85"],"state":"tree"},{"e":["T85","T86"],"state":"tree"},{"e":["T86","T87"],"state":"tree"},{"e":["T87","T88"],"state":"tree"},{"e":["T88","T89"],"state":"tree"},{"e":["T89","T90"],"state":"tree"},{"e":["T90","T100"],"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[\"T100\"]\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, \"T45\", \"T100\", 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}"}
