Heuristic Suite

Overview

Heuristic Suite is an experimental implementation of a series of heuristic algorithms in generic programming. The project is aimed to provide an infrastructure that can be applied to any puzzle - as long as the puzzle can be resolved with the algorithm.

Implemented algorithms:

The implementation is fully object-oriented and takes advantages of built-in .NET Framework comparison mechanism such as IComparer(T) and IEqualityComparer(T) to create great compatibility with .NET Standard and entire .NET ecosystem. Source code can be easily brought to other platforms such as Unity and Xamarin.

Solving Puzzle with Algorithm

In order to apply the algorithm to puzzle, following implementations are needed:

  1. Step Definition The type that defines step of the puzzle will be required to implement IStep(TKey) interface. The Key property serves two purposes:
    • To test whether two steps are equivalent. For example: same position on the board.
    • To compare two steps to determine which has better score. For example: the distance between position A and goal, and the distance between position B and goal, the closer one is scored better.
  2. Step Comparison Steps are compared to each other based on Key property to determine which has better score. The comparison can be done in one of following ways:
  3. The Available Steps from Current Step Next step information can be provided by implementing INextStepFactory(TKey, TStep) interface, or providing NextStepFactory delegate.

After which, the algorithm can be run by invoking FindSolution method with from and goal steps as parameters. If the solution exists, each of steps can be obtained by calling Enumerate method. Steps can be Reversed before the enumeration starts.

Heuristic Comparer and Discrete Heuristic Comparer

The project provides HeuristicComparer and DiscreteHeuristicComparer for different step comparison scenarios.

Heuristic Function Preference

The HeuristicFunctionPreference enumeration enable users to change the balance of estimation f(n) = g(n) + h(n). When two steps are evaluated same score, the enumeration decides which function, g(n) or h(n), will be considered first. The changed balance can affect the behavior of heuristic algorithm.

Examples

More examples will be added in future.

Platform

The project currently targets .NET Core and .NET Framework 4.5 or above.