Heuristic Search
(heuristic/all.hpp)

• View this file on GitHub
• Last update: 2026-08-12 20:17:35+09:00
• Include: #include "heuristic/all.hpp"

Start Here

The heuristic headers provide reusable search decisions. They do not know your problem’s state, moves, or score. In most solutions you still write:

1. a state representation;
2. a function that evaluates the state, or computes a move’s score difference;
3. a way to generate neighboring or child states;
4. the stopping condition, usually an iteration count or Timer.

The library handles the general part: deciding whether to accept a local move, or deciding which states survive to the next beam-search layer.

Which Search Should I Use?

Situation	Recommended tool	Why
Every state has nearby moves and greedy improvement works well	HillClimbing	Smallest overhead and simplest behavior.
Greedy search becomes trapped in local optima	SimulatedAnnealing	Sometimes accepts worse moves early, then becomes increasingly greedy.
A solution is constructed in a fixed sequence of decisions	beam_search	Keeps several promising partial solutions at every depth.

A useful starting progression is hill climbing, then simulated annealing if local optima are a problem. Use beam search when the problem naturally looks like a branching decision tree rather than repeated modification of one state.

Shared Terms

• A state is one candidate solution.
• A score is the value used to compare states.
• A move changes one state into a nearby state.
• Objective::maximize means larger scores are better.
• Objective::minimize means smaller scores are better.
• delta always means candidate_score - current_score, even when minimizing.

utilities/Timer and utilities/Random provide the usual time limit and randomness for local search.

Included Headers

Header	Contents
heuristic/objective.hpp	Shared minimization/maximization score ordering.
heuristic/hill_climbing.hpp	Greedy local-search acceptance with optional equal-score moves.
heuristic/simulated_annealing.hpp	Temperature schedules and probabilistic acceptance.
heuristic/beam_search.hpp	Memory-bounded layered search with simple and allocation-conscious child generation.

Include heuristic/all.hpp to use every heuristic header, or include only the specific header needed by the solution.

Depends on

• Beam Search (heuristic/beam_search.hpp)
• Hill Climbing (heuristic/hill_climbing.hpp)
• Heuristic Objective (heuristic/objective.hpp)
• Simulated Annealing (heuristic/simulated_annealing.hpp)

Verified with

• verify/heuristic/simulated_annealing.test.cpp

Code

#ifndef M1UNE_HEURISTIC_ALL_HPP
#define M1UNE_HEURISTIC_ALL_HPP 1

#include "beam_search.hpp"
#include "hill_climbing.hpp"
#include "objective.hpp"
#include "simulated_annealing.hpp"

#endif  // M1UNE_HEURISTIC_ALL_HPP

#line 1 "heuristic/all.hpp"



#line 1 "heuristic/beam_search.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <functional>
#include <type_traits>
#include <utility>
#include <vector>

#line 1 "heuristic/objective.hpp"



namespace m1une {
namespace heuristic {

enum class Objective {
    minimize,
    maximize,
};

template <class Score>
bool better_score(const Score& first, const Score& second,
                  Objective objective) {
    if (objective == Objective::maximize) return second < first;
    return first < second;
}

}  // namespace heuristic
}  // namespace m1une


#line 14 "heuristic/beam_search.hpp"

namespace m1une {
namespace heuristic {

template <class State, class Score>
struct BeamSearchResult {
    State state;
    Score score;
    int depth;
    std::size_t expanded_states;
    std::size_t generated_states;
};

namespace beam_search_detail {

template <class State, class Score>
struct Node {
    State state;
    Score score;
    std::size_t order;
};

template <class State, class Score>
struct BetterNode {
    Objective objective;

