Patent ID: 7389279

Claim:
A method for obtaining solutions to a combinatorial problem, said method comprising: maintaining a plurality of nodes, each of said nodes comprising a partial solution to said combinatorial problem; performing a discrete state-based search of said plurality of nodes utilizing a user-specified utility function based both on solution quality and distance in search steps to a goal, said method stored and executed as a computer application, and said goal being a node comprising a desired solution; initializing operation by creating an open queue to hold nodes that have been generated but not expanded; applying the utility function to identify one of said nodes having a highest utility value, wherein said utility function considers both solution quality and solution time; providing a utility default value, wherein said utility default value represents the utility of immediately returning an empty solution; providing a solution quality importance factor; providing a computation time importance factor; determining solution cost for a particular node by multiplying an estimated cost of a solution with said solution quality factor; determining solution time for a particular node by multiplying an estimated time at which a solution could be returned to the user with said computation time importance factor; summing said solution cost for a particular node and said solution time for a particular node to determine a sum; subtracting said sum from said utility default value; and repeating determining said solution cost for another node, determining said solution time for another node, summing said solution cost and said solution time for said another node to determine another sum, and subtracting said another sum from said utility default value until a node with highest utility is identified; removing said node with highest utility value from said open queue; determining whether said node with highest utility value is a goal, wherein said goal is a desired problem solution; generating a plurality of child nodes for said node with highest utility value if said node is not a goal, wherein each of said child nodes represents a different way of continuing to fill in the partial solution of the parent node, wherein said parent node comprises the node with highest utility value; adding said parent node's child nodes to said open queue; repeating the sequence of applying said utility function, removing a highest utility valued node, determining whether said highest utility valued node is a goal, generating child nodes, and adding said child nodes to said open queue until a problem solution is identified; and returning at least one of said desired solution and path to said goal to the user.