×

Heuristic directional search optimal path algorithm based on the variable raster model. (Chinese. English summary) Zbl 1363.90267

Summary: For graph theory method cannot be directly used to approach the path analysis problems in continuous space, a variable resolution grid model based on quad-tree thought is figured out. This model not only takes into account the topographic expression accuracy and data redundancy, but also avoids the impact of the “edge effect”. On the basis of the model, a heuristic directional search algorithm is designed, in which a directional search method is introduced. The algorithm firstly selects nodes according to the direction when searching for adjacent node, thereby reducing the search space and improving the efficiency of the algorithm. Experimental results show that the model and the algorithm proposed cannot only obtain the optimal path in continuous space, but also have high computational efficiency.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite