Source Code for Module gmisclib.beamsearch

 1   
 2   
 3 -def beamsearch(cost, extra, initial, B, E): 
 4          """A breadth-first beam search. 
 5          B = max number of options to keep, 
 6          E = max cost difference between best and worst threads in beam. 
 7          initial = [ starting positions ] 
 8          extra = arbitrary information for cost function. 
 9          cost = fn(state, extra) -> (total_cost, [next states], output_if_goal) 
10          """ 
11   
12          o = [] 
13          B = max(B, len(initial)) 
14          hlist = [ (0.0, tmp) for tmp in initial ] 
15          while len(hlist)>0: 
16                  # print "Len(hlist)=", len(hlist), "len(o)=", len(o) 
17                  hlist.sort() 
18                  if len(hlist) > B: 
19                          hlist = hlist[:B] 
20                  # print "E=", hlist[0][0], " to ", hlist[0][0]+E 
21                  hlist = filter(lambda q, e0=hlist[0][0], e=E: q[0]-e0<=e, hlist) 
22                  # print "               after: Len(hlist)=", len(hlist) 
23                  nlist = [] 
24                  while len(hlist) > 0: 
25                          c, point = hlist.pop(0) 
26                          newcost, nextsteps, is_goal = cost(point, extra) 
27                          if is_goal: 
28                                  o.append((newcost, is_goal)) 
29                          for t in nextsteps: 
30                                  nlist.append((newcost, t)) 
31                  hlist = nlist 
32          o.sort() 
33          return o 
34