Wyszukiwanie zaawansowane ?

Obiekt

Pobierz

Tytuł: Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles, Journal of Telecommunications and Information Technology, 2018, nr 3

Autor:

Nagaraja, Shylashree

Data wydania:

2018, nr 3

Typ zasobu:

artykuł

Opis:

The paper presents a new algorithm to determine the shortest, non-crossing, rectilinear paths in a twodimensional grid graph. The shortest paths are determined in a manner ensuring that they do not cross each other and bypass any obstacles present. Such shortest paths are applied in robotic chip design, suburban railway track layouts, routing traffic in wireless sensor networks, printed circuit board design routing, etc. When more than one equal length noncrossing path is present between the source and the destination, the proposed algorithm selects the path which has the least number of corners (bends) along the path. This feature makes the path more suitable for moving objects, such as unmanned vehicles. In the author’s scheme presented herein, the grid points are the vertices of the graph and the lines joining the grid points are the edges of the graph. The obstacles are represented by their boundary grid points. Once the graph is ready, an adjacency matrix is generated and the Floyd-Warshall all-pairs shortest path algorithm is used iteratively to identify the non-crossing shortest paths. To get the minimum number of bends in a path, we make a modification to the Floyd-Warshall algorithm, which is constitutes the main contribution of the author presented herein.

Wydawca:

Instytut Łączności - Państwowy Instytut Badawczy

Format:

application/pdf

Identyfikator zasobu:

ISSN 1509-4553, on-line: ISSN 1899-8852 ; oai:bc.itl.waw.pl:2045

Źródło:

Journal of Telecommunications and Information Technology

Język:

ang

Prawa:

Biblioteka Naukowa Instytutu Łączności

Temat i słowa kluczowe:

Floyd-Warshall algorithm rectilinear non-crossing shortest paths rectilinear obstacles

Kolekcje, do których przypisany jest obiekt:

Data ostatniej modyfikacji:

15 kwi 2019

Data dodania obiektu:

29 paź 2018

Liczba wyświetleń treści obiektu:

53

Wszystkie dostępne wersje tego obiektu:

https://bc.itl.waw.pl/publication/2329

Wyświetl opis w formacie RDF:

RDF

Wyświetl opis w formacie OAI-PMH:

OAI-PMH

Nazwa wydania Data
Nagaraja Shylashree, Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles, Journal of Telecommunications and Information Technology, 2018, nr 3 15 kwi 2019
×

Cytowanie

Styl cytowania:

Dane kontaktowe

Adres

Instytut Łączności – Państwowy Instytut Badawczy ul. Szachowa 1 04-894 Warszawa

Telefon

(+48) 5128 696

E-Mail

biblioteka@il-pib.pl

Odwiedź nas!

Ta strona wykorzystuje pliki 'cookies'. Więcej informacji