search.py 文件源码

def random_weighted_selection(seq, n, weight_fn):
    """Pick n elements of seq, weighted according to weight_fn.
    That is, apply weight_fn to each element of seq, add up the total.
    Then choose an element e with probability weight[e]/total.
    Repeat n times, with replacement. """
    totals = []; runningtotal = 0
    for item in seq:
        runningtotal += weight_fn(item)
        totals.append(runningtotal)
    selections = []
    for s in range(n):
        r = random.uniform(0, totals[-1])
        for i in range(len(seq)):
            if totals[i] > r:
                selections.append(seq[i])
                break
    return selections


#_____________________________________________________________________________
# The remainder of this file implements examples for the search algorithms.

#______________________________________________________________________________
# Graphs and Graph Problems