Finding Combined L1 and Link Metric Shortest Paths in the Presence of Orthogonal Obstacles: A Heuristic Approach | Zendy

Joon S. Lim | Zendy; S. S. Iyengar | Zendy; Si-Qing Zheng | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Finding Combined L₁ and Link Metric Shortest Paths in the Presence of Orthogonal Obstacles: A Heuristic Approach

Author(s) -

Joon S. Lim,

S. S. Iyengar,

Si-Qing Zheng

Publication year - 1999

Publication title -

vlsi design

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.123

H-Index - 24

eISSN - 1065-514X

pISSN - 1026-7123

DOI - 10.1155/1999/37271

Subject(s) - shortest path problem , metric (unit) , k shortest path routing , mathematics , yen's algorithm , metric space , heuristic , line (geometry) , combinatorics , algorithm , path (computing) , mathematical optimization , dijkstra's algorithm , graph , computer science , discrete mathematics , geometry , operations management , economics , programming language

This paper presents new heuristic search algorithms for searching combined rectilinear(L1) and link metric shortest paths in the presence of orthogonal obstacles. The Guided Minimum Detour (GMD)algorithm for L1 metric combines the best features of mazerunningalgorithms and line-search algorithms. The Line-by-Line Guided MinimumDetour (LGMD) algorithm for L1 metric is a modification of the GMD algorithm thatimproves on efficiency using line-by-line extensions. Our GMD and LGMD algorithmsalways find a rectilinear shortest path using the guided A* search method withoutconstructing a connection graph that contains shortest paths. The GMD and the LGMDalgorithms can be implemented in O(m+eloge+NlogN)and O(eloge+NlogN) time,respectively, and O(e+N) space, where m is the total number of searched nodes, e is thenumber of boundary sides of obstacles, and N is the total number of searched linesegments. Based on the LGMD algorithm, we consider not only the problems of findinga link metric shortest path in terms of the number of bends, but also the combined L1metric and link metric shortest path in terms of the length and the number of bends

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research