tsp

Documentation

Index

• Variables
• func Solve[P Problem[State, Solution], State comparable, Solution any](problem P, capacity int) (Solution, error)
• type Problem

Variables

var ErrBadCapacity = errors.New("capacity must be positive")

ErrBadCapacity is returned by Solve when the capacity is not positive.

var ErrNoSolution = errors.New("no solution found")

ErrNoSolution is returned by Solve when all states have been checked without finding a solution.

Functions

func Solve

func Solve[P Problem[State, Solution], State comparable, Solution any](problem P, capacity int) (Solution, error)

Solves the given problem, returning the best state found.

The capacity is the maximum number of states that can be stored in memory at any given time.

If capacity is greater than 0, then the solver will maintain a max heap and discard states when it reaches capacity.

Types

type Problem

type Problem[State comparable, Solution any] interface {
	// Require a problem to implement the problem.Problem interface.
	problem.Problem[State]

	// Appends the initial states to begin the search with.
	Initialize(out []State) ([]State, error)

	// Appends the next possible states to the given slice.
	//
	// Appending an already known state is allowed, if this happens its
	// relative order is assumed to have changed.
	//
	// A state should only be resubmitted if its cost has changed, otherwise
	// we'd potentially be stuck in a loop trying to explore the same state over and over.
	Next(seed State, out []State) ([]State, error)

	// Returns true if this node represents a complete solution.
	Solved(state State) bool

	// Converts the given solved state into a solution that can be returned by the Solve function.
	Finish(state State) (Solution, error)
}

Problem represents a search problem.