Bounded sub-optimal problem solving
US7966336B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Nov 30, 2007 |
| Grant date | Jun 21, 2011 |
| Priority date | — |
| Expiry date | May 12, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9027
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A data structure is described that comprises a balanced binary tree and a binary heap, which may be utilized for combinatorial searching algorithms. For instance, solutions for performing a task, such as a print job or the like, are associated with nodes that are utilized to generate the data structure. Each node is associated with a quality indicator that describes a most optimal solution that may be reached through the node when traversing the binary tree. The binary heap is generated from a subset of the nodes in the tree, wherein each node in the subset has a quality indicator value that is within a predefined range of a best known solution quality. The binary heap is sorted according to a search effort indicator value for each node, where nodes that are more easily reached in the tree are placed higher in the heap to facilitate rapid identification.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.