SYSTEM AND METHOD FOR COMBINING BREADTH-FIRST AND DEPTH-FIRST SEARCH STRATEGIES WITH APPLICATION TO GRAPH-SEARCH PROBLEM WITH LARGE ENCODING SIZE

摘要

PPROBLEM TO BE SOLVED: To integrate breadth-first and depth-first search strategies in a single search algorithm. PSOLUTION: A graph search method of one embodiment includes: a step for 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; a step for performing depth-first scanning 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 a step for deriving an intermediate graph of the selected node by modifying the intermediate graph of the current node. PCOPYRIGHT: (C)2011,JPO&INPIT