A method for obtaining solutions to combinatorial problems by way of a
discrete state-based search approach utilizes a node evaluation function
based both on solution quality and distance in search steps to a goal.
The method considers the problem as finding the shortest path between an
initial state and a goal state in a large graph and performs solution
evaluation utilizing computation time balanced against solution quality.
Rather than solely using a lower bound on the solution cost achievable
below a search node, an estimate of the distance (in search steps) to the
nearest solution below a search node is also utilized. These are combined
using the user's stated utility function (represented as a function of
time and cost) to evaluate candidate search nodes.