    bool operator()(const Node<State, Score>& first,
                    const Node<State, Score>& second) const {
        if (better_score(first.score, second.score, objective)) return true;
        if (better_score(second.score, first.score, objective)) return false;
        return first.order < second.order;
    }
};

}  // namespace beam_search_detail

// expand(state, next_depth) may return a range of children. For allocation-free
// generation, expand(state, next_depth, emit) may instead call emit(child).
// evaluate(state) returns its score. The best beam_width states are retained at
// every depth, and the best state in the last non-empty layer is returned.
template <class State, class Expand, class Evaluate>
auto beam_search(State initial_state, int depth_limit, int beam_width,
                 Expand expand, Evaluate evaluate,
                 Objective objective = Objective::maximize) {
    assert(0 <= depth_limit);
    assert(0 < beam_width);

    using Score = std::remove_cvref_t<
        std::invoke_result_t<Evaluate&, const State&>>;
    using Node = beam_search_detail::Node<State, Score>;
    using Better = beam_search_detail::BetterNode<State, Score>;

    Score initial_score = std::invoke(evaluate, initial_state);
    std::vector<Node> beam;
    beam.push_back(Node{std::move(initial_state),
                        std::move(initial_score), 0});

    std::size_t expanded_states = 0;
    std::size_t generated_states = 0;
    int reached_depth = 0;
    if (depth_limit < 0 || beam_width <= 0) depth_limit = 0;

    Better better{objective};
    for (int next_depth = 1; next_depth <= depth_limit; next_depth++) {
        std::vector<Node> candidates;
        candidates.reserve(static_cast<std::size_t>(beam_width));
        std::size_t order = 0;

        for (const Node& node : beam) {
            expanded_states++;
            auto emit = [&](auto&& candidate_state) {
                using Candidate = decltype(candidate_state);
                static_assert(std::is_constructible_v<State, Candidate>);
                State state(std::forward<Candidate>(candidate_state));
                Score candidate_score = std::invoke(evaluate, state);
                Node candidate{std::move(state), std::move(candidate_score),
                               order++};
                generated_states++;
                if (int(candidates.size()) < beam_width) {
                    candidates.push_back(std::move(candidate));
                    std::push_heap(candidates.begin(), candidates.end(), better);
                } else if (better(candidate, candidates.front())) {
                    std::pop_heap(candidates.begin(), candidates.end(), better);
                    candidates.back() = std::move(candidate);
                    std::push_heap(candidates.begin(), candidates.end(), better);
                }
            };
            if constexpr (std::invocable<Expand&, const State&, int>) {
                auto next_states =
                    std::invoke(expand, node.state, next_depth);
                for (auto& candidate_state : next_states) {
                    emit(std::move(candidate_state));
                }
            } else if constexpr (std::invocable<Expand&, const State&>) {
                auto next_states = std::invoke(expand, node.state);
                for (auto& candidate_state : next_states) {
                    emit(std::move(candidate_state));
                }
            } else {
                std::invoke(expand, node.state, next_depth, emit);
            }
        }

        if (candidates.empty()) break;
        beam = std::move(candidates);
        reached_depth = next_depth;
    }

    int best = 0;
    for (int index = 1; index < int(beam.size()); index++) {
        if (better(beam[index], beam[best])) best = index;
    }
    return BeamSearchResult<State, Score>{
        std::move(beam[best].state), std::move(beam[best].score),
        reached_depth, expanded_states, generated_states};
}

}  // namespace heuristic
}  // namespace m1une


#line 1 "heuristic/hill_climbing.hpp"



#line 5 "heuristic/hill_climbing.hpp"

#line 7 "heuristic/hill_climbing.hpp"

namespace m1une {
namespace heuristic {

using HillClimbingObjective = Objective;

class HillClimbing {
   private:
    Objective _objective;
    bool _accept_equal;

   public:
    explicit HillClimbing(Objective objective = Objective::maximize,
                          bool accept_equal = false)
        : _objective(objective), _accept_equal(accept_equal) {}

