state_search_common.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
# ifndef STATE_SEARCH_COMMON_H
# define STATE_SEARCH_COMMON_H
 
#include <chrono>
#include <concepts>
#include <cstddef>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
 
#include <ah-concepts.H>
#include <ah-errors.H>
#include <htlist.H>
#include <search_move_ordering.H>
#include <tpl_array.H>
#include <tpl_hash.H>
 
namespace Aleph {
 
inline constexpr size_t Search_Unlimited = std::numeric_limits<size_t>::max();
 
enum class SearchStatus
{
  NotStarted,         
  Exhausted,          
  StoppedOnSolution,  
  LimitReached        
};
 
template <typename T>
concept SearchState = std::movable<T> and std::copy_constructible<T>;
 
template <typename T>
concept SearchMove = Aleph::ArrayStorable<T> and std::copyable<T>;
 
template <SearchMove Move>
using SearchPath = Array<Move>;
 
using SearchClock = std::chrono::steady_clock;  
 
[[nodiscard]] inline double search_elapsed_ms(const SearchClock::duration &duration) noexcept
{
  return std::chrono::duration<double, std::milli>(duration).count();
}
 
template <typename Key,
          typename Data,
          template <typename, typename, class> class HashMapTable = MapOLhash,
          class Cmp = Aleph::equal_to<Key>>
using SearchStorageMap = DynHashMap<Key, Data, HashMapTable, Cmp>;
 
template <typename Key,
          template <typename, class> class HashSetTable = OLhashTable,
          class Cmp = Aleph::equal_to<Key>>
using SearchStorageSet = DynHashSet<Key, HashSetTable, Cmp>;
 
template <typename Set, typename Key>
concept VisitedStateSet = requires(Set &set, const Key &key) {
  { set.contains(key) } -> std::convertible_to<bool>;
  set.insert(key);
};
 
template <typename Map, typename Key, typename Objective>
concept VisitedBoundMap = requires(Map &map, const Key &key, const Objective &obj) {
  map.insert(key, obj);
  map.remove(key);
  { map.search(key) == nullptr } -> std::convertible_to<bool>;
  map.search(key)->second = obj;
};
 
template <typename Domain>
concept IncrementalBoundProvider =
  requires(Domain &domain,
           const typename Domain::State &state,
           const typename Domain::Move  &move) {
    { domain.bound_after(state, move) }
      -> std::convertible_to<typename Domain::Objective>;
  };
 
template <typename Domain>
concept IncrementalEvaluator =
  requires(Domain &domain,
           const typename Domain::State &state,
           const typename Domain::Move  &move) {
    { domain.evaluate_after(state, move) }
      -> std::convertible_to<typename Domain::Score>;
  };
 
template <typename Engine>
concept SupportsBestFirst = Engine::supports_best_first;
 
struct SearchStats
{
  size_t visited_states = 0;        
  size_t expanded_states = 0;       
  size_t generated_successors = 0;  
  size_t solutions_found = 0;       
  size_t terminal_states = 0;       
  size_t pruned_by_depth = 0;       
  size_t pruned_by_domain = 0;      
  size_t pruned_by_visited = 0;     
  size_t limit_hits = 0;            
  size_t max_depth_reached = 0;     
  double elapsed_ms = 0.0;          
  MoveOrderingStats move_ordering;  
};
 
struct SearchLimits
{
  size_t max_depth = Search_Unlimited;       
  size_t max_expansions = Search_Unlimited;  
  size_t max_solutions = Search_Unlimited;   
};
 
template <SearchMove Move>
inline void reserve_search_path(SearchPath<Move> &path, const SearchLimits &limits)
{
  if (limits.max_depth != Search_Unlimited)
    path.reserve(limits.max_depth + 1);
}
 
struct ExplorationPolicy
{
  enum class Strategy
  {
    Depth_First,  
    Best_First    
  };
 
  Strategy strategy = Strategy::Depth_First;                  
  MoveOrderingMode move_ordering = MoveOrderingMode::Domain;  
  bool stop_at_first_solution = true;  
  bool use_killer_moves = false;       
  bool use_history_heuristic = false;  
};
 
template <SearchState State, SearchMove Move>
struct SearchSolution
{
  State state;            
  SearchPath<Move> path;  
  size_t depth = 0;       
};
 
template <typename Solution>
struct KeepFirstSolution
{
  bool operator()(const Solution &, const Solution &) const noexcept
  {
    return false;
  }
};
 
struct ContinueSearch
{
  template <typename Solution>
  bool operator()(const Solution &) const noexcept
  {
    return true;
  }
};
 
template <typename Visitor, typename Solution>
concept SearchSolutionVisitor = requires(Visitor &visitor, const Solution &solution) {
  { visitor(solution) } -> std::convertible_to<bool>;
};
 
template <typename Solution>
class SearchSolutionCollector
{
public:
  using Solution_Type = Solution;
  using Container_Type = DynList<Solution>;
 
  SearchSolutionCollector() = default;
 
  explicit SearchSolutionCollector(const size_t max_solutions) : limit_(max_solutions)
  {
    ah_invalid_argument_if(limit_ == 0)
      << "SearchSolutionCollector: max_solutions must be positive";
  }
 
  bool operator()(const Solution &solution)
  {
    solutions_.append(solution);
    ++count_;
    return count_ < limit_;
  }
 
  void clear() noexcept
  {
    solutions_.empty();
    count_ = 0;
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return count_;
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return count_ == 0;
  }
 
  [[nodiscard]] const Container_Type &solutions() const noexcept
  {
    return solutions_;
  }
 
  [[nodiscard]] Container_Type &solutions() noexcept
  {
    return solutions_;
  }
 
private:
  Container_Type solutions_;
  size_t count_ = 0;
  size_t limit_ = Search_Unlimited;
};
 
template <typename Solution, typename Compare = KeepFirstSolution<Solution>>
  requires BinaryPredicate<Compare, Solution>
class BestSolution
{
public:
  using Solution_Type = Solution;
  using Compare_Type = Compare;
 
  BestSolution() = default;
 
  explicit BestSolution(Compare compare) : compare_(std::move(compare))
  {
    // empty
  }
 
  [[nodiscard]] bool has_value() const noexcept
  {
    return current_.has_value();
  }
 
  void clear() noexcept
  {
    current_.reset();
  }
 
  [[nodiscard]] const Solution &get() const
  {
    ah_runtime_error_unless(current_.has_value())
      << "BestSolution::get: no incumbent solution available";
    return *current_;
  }
 
  [[nodiscard]] Solution &get()
  {
    ah_runtime_error_unless(current_.has_value())
      << "BestSolution::get: no incumbent solution available";
    return *current_;
  }
 
  [[nodiscard]] const Compare &compare() const noexcept
  {
    return compare_;
  }
 
  bool consider(const Solution &candidate)
  {
    if (not current_.has_value() or compare_(candidate, *current_))
      {
        current_ = candidate;
        return true;
      }
 
    return false;
  }
 
  bool consider(Solution &&candidate)
  {
    if (not current_.has_value() or compare_(candidate, *current_))
      {
        current_ = std::move(candidate);
        return true;
      }
 
    return false;
  }
 
private:
  Compare compare_ = {};
  std::optional<Solution> current_;
};
 
template <typename Solution, typename Compare = KeepFirstSolution<Solution>>
using Incumbent = BestSolution<Solution, Compare>;
 
template <typename Domain>
concept SuccessorGenerator = requires(Domain &d, const typename Domain::State &state) {
  typename Domain::State;
  typename Domain::Move;
  requires SearchState<typename Domain::State>;
  requires SearchMove<typename Domain::Move>;
  {
    d.for_each_successor(state,
                         [](const typename Domain::Move &) -> bool
    {
      return true;
    })
  } -> std::convertible_to<bool>;
};
 
template <typename Domain>
concept GoalPredicate = requires(Domain &d, const typename Domain::State &state) {
  { d.is_goal(state) } -> std::convertible_to<bool>;
};
 
template <typename Domain>
concept TerminalPredicate = requires(const Domain &d, const typename Domain::State &state) {
  { d.is_terminal(state) } -> std::convertible_to<bool>;
};
 
template <typename Domain>
concept DomainPruner = requires(Domain &d, const typename Domain::State &state, const size_t depth) {
  { d.should_prune(state, depth) } -> std::convertible_to<bool>;
};
 
template <typename Domain>
concept MoveKeyProvider = requires(Domain &d, const typename Domain::Move &move) {
  typename Domain::Move_Key;
  { d.move_key(move) } -> std::convertible_to<typename Domain::Move_Key>;
};
 
template <typename Provider>
concept SearchStateKeyProvider = requires(const Provider &provider, const typename Provider::State &state) {
  typename Provider::State_Key;
  { provider.state_key(state) } -> std::convertible_to<typename Provider::State_Key>;
};
 
template <typename Domain>
concept HeuristicEvaluator = requires(Domain &d, const typename Domain::State &state) {
  typename Domain::Distance;
  { d.heuristic(state) } -> std::convertible_to<typename Domain::Distance>;
};
 
template <typename Domain>
concept ActionCostProvider
  = requires(Domain &d, const typename Domain::State &state, const typename Domain::Move &move) {
      typename Domain::Distance;
      { d.cost(state, move) } -> std::convertible_to<typename Domain::Distance>;
    };
 
template <typename Domain>
concept BacktrackingDomain
  = SuccessorGenerator<Domain> and GoalPredicate<Domain>
and requires(Domain &d, typename Domain::State &state, const typename Domain::Move &move) {
      { d.apply(state, move) } -> std::same_as<void>;
      { d.undo(state, move) } -> std::same_as<void>;
    };
 
template <typename Solution, typename Compare = KeepFirstSolution<Solution>>
  requires BinaryPredicate<Compare, Solution>
struct SearchResult
{
  using Solution_Type = Solution;
  using Compare_Type = Compare;
  using Incumbent_Type = BestSolution<Solution, Compare>;
 
  SearchStatus status = SearchStatus::NotStarted;  
  ExplorationPolicy policy;                        
  SearchLimits limits;                             
  SearchStats stats;                               
  Incumbent_Type best_solution;                    
 
  SearchResult() = default;
 
  explicit SearchResult(Compare compare) : best_solution(std::move(compare))
  {
    // empty
  }
 
  [[nodiscard]] bool found_solution() const noexcept
  {
    return best_solution.has_value();
  }
 
  [[nodiscard]] bool exhausted() const noexcept
  {
    return status == SearchStatus::Exhausted;
  }
 
  [[nodiscard]] bool stopped_on_solution() const noexcept
  {
    return status == SearchStatus::StoppedOnSolution;
  }
 
  [[nodiscard]] bool limit_reached() const noexcept
  {
    return status == SearchStatus::LimitReached;
  }
};
 
namespace search_engine_detail {
 
template <typename Domain>
[[nodiscard]] bool is_terminal_state(const Domain &domain,
                                     const typename Domain::State &state)
{
  if constexpr (TerminalPredicate<Domain>)
    return domain.is_terminal(state);
  else
    return false;
}
 
template <typename Domain>
[[nodiscard]] bool should_prune_state(Domain &domain,
                                      const typename Domain::State &state,
                                      const size_t depth)
{
  if constexpr (DomainPruner<Domain>)
    return domain.should_prune(state, depth);
  else
    return false;
}
 
template <typename Result>
void register_visit(const size_t depth, Result &result)
{
  ++result.stats.visited_states;
  if (depth > result.stats.max_depth_reached)
    result.stats.max_depth_reached = depth;
}
 
template <typename Result>
[[nodiscard]] bool expansion_limit_reached(Result &result, const SearchLimits &limits)
{
  if (result.stats.expanded_states >= limits.max_expansions)
    {
      ++result.stats.limit_hits;
      result.status = SearchStatus::LimitReached;
      return true;
    }
 
  return false;
}
 
template <typename Result>
[[nodiscard]] bool stop_after_solution(Result &result,
                                       const ExplorationPolicy &policy,
                                       const SearchLimits &limits)
{
  if (limits.max_solutions != Search_Unlimited
      and result.stats.solutions_found >= limits.max_solutions)
    {
      ++result.stats.limit_hits;
      result.status = SearchStatus::LimitReached;
      return true;
    }
 
  if (policy.stop_at_first_solution)
    {
      result.status = SearchStatus::StoppedOnSolution;
      return true;
    }
 
  return false;
}
 
}  // end namespace search_engine_detail
 
}  // end namespace Aleph
 
# endif  // STATE_SEARCH_COMMON_H