MINIMUM-COST PATH SEARCH SYSTEM AND MINIMUM-COST PATH SEARCH METHOD FOR USE IN THE SAME

摘要

PROBLEM TO BE SOLVED: To provide a minimum-cost path search method that can determine an arbitrary number of minimum-cost paths to each output node in order of increasing cost within a limited storage capacity and search for a path quickly. SOLUTION: Cost prediction in Step S1 predicts costs from an intermediate node to all output nodes, and path generation in Step S2 generates a path into which a presently searched path is extended to an adjacent node. Path storage in Step S3 checks the generated path, and if a storage part is available, stores the path. Path selection in Step S4 selects the unselected path that provides a minimum sum of path cost and minimum prediction cost, as a presently searched path, from paths stored in the storage part for all intermediate and input nodes. Path output in Step S6 outputs paths stored in the output nodes as search results.