    bool accept_delta(long double candidate_minus_current) const {
        if (_objective == Objective::maximize) {
            return _accept_equal ? 0.0L <= candidate_minus_current
                                 : 0.0L < candidate_minus_current;
        }
        return _accept_equal ? candidate_minus_current <= 0.0L
                             : candidate_minus_current < 0.0L;
    }

    template <std::convertible_to<long double> CurrentScore,
              std::convertible_to<long double> CandidateScore>
    bool accept(CurrentScore current_score,
                CandidateScore candidate_score) const {
        long double delta = static_cast<long double>(candidate_score) -
                            static_cast<long double>(current_score);
        return accept_delta(delta);
    }
};

}  // namespace heuristic
}  // namespace m1une


#line 1 "heuristic/simulated_annealing.hpp"



#line 6 "heuristic/simulated_annealing.hpp"
#include <cmath>
#line 8 "heuristic/simulated_annealing.hpp"

#line 10 "heuristic/simulated_annealing.hpp"

namespace m1une {
namespace heuristic {

using AnnealingObjective = Objective;

enum class AnnealingCooling {
    linear,
    exponential,
};

class SimulatedAnnealing {
   private:
    double _start_temperature;
    double _end_temperature;
    AnnealingObjective _objective;
    AnnealingCooling _cooling;

    long double directed_delta(long double candidate_minus_current) const {
        if (_objective == AnnealingObjective::maximize) {
            return candidate_minus_current;
        }
        return -candidate_minus_current;
    }

   public:
    SimulatedAnnealing(
        double start_temperature, double end_temperature,
        AnnealingObjective objective = AnnealingObjective::maximize,
        AnnealingCooling cooling = AnnealingCooling::exponential)
        : _start_temperature(start_temperature),
          _end_temperature(end_temperature),
          _objective(objective),
          _cooling(cooling) {
        assert(std::isfinite(start_temperature));
        assert(std::isfinite(end_temperature));
        assert(0.0 <= end_temperature);
        assert(end_temperature <= start_temperature);
        assert(cooling != AnnealingCooling::exponential ||
               0.0 < end_temperature);
    }

    double temperature(double progress) const {
        assert(std::isfinite(progress));
        assert(0.0 <= progress && progress <= 1.0);
        progress = std::clamp(progress, 0.0, 1.0);
        if (_cooling == AnnealingCooling::linear) {
            return _start_temperature +
                   (_end_temperature - _start_temperature) * progress;
        }
        return _start_temperature *
               std::pow(_end_temperature / _start_temperature, progress);
    }

    double acceptance_probability_delta(
        long double candidate_minus_current, double progress) const {
        long double improvement = directed_delta(candidate_minus_current);
        if (0.0L <= improvement) return 1.0;
        double current_temperature = temperature(progress);
        if (current_temperature == 0.0) return 0.0;
        return std::exp(static_cast<double>(
            improvement / static_cast<long double>(current_temperature)));
    }

    bool accept_delta(long double candidate_minus_current, double progress,
                      double random01) const {
        assert(std::isfinite(random01));
        assert(0.0 <= random01 && random01 < 1.0);
        return random01 <
               acceptance_probability_delta(candidate_minus_current, progress);
    }

    template <std::convertible_to<long double> CurrentScore,
              std::convertible_to<long double> CandidateScore>
    double acceptance_probability(CurrentScore current_score,
                                  CandidateScore candidate_score,
                                  double progress) const {
        long double delta = static_cast<long double>(candidate_score) -
                            static_cast<long double>(current_score);
        return acceptance_probability_delta(delta, progress);
    }

    template <std::convertible_to<long double> CurrentScore,
              std::convertible_to<long double> CandidateScore>
    bool accept(CurrentScore current_score, CandidateScore candidate_score,
                double progress, double random01) const {
        long double delta = static_cast<long double>(candidate_score) -
                            static_cast<long double>(current_score);
        return accept_delta(delta, progress, random01);
    }
};

}  // namespace heuristic
}  // namespace m1une


#line 8 "heuristic/all.hpp"

Back to top page