Beam Search

Idea: At each level, generate successors but keep only the best (as measured by a heuristic or score) k states. Here k is the beam width.

BEAM_sEARCH(start, goal, k, score):
    beam = [start]

    while beam is not empty:
        candidates = []
        for state in beam:
            if state is goal:
                return path to state
            for each successor next of state:
                parent[next] = state
                add next to candidates

        sort candidates by score
        beam = best k candidates

    return failure
    return failure