Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Floyd-Warshall algorithm

Sortuj według:

Ogranicz wyniki do:

Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles

Nagaraja S.

Journal of Telecommunications and Information Technology

2018

nr 3

82--91

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 modiﬁcation to the Floyd-Warshall algorithm, which is constitutes the main contribution of the author presented herein.

Optymalizacja transportu przesyłek przy wykorzystaniu stałych linii komunikacyjnych i wyróżnionych węzłów sortujących

Kuczora M.

Studia Informatica

2002

Vol. 23, nr 4

105-124

Artykuł opisuje problem transportowy zakładający istnienie sieci węzłów o zróżnicowanej funkcji, pomiędzy którymi są transportowane przesyłki. Rozważane jest znalezienie optymalnej drogi paczki oraz określenie reguł konstrukcji rozkładu jazdy. Próba rozwiązania zakłada adaptację klasycznych algorytmów transportowych, tzn. algorytmu wyszukiwania najkrótszych ścieżek Dijkstry oraz Floyda-Warshalla. Wyniki są selekcjonowane w świetle przyjętych ograniczeń. Jako alternatywne rozwiązanie jest przedstawiony algorytmu przeszukiwania Tabu. Uzyskane rezultaty są porównane do wyników empirycznych, a wykorzystywane metody do prac podejmowanych na świecie.

Article describes transport-class problem connected with network transporting packages that contains nodes which have different function. The goal is to find an optimal parcel itinerary and specify timetable creation rules. The attempt of solution adapts classical transport algorithms such as Dijkstra and Floyd-Warshall ones. The content modification of those algorithms and the selection of results according to given assumptions are executed. Tabu Search algorithm is considered as an alternative solution. The results are compared to empiric ones and applied methods to works which are undertaken in the world.