from fractions import Fraction
first={'A':Fraction(60,100),'B':Fraction(40,100)}
next_step={'A':{'x':Fraction(51,100),'y':Fraction(49,100)},'B':{'z':Fraction(95,100),'w':Fraction(5,100)}}
beam_width=2
assert isinstance(beam_width,int) and 1 <= beam_width <= len(first)
assert sum(first.values())==1
assert all(sum(v.values())==1 for v in next_step.values())
paths=sorted(((a+' '+b,p*q) for a,p in first.items() for b,q in next_step[a].items()),key=lambda row:row[1],reverse=True)
greedy=max(first,key=first.get)
print('Greedy:',greedy,max(next_step[greedy],key=next_step[greedy].get))
for name,score in paths:print(name,format(float(score),'.3f'))
kept=sorted(first,key=first.get,reverse=True)[:beam_width]
beam_paths=[row for row in paths if row[0].split()[0] in kept]
print('Beam winner:',beam_paths[0][0],format(float(beam_paths[0][1]),'.3f'))