| 摘要 |
PROBLEM TO BE SOLVED: To improve search speed by improving the accuracy of the upper limit and the lower limit, in an A* search technique. SOLUTION: A plurality of landmarks is selected in a weighted diagrammatic chart to be used as a basis and searched for routes; the shortest lengths of the paths between the landmarks, and the shortest lengths of paths to nearby landmarks from each vertex are computed and recorded in a storage device so that they can be referred to afterwards. On the basis of expression derived from an inequality expression for a rectangle comprising two vertices v and w and the two vertices of two landmarks proximate to the two vertices v and w, routines for computing upper and lower limits of the shortest length of the path, corresponding to the vertices v and w, are prepared. In response to the calling from an A* search program, the routines refers to the data previously recorded in the storage device, regarding the shortest lengths of paths between the landmarks, and the shortest lengths of paths to nearby landmarks from each vertex, to return the upper or the lower limit of the shortest length of the path that corresponds to the vertices v and w. COPYRIGHT: (C)2008,JPO&INPIT |
