System and method for combining breadth-first and depth-first search strategies with applications to graph-search problems with large encoding sizes
A system and method to integrate breadth-first and depth-first strategies in a single search technique or routine is provided. It combines the complementary strengths of both strategies to achieve significantly improved speed over either strategy used alone. The new algorithm can be used to efficiently find solutions to the treewidth problem that has applications in areas such as diagnosis using probabilistic inferences.
1. A graph search method comprising:
generating an ordered decision tree structure to represent the set of search frontier nodes with internal nodes of the decision tree corresponding to decision nodes operative to perform tests on state variables, and the leaf nodes corresponding to nodes in a search frontier;
performing depth-first traversal in the ordered decision tree structure to order node expansions such that a node to be expanded next is a close neighbor of a current node; and,
deriving an intermediate graph of the selected node by modifying the intermediate graph of the current node.
2. The method as set forth in claim 1 wherein the generating and deriving comprise a breadth-first approach.
3. The method as set forth in claim 1 wherein the generating and deriving comprise a best-first approach.
4. The method as set forth in claim 1 further comprising deriving encoding or representation of a node that is needed to generate successors of the node.
5. The method as set forth in claim 1 wherein modifying the intermediate graph comprises performing actions and meta-actions.
6. The method as set forth in claim 5 wherein the actions include eliminating vertices.
7. The method as set forth in claim 5 wherein the meta-actions include un-eliminating vertices.
8. The method as set forth in claim 5 wherein the undo information for an edge of the meta search space is cached until the depth-first traversal in the ordered decision tree structure backtracks from the edge to the source decision node of that edge.
9. The method as set forth in claim 1 wherein each internal decision node stores a counter for a number of leaf nodes in the decision tree, and any internal node having a counter with a value of zero is deleted.
10. The method as set forth in claim 1 wherein the order in which the state variables are tested in the decision tree structure is arranged in decreasing order of the number of neighbors a vertex has in the graph.
11. The method as set forth in claim 1 wherein the internal nodes of the ordered decision tree structure are selectively generated and deleted by constructing a decision tree for a subset of the frontier nodes.
12. The method as set forth in claim 11 wherein an approach based on state-space abstraction is used to determine the frontier nodes that belong to a same subset for which the decision tree structure is constructed and an order in which nodes in different subsets are expanded.
13. A system comprising:
sensors operative to detect states or events or conditions within the system;
a controller operative to control the system or a process of the system based on output of the sensors; and,
a diagnosis module within the controller to diagnose the system or process of the system, the diagnosis module having a treewidth solver being operative to generate an elimination order of the diagnosis state variables that corresponds to the minimum width of an underlying Bayesian network, the treewidth solver using an ordered decision tree structure to represent the set of search frontier nodes with internal nodes of the decision tree corresponding to decision nodes operative to perform tests on state variables, and the leaf nodes corresponding to nodes in a search frontier, perform depth-first traversal in the ordered decision tree structure to order node expansions such that a node to be expanded next is a close neighbor of a current node and derive an intermediate graph of the selected node by modifying the intermediate graph of the current node.
14. The system as set forth in claim 13 wherein the diagnosis comprises diagnosis, prognosis and analysis of state of health of the system.
15. The system set forth in claim 13 wherein the system is an image rendering system.