HillClimbing.java

package com.github.lstephen.ai.search;

import com.github.lstephen.ai.search.action.ActionGenerator;

import java.util.Optional;

import com.google.common.base.Preconditions;
import com.google.common.collect.Ordering;

/**
 * <p>
 *   Hillclimbing search to optimize a solution for a given {@link Heuristic}.
 * </p>
 *
 * <p>
 *   The following are provided to enable the search:
 * </p>
 * <ul>
 *   <li>
 *     {@link Heuristic} -
 *     To determine which solutions are better than another.
 *   </li>
 *
 *   <li>
 *     {@link ActionGenerator} -
 *     Provides the possible {@link Action}s that transform the current solution into
 *     another solution.
 *   </li>
 *
 *   <li>
 *     {@link Validator} -
 *     Determines if a given solution is valid.
 *     This allows the {@link ActionGenerator} to provide {@link Action}s that may lead
 *     to invalid solutions.
 *     Sometimes this is useful for performance reasons.
 *   </li>
 * </ul>
 *
 * <p>
 *   The {@link Validator} is optional and if not provided it's assumed that all solutions
 *   are valid.
 * </p>
 *
 * @param <S> type of solution to optimize
 */
public final class HillClimbing<S> {

  private final Validator<S> validator;

  private final Heuristic<S> heuristic;

  private final ActionGenerator<S> actionGenerator;

  private HillClimbing(Builder<S> builder) {
    Preconditions.checkNotNull(builder.validator);
    Preconditions.checkNotNull(builder.heuristic);
    Preconditions.checkNotNull(builder.actionGenerator);

    this.validator = builder.validator;
    this.heuristic = builder.heuristic;
    this.actionGenerator = builder.actionGenerator;
  }

  /**
   * The {@link Heuristic} being used for the search.
   *
   * @return heuristic used for search.
   */
  public Heuristic<S> getHeuristic() {
    return heuristic;
  }

  /**
   * Search the solution space starting from the given starting point.
   *
   * @param initial the starting point
   * @return the optimized solution
   */
  public S search(S initial) {
    S current = initial;

    Optional<S> next = next(current);

    while (next.isPresent()) {
      current = next.get();

      next = next(current);
    }

    return current;
  }

  private Optional<S> next(S current) {
    return actionGenerator
      .apply(current)
      .map((a) -> a.apply(current))
      .filter(validator)
      .filter((n) -> heuristic.compare(current, n) < 0)
      .findFirst();
  }

  /**
   * Get a {@link Builder} that can be used to create a {@link HillClimbing} instance.
   *
   * @param <S> type of solution to optimize
   * @return a builder for constructing an instance
   */
  public static <S> Builder<S> builder() {
    return Builder.create();
  }

  private static <S> HillClimbing<S> build(Builder<S> builder) {
    return new HillClimbing<>(builder);
  }

  /**
   * <p>
   *   Builder for creating {@link HillClimbing} instances.
   * </p>
   *
   * <p>
   *   Example:
   * </p>
   *
   * <p><blockquote><pre>{@code
   *   HillClimbing<MyClass> search = Hillclimbing
   *     .builder()
   *     .validator((s) -> s.isValid())
   *     .heuristic((s) -> s.getScore())
   *     .actionGenerator((s) -> s.getTransformations())
   *     .build();
   * }</pre></blockquote></p>
   *
   * @param <S> solution type
   */
  public static final class Builder<S> {

    private Validator<S> validator = (s) -> true;

    private Heuristic<S> heuristic;

    private ActionGenerator<S> actionGenerator;

    private Builder() { }

    public Builder<S> validator(Validator<S> validator) {
      this.validator = validator;
      return this;
    }

    public Builder<S> heuristic(Heuristic<S> heurisitc) {
      this.heuristic = heurisitc;
      return this;
    }

    public Builder<S> heuristic(final Ordering<? super S> ordering) {
      return heuristic(ordering::compare);
    }

    public Builder<S> actionGenerator(ActionGenerator<S> actionGenerator) {
      this.actionGenerator = actionGenerator;
      return this;
    }

    /**
     * Build the {@link HillClimbing} instance.
     *
     * @return the constructed instance
     */
    public HillClimbing<S> build() {
      return HillClimbing.build(this);
    }

    private static <S> Builder<S> create() {
      return new Builder<S>();
    }
  }

}