Wyniki wyszukiwania - BazTech

1

Modyfikacje algorytmów planowania trasy uwzględniające ograniczenia czasowe i odległościowe

Wolanin Mateusz, Korniszuk Klaudia, Smołka Jakub

Journal of Computer Sciences Institute

|

2019

|

Vol. 10

18--23

PL

Artykuł przedstawia modyfikacje algorytmów wyszukiwania ścieżki w grafie mające na celu wprowadzenie ograniczeń: czasowych lub odległościowych do znalezionej trasy. Zmodyfikowane zostały dwa algorytmy: A* oraz BFS. Zaproponowana została również modyfikacja algorytmu A*, która łączy atuty tych dwóch algorytmów – wygenerowanie najkrótszych tras o jak najmniejszej liczbie wierzchołków. Zmodyfikowane algorytmy umożliwią stworzenie aplikacji pozwalającej na łatwiejsze i bardziej oszczędne poruszanie się z wykorzystaniem usług typu rowerem miejski.

EN

This paper describes modifications of path-finding algorithms. The modifications add time and distance constraints to generated paths. A* and BFS algorithms are modified. Additionally, A* algorithm modification which combines the advantages (generating the shortest routes with the smallest number of vertices) of A* and BFS is presented.. This allows for creating a route planning app that enables users of bike sharing services to travel more easily and economically.

2

Wyznaczanie trasy w planerach podróży z zastosowaniem funkcji heurystycznych

Celiński I., Staniek M., Sierpiński G.

TTS Technika Transportu Szynowego

|

2015

|

R. 22, nr 12

246--251, CD

PL

W artykule zaproponowano uzupełnienie algorytmu A* o inne heurystyki aniżeli powszechne stosowane w tym celu odległości Manhattan czy Euklidesowe. W przedstawionej metodzie, jako źródło danych dla wartości funkcji heurystycznych zastosowano macierz wskaźników charakteryzujących sieć drogową. Taki wskaźnik nadawany jest każdemu rejonowi przestrzennemu (reżimowi) powstałemu na skutek jej celowej delimitacji. Ściślej, dla każdego rejonu można zdefiniować zbiór wskaźników: multimodalnych, bezpieczeństwa, ekologicznych i innych. Każdy ze wskaźników podkreśla inny sposób korzystania z sieci transportowej w danym rejonie przez jej użytkownika. Zbudowana w ten sposób heurystyka ma dwie podstawowe funkcjonalności. Dla rejonów przestrzennych o dużych wymiarach (powierzchni) przyspiesza czas wykonywania obliczeń algorytmu A*. Dla rejonów o małych wymiarach obszarowych profiluje trasę zgodnie z wolą użytkownika w sposób inny niż heurystyki oparte na prostych miarach przestrzennych.

EN

The article proposes an algorithm A* supplement to other heuristics than normally used for this purpose (Manhattan and Euclidean dist.). In the presented method, as the data source for the heuristics used ma-trix of indicators characterizing the road network. This indicator is assigned to each space regime due to its deliberate delimitation. Specifically, for each regime you can define a set of indicators: multimodal, safety, environmental friendly etc. Each of the indicators stresses otherwise use the transport network by the user. Constructed in this way heuristics has two basic func. For large areas of spatial regime accelerates compute time algorithm. For small areas of spatial profiles the route according to the user's expectations transport network in a manner other than heuristics based on measures of spatial.

3

Heurystyki generowania tras kompletacji

Kłodawski M.

Logistyka

|

2015

|

nr 2

359--369, CD1

PL

W artykule podjęto problematykę wyznaczania tras kompletacji oraz przedstawiono znane i analizowane w literaturze podejścia do tego zagadnienia. Szczególną uwagę poświęcono heurystycznym sposobom generowania ścieżek kompletacyjnych. W tym celu przedstawiono jedenaście różnych metod heurystycznych i metaheurystycznych (algorytmy mrówkowe) mogących służyć do sekwencjonowania miejsc pobrań. Dodatkowo zaproponowano wykorzystanie algorytmu A* do wyznaczania najkrót szych ścieżek pomiędzy tymi miejscami. Przedstawione metody zostały ze sobą porównane i ocenione na podstawie wyników uzyskanych z przeprowadzonych badań.

EN

The paper deals with a problem of routing order pickers and presents known and analyzed in literature approaches. Main attention was paid to heuristics of order pickers routing. Eleven own heuristics and metaheuristics (ant algorithms) used for sequencing pick locations was proposed and investigated. Provided heuristics use the A - star algorithm to determine the shortest paths between pick locations. Presented methods were compared and evaluated according to results of research.

4

Real-time pathfinding algorithms in practical application

Pochmara J, Grygiel W

Elektronika : konstrukcje, technologie, zastosowania

|

2013

|

Vol. 54, nr 12

9-13

EN

Due to the fact that the A* algorithm is very flexible, can be used in a variety of situations, it became the main algorithm used in our study. Its biggest drawback is the need for large amounts of memory to store all the surveyed points. This problem greatly increases with the increase in the study area. However, the A* algorithm allows the robots to make efficient decisions on how to move from the starting to the ending point. Because of this, the A* algorithm should be taken into account as an option for pathfinding for intelligent robots.

PL

Ze względu na to, że Algorytm A* jest bardzo elastyczny, można go stosować różnych sytuacjach, stał się on głównym algorytmem wykorzystywanym podczas naszych badań. Jego największą wadą jest potrzeba dużej ilości pamięci w celu zapamiętania wszystkich zbadanych punktów. Ten problem znacznie się nasila wraz ze wzrostem badanego obszaru. Jednak algorytm A* pozwala robotom na podejmowanie sprawnych decyzji co do sposobu poruszania się od punktu startowego do końcowego. Z tego powodu warto brać algorytm A* pod uwagę jako opcję dla poszukiwania dróg przez inteligentne roboty.

5

Using quad tree as data storage for a terrain representation and a core for a path finding algorithm

Waresiak B., Skrzyński P.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 3

681-691

EN

This paper presents the concept of using single quad tree data structure for data storage for terrain representation and simultaneously a core for a path-finding algorithm. The simulated world is an artificially created two-dimensional world that consists of an island surrounded by water, which is considered to be an impassable terrain. Furthermore, the path-find operation is a possible route for a ship that has to avoid the island. The application of the quad tree data structure for Level of Detail implementation in 3D rendering is also discussed. Implementation details are presented together with initial results. Further research paths are presented in the conclusion.

PL

W artykule zaprezentowana została koncepcja wykorzystania pojedynczego drzewa czwórkowego do reprezentacji terenu oraz poszukiwania optymalnej ścieżki. Zaprezentowane zostało drzewo stworzone dla przykładowego świata, który składa się z wyspy otoczonej wodą, przy czym poruszanie się jest możliwe tylko po wodzie. Ponadto przedyskutowano możliwości zastosowania tego typu struktury do implementacji Level of Detail podczas renderowania kształtów 3D. Poza prezentacją wykorzystywanych w implementacji struktur oraz algorytmów przedstawione są wstępne wyniki oraz zarysowano dalsze kierunki badań.

6

Efektywne wyszukiwanie najkrótszej drogi pomiędzy dwoma węzłami w przestrzeni 3d przy wykorzystaniu algorytmu a* (a-star)

Jóźwiak I.

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2007

|

z. 40

109-114

PL

Wyszukiwanie najkrótszej drogi na scenie wirtualnej jest ważnym zagadnieniem w grafice komputerowej czasu rzeczywistego. Niniejszy artykułprezentuje wykorzystanie algorytmu A* oraz drzewiastej struktury podziału przestrzeni 3D w celu wyszukania najkrótszej drogi pomiędzy dwoma węzłami z uwzględnieniem przeszkód.

EN

One of the most significant issue in real-time computer graphics is finding a path in virtual world. This article presents A-star algorithm and octree data structure used to take advantage of fast and efficient path finding between two nodes in virtual world.