'Runs beam search caption generation on a single image.
Args:
sess: TensorFlow Session object.
encoded_image: An encoded image string.
Returns:
A list of Caption sorted by descending score.'

def beam_search(self, sess, encoded_image):

    initial_state = self.model.feed_image(sess, encoded_image)
    initial_beam = Caption(sentence=[self.vocab.start_id], state=initial_state[0], logprob=0.0, score=0.0, metadata=[''])
    partial_captions = TopN(self.beam_size)
    partial_captions.push(initial_beam)
    complete_captions = TopN(self.beam_size)
    for _ in range((self.max_caption_length - 1)):
        partial_captions_list = partial_captions.extract()
        partial_captions.reset()
        input_feed = np.array([c.sentence[(-1)] for c in partial_captions_list])
        state_feed = np.array([c.state for c in partial_captions_list])
        (softmax, new_states, metadata) = self.model.inference_step(sess, input_feed, state_feed)
        for (i, partial_caption) in enumerate(partial_captions_list):
            word_probabilities = softmax[i]
            state = new_states[i]
            words_and_probs = list(enumerate(word_probabilities))
            words_and_probs.sort(key=(lambda x: (- x[1])))
            words_and_probs = words_and_probs[0:self.beam_size]
            for (w, p) in words_and_probs:
                if (p < 1e-12):
                    continue
                sentence = (partial_caption.sentence + [w])
                logprob = (partial_caption.logprob + math.log(p))
                score = logprob
                if metadata:
                    metadata_list = (partial_caption.metadata + [metadata[i]])
                else:
                    metadata_list = None
                if (w == self.vocab.end_id):
                    if (self.length_normalization_factor > 0):
                        score /= (len(sentence) ** self.length_normalization_factor)
                    beam = Caption(sentence, state, logprob, score, metadata_list)
                    complete_captions.push(beam)
                else:
                    beam = Caption(sentence, state, logprob, score, metadata_list)
                    partial_captions.push(beam)
        if (partial_captions.size() == 0):
            break
    if (not complete_captions.size()):
        complete_captions = partial_captions
    return complete_captions.extract(sort=True)
