最低成本路径搜索装置及其使用的最低成本路径搜索方法

摘要

在步骤S1的成本估计步骤中,估计出从中间节点到所有出口节点的成本,并且在步骤S2的生成步骤中,通过将当前搜索路径延伸至一相邻路径而生成各个路径。在步骤S3的路径存储步骤中,对生成的路径进行检查,如果在存储单元中有空闲项,则保存该路径。在步骤S4的路径选择步骤中,存储单元中保存在所有中间节点和入口节点的项目中的一个尚未被选择的路径被选择作为当前搜索路径,该路径的路径成本与最低估计成本之和最小。在步骤S6的路径输出步骤中,将保存在出口节点中的路径作为搜索结果输出。