PL
 |
EN
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 16

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  algorytm Dijkstry
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Problem wyznaczania połączeń autobusowych.
100%
Szołtysek M.
Studia Informatica
|
2000
|
tom Vol. 21, nr 3
187-200
PL
Problem wyznaczania połączeń autobusowych jest przykładem złożonej optymalizacji kombinatorycznej. W celu zastosowania badanych algorytmów dla rzeczywistej sieci komunikacyjnej wraz z jej ograniczeniami stworzono komputerowy model realnej sieci komunkacyjnej. W dalszych pracach nad problemem połączeń autobusowych planuje się zbadanie algorytmów heurystycznych, takich jak przeszukiwanie tabu. Wymaga to istnienia dowolnego rozwiązania startowego oraz, w celu bezwzględnej oceny algorytmu, znajomości rozwiązania dokładnego, o ile rozmiar danych wejściowych pozwala na jego wyznaczenie. Z tych powodów prace nad problemem wyznaczania połączeń autobusowych rozpoczęto od stworzenia algorytmów realizujących te potrzeby. W niniejszej pracy przedstawiono wyniki działania algorytmu wyszukiwania wyczerpującego, algorytmu przeszukiwania wszerz oraz modyfikację algorytmu Dijkstry do wyznaczania połączeń autobusowych dla danych wejściowych opisujących rzeczywistą sieć komunikacyjną miast Gliwice i Zabrze.
EN
The bus routing problem is a difficult combinatorial optimization problem. we have created a real bus network computer model in order to apply our algorithms to a real bus network. In the future research we plan to investigate the heuristic algorithms, including Tabu Search. The heuristic such as Tabu Search require a start solution, and in order to assess the heuristic algorithm efficiency we need to know the optimal solution, provided that the size of input data allows to determine it. For these reasons we have started our work with creating the algorithms for mentioned needs. In this paper the results of the exhaustive search algorithm, Breadth First Search (BFS) and modification of Dijkstra's shortest path algorithm for the bus routing problem, tested on the input data describing a real communication network of Gliwice and Zabrze cities, are presented.
2
Content available remote Canonical greedy algorithms and dynamic programming
88%
Lew A.
Control and Cybernetics
|
2006
|
tom Vol. 35, no 3
621-643
EN
There has been little work on how to construct greedy algorithms to solve new optimization problems efficiently. Instead, greedy algorithms have generally been designed on an ad hoc basis. On the other hand, dynamic programming has a long history of being a useful tool for solving optimization problems, but is often inefficient. We show how dynamic programming can be used to derive efficient greedy algorithms that are optimal for a wide variety of problems. This approach also provides a way to obtain less efficient but optimal solutions to problems where derived greedy algorithms are nonoptimal.
3
Content available remote Propozycja metody trasowania przewodów wodociągowych
75%
Suchorab P. , Kowalski D. , Kowalska B.
Instal
|
2016
|
tom nr 5
44--47
PL
Wybór trasy wodociągu jest jednym z podstawowych zadań stawianych przed projektantem. Od decyzji podjętych na tym etapie zależy wiele późniejszych aspektów, takich jak: przebieg procesu budowy, koszty inwestycyjne i eksploatacyjne oraz częściowo proces eksploatacji sieci. Wśród wielu etapów projektowania systemu wodociągowego, wyznaczanie trasy przewodów wodociągowych (proces trasowania) jest stosunkowo najsłabiej wspieranym przez komputerowe narzędzia wspomagania projektowania. Wynika to z faktu, iż każda sieć wodociągowa ma indywidualny charakter, w tym strukturę geometryczną, która determinowana jest przez układ terytorialno-wysokościowy danej jednostki osadniczej oraz punkty lokalizacji źródeł wody, pompowni i największego zapotrzebowania na wodę. Uniwersalny opis takich struktur może być realizowany przez elementy geometrii fraktalnej. Daje to szerokie możliwości proponowania nowych podejść w kontekście ich klasyfikowania, opisywania, odwzorowywania i projektowania. W niniejszym artykule przedstawiono propozycję metody trasowania przewodów wodociągowych, opartą o elementy teorii fraktalnej, teorii grafów, algorytm znajdowania najkrótszej ścieżki i hierarchizację punktów poboru wody. Metodę przetestowano w warunkach modelowej jednostki osadniczej.
EN
The water pipes path design is one of the basic steps during the designing process. Basing on decisions made during this stage depends many further aspects, such as: building process, investment and exploitation costs and partially the exploitation process. Among many steps of water supply system design, the water pipes path design is relatively weakly supported by computer aided designing tools. That is because every water supply network is unique, considering both shape and territory of a municipality, but also a number and localisation of water sources, pumping stations and highest water demand points. The universal description of all water supply structures is available by using elements of a fractal geometry. That gives plural possibilities in new methods of a classification, description and design of water supply networks. This paper presents the method of a water pipes path design method with the use of elements of a fractal geometry, graph theory, shortest path algorithm and classification of water demand points. The method was further applied in model municipality conditions.
4
Wpływ informacji o gęstości ruchu na czas przejazdu
75%
Chalfen M. , Kamińska J.
Logistyka
|
2015
|
tom nr 4
2739--2746, CD2
PL
W pracy przedstawiono makroskopowy model ruchu samochodowego w mieście. Sieć ulic w mieście potraktowano jako graf skierowany. Trasę przejazdu pojazdu od punktu startowego do docelowego wyznaczono korzystając z algorytmu Dijkstry wyszukiwania najkrótszej w czasie trasy. Prędkość poruszania uzależniono od aktualnej na danym odcinku ulicy gęstości ruchu. Obliczenia symulacyjne wykonano w dwóch wariantach. W pierwszym trasę przejazdu wyznaczono w chwili startu pojazdu i nie modyfikowano jej trakcie dalszej podróży. W drugim trasę modyfikowano na każdym skrzyżowaniu w zależności od dynamicznie zmieniającej się gęstości ruchu w mieście. Na przykładzie hipotetycznego miasta wykazano, że wdrożenie systemu ciągłej informacji o ruchu w mieście może wyraźnie skrócić średni czas podróży. Wskazano także na potrzebę dostosowania parametrów sieci ulic w sytuacji korzystania przez kierowców z systemu wyznaczającego optymalne w czasie trasy przejazdu.
EN
The paper presents a macroscopic model of city traffic flow. Network of streets in the city was treated as a directed graph. The route of the vehicle from the starting point to the target was determined by using the Dijkstra’s algorithm searching shortest-time route. The speed of movement was modeled as a traffic density function. Simulations carried out in two variants. In the first route was not modified during the travel. The second route was modified at every intersection, depending on dynamically changing traffic density in the city. In the paper on hypothetical city have shown that the implementation of a system of continuous information about traffic in the city can significantly reduce the average travel time.
5
Content available Analiza i implementacja algorytmów odnajdywania ścieżki do zastosowania w grach przeglądarkowych
63%
Laszkiewicz B. , Sobczak T.
Biuletyn Naukowy Wrocławskiej Wyższej Szkoły Informatyki Stosowanej. Informatyka
|
2022
|
tom vol. 9, nr 1
16--24
PL
Celem tego artykułu jest przedstawienie, porównanie oraz implementacja algorytmów odnajdywania ścieżki do zastosowania w grach przeglądarkowych z wykorzystaniem ogólnodostępnych, darmowych technologii internetowych. Pokazano również możliwość wykorzystania najlepszego algorytmu w grze przeglądarkowej
EN
The goal of this article is to present, compare and implement path finding algorithms for use in browser games, using public, free internet technologies. The possibility of using the best algorithm in a browser game is also shown.
6
Content available Multithreaded enhancements of the Dijkstra algorithm for route optimization in urban networks
63%
Bazan M. , Ciskowski P. , Dudek R. , Halawa K. , Janiczek T. , Kozaczewski P. , Rusiecki A.
Archives of Transport System Telematics
|
2016
|
tom Vol. 9, iss. 2
3--7
EN
In this paper, we present a case study, showing step by step, how to speed up Dijkstra’s method by parallelizing its computation and using different data structures. We compare basic algorithm with its bidirectional version and investigate two-and-multi-thread implementations based on Fibonacci heaps and regular priority queues. Experimental results obtained for artificially generated graphs as well as real-world road network data are presented and described.
7
Content available Zastosowanie informatyki w logistyce transportu
63%
Brzoza A. , Muszyński G.
Autobusy : technika, eksploatacja, systemy transportowe
|
2017
|
tom R. 18, nr 6
1335--1337, CD
PL
W artykule została omówiona logistyka transportu mająca coraz większe znaczenie w planowaniu transportu towarów. Ponieważ koszty transportu zależą od jego przewidywanego czasu dostarczenia oraz od środka transportu, stąd planowanie trasy przejazdu jest istotnym czynnikiem w logistyce transportu, która we współczesnym świecie nie może w pełni funkcjonować bez rozwiązań informatycznych. W artykule poddano analizie transport kolejowy w Szwajcarii, będący jednym z najbardziej rozwiniętych tego typu systemów transportowych w Europie. Obliczenia bazują na przykładowych danych dotyczących tras kolejowych narodowego przewoźnika w tym kraju z wyborem czasu przejazdu jako głównego kryterium wyznaczania optymalnej trasy przejazdu dla wybranych połączeń między miastami. Dla potrzeb analizy został stworzony program implementujący algorytm Dijkstry, który posłużył do wyszukiwania optymalnego połączenia między wskazanymi miastami według danego kryterium.
EN
This article discusses some computer-based logistics solutions aimed to improve the planning process in freight transport. Since transport costs are dependent on the lead time and the transport mode, route planning is a crucial factor in transport logistics, which, these days, relies heavilyon computer technology. The study is focused on the rail transport system in Switzerland, known to be the most developed in Europe. The data used in the computations refers to rail routes of the national carrier in that country. The transportation time was the main criterion to select an optimal route between origin and destination. The analysis involved developing a program that implements Dijkstra’s algorithm to find an optimal connection between places according to the selected criterion.
8
Content available Design and development of a road traffic redirection system
63%
Bazan M. , Janiczek T. , Halawa K. , Dudek R. , Rudawski Ł.
Archives of Transport System Telematics
|
2017
|
tom Vol. 10, iss. 1
3--8
EN
Nowadays, the crucial issue of guidance systems based on a GPS signal is that they are not able to redirect road users, taking into account the current state of traffic (and the predicted state within the time of the travel) in the city. In this paper we present a three layer architecture of a computer system capable of redirecting users of an urban road system via routes with a lighter traffic load in order to reach their declared destination in the city. A basic layer is a multiprocessor calculation server running Dijkstra path search tasks, the middle layer - the one which is visible to the road user - is a replicable proxy server that collects route requests from road users. The third layer is a mobile application. The prototype of such a system was developed by the ArsNumerica Group. The crucial feature of the system is feedback from road users that allows us to adjust the whole Intelligent Transportation System in the city to changes in traffic flow at various road links introduced by the redirection process applied to many users. The performance test strategy to prove the efficiency of the architecture was carried out for the city of Wrocław.
9
Content available remote Zastosowanie grafu widoczności w planowaniu trasy przejścia statku
63%
Lazarowska A.
Zeszyty Naukowe Akademii Morskiej w Gdyni
|
2017
|
tom nr 98
116--121
PL
W artykule przedstawiono propozycję rozwiązania problemu wyznaczania trasy przejścia statku przy zastosowaniu jednej z metod teorii grafów. Celem pracy była ocena możliwości zastosowania wybranej metody teorii grafów w planowaniu globalnej trasy przejścia statku, uwzględniającej statyczne ograniczenia nawigacyjne (lądy, mielizny). Środowisko nawigacyjne zostało zamodelowane w postaci grafu widoczności przy zastosowaniu algorytmu obrotowego zamiatania płaszczyzny. Najkrótsza trasa przejścia statku wyznaczono następnie za pomocą algorytmu Dijkstry.
EN
The article presents a proposal for solving the problem of determining a ship’s safe path using one of the graph theory methods. The aim of the study was to evaluate the possibility of the selected graph theory method application in planning a ship’s global route, taking into account the static navigational restrictions (lands, shallows). The navigational environment was modelled as a visibility graph using a rotational plane sweep algorithm. The shortest ship’s path is then determined using a Dijkstra's algorithm.
10
Content available Algorytm Dijkstry w modelowaniu samochodowego ruchu miejskiego
63%
Chalfen M. , Kamińska J.
Autobusy : technika, eksploatacja, systemy transportowe
|
2013
|
tom R. 14, nr 3
1885-1893
PL
W pracy przedstawiono matematyczny model ruchu samochodowego mieście w okresie porannego szczytu. Obliczenia wykonano na przykładzie hipotetycznego miasta średniej wielkości przy założeniu niejednorodności gęstości sieci ulic i zróżnicowanych rzeczywistych prędkościach poruszania się samochodów w wybranych rejonach miasta. Do określenia optymalnej trasy przejazdu pojedynczego pojazdu wykorzystano algorytm Dijkstry wyszukiwania najtańszej ścieżki w grafie. Metodami statystycznymi wykazano przydatność tego algorytmu do modelowania ruchu samochodowego.
EN
The paper presents a mathematical model of the traffic flow during the morning rush. The calculations were performed on the example of a hypothetical medium-sized cities, assuming a heterogeneity density of road network and diverse actual speed of movement of cars in some areas of the city. To determine the optimal route of the vehicle were used a Dijkstra algorithm to search the cheapest path in the graph. Statistical methods have shown the usefulness of this algorithm to modeling the urban traffic.
11
Content available Wyznaczanie trasy statku żaglowego z ograniczeniem zmian kursu
63%
Życzkowski M.
Prace Wydziału Nawigacyjnego Akademii Morskiej w Gdyni
|
2017
|
tom Z. 32
121--132
PL
W artykule przedstawiono propozycję rozwiązania problemu planowania trasy statku żaglowego z zadanej pozycji startowej do pozycji docelowej w przestrzeni dyskretnej. Artykuł jest kontynuacją rozważań autora nad planowaniem trasy statku żaglowego. Proponowana wersja metody jest odpowiednia dla użytkowników statków żaglowych o przeznaczeniu rekreacyjnym lub dla początkujących żeglarzy. Jako kryterium optymalizacji przyjęto czas żeglugi, ale wprowadzono ograniczenie możliwości wykonywania znacznych zmian kursu.
EN
The article presents a solution to the problem of planning a sailing vessel route from a given starting position to a target position in a discrete domain. This article is a continuation of the author's research on the sailing ship's route planning. The proposed version of the method is suitable for recreational sailing craft users or beginner sailors. The time of navigation was chosen as the optimization criterion, but the possibility of making significant alteration of the course was limited.
12
Optymalizacja transportu przesyłek przy wykorzystaniu stałych linii komunikacyjnych i wyróżnionych węzłów sortujących
51%
Kuczora M.
Studia Informatica
|
2002
|
tom Vol. 23, nr 4
105-124
PL
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.
EN
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.
13
Algorytm dewiacyjny dla problemu wyznaczania K najkrótszych ścieżek
51%
Widuch J. , Szołtysek M.
Studia Informatica
|
2011
|
tom Vol. 32, nr 1A
55-77
PL
Jednym z badanych problemów teorii grafów jest problem wyznaczenia najkrótszej ścieżki. Rozszerzeniem tego problemu jest problem wyznaczenia K (K > 1) najkrótszych ścieżek. Badane są dwa warianty tego problemu. W pierwszym dopuszcza się wyznaczenie ścieżek zawierających cykle, a w drugim są wyznaczane wyłącznie ścieżki acykliczne. W pracy został przedstawiony algorytm dewiacyjny, umożliwiający wyznaczenie K najkrótszych ścieżek, które mogą zawierać cykle.
EN
One of the studied problems of the graph theory is the shortest path problem. An extension of this problem is the problem of finding K (K > 1) shortest paths. Two variants of this problem are studied. In the first case path containing cycles are allowed, and in the second are determined only loopless paths. In the paper a deviation algorithm for solving K shortest paths, which may contain cycles is shown.
14
Mobile application prototype for public transportation trip planning
51%
Bembenik R. , Byczuk M.
Metody Informatyki Stosowanej
|
2011
|
tom nr 3
19-30
EN
Paper presents a prototype of a system that allows passengers of public transportation to plan their trips. It is assumed that the user enters information concerning the planned trip (start address, end address and start time) and the system provides (i) description of the most convenient route i.e. one with the minimum number of transfers, the shortest walking distance and possibly the shortest trip time and (ii) a map presenting the route. The system is delivered to the end-user as a mobile application. Mobile devices (cellular phones, smartphones) are oftentimes equipped with a GPS (Global Positioning System) unit. The client's application makes use of the GPS unit so that the users who do not know their exact location can conveniently plan their trips. The system is built up of four programs implemented in Java. Oracle Spatial is used to store, access and analyze spatial data in the system.
15
Content available remote Szacowanie czasu propagacji fal dźwiękowych w ośrodkach materialnych za pomocą metody Dijkstry
51%
Perkowski Z. , Gozarska K.
Roczniki Inżynierii Budowlanej
|
2012
|
tom z. 12
43--48
EN
A proposition of method enabling an estimation of wave propagation time from point to point (but without refection) in material media is presented in the work. The calculating procedure is based on Fermat’s principle and Dijkstra’s algorithm and it is relatively quick and easy for its implementation by means of individual computer code. It can be used effectively in optimization methods oriented on reconstruction of damage state in engineering structures basing on time-of-flight measurements for mechanical waves.
16
Content available The use of the roadload application in geographical studies of flows generated by individual modes of transport
51%
Borowska-Stefańska M. , Kowalski M. , Wiśniewski S. , Domagalski A.
Transport Problems
|
2020
|
tom T. 15, z. 4, cz. 2
227--240
EN
The purpose of this article is to present the authors' own software for predicting changes in the density and directions of traffic flows and to compare overall results of research on transport accessibility with the results returned in the study of transport accessibility conducted with the software (isochronic accessibility). Developed for research purposes, the authors' application is based on Dijkstra's algorithm, which is classified as one of the greedy ones and does not always return optimum results, even though it is considered to be generally accurate. In the course of the research, it was stated that the implementation of Dijkstra's algorithm in the RoadLoad tool is suitable for studying and prognosing phenomena, under the assumption that there are detailed data on the point of departure and destination for each trip. The tool enables us to research a spatial (cumulated values of network load) as well as time-spatial (network load at virtually any time) dimension of the phenomenon. It cannot be applied, however, without the knowledge of the transport behavior characteristics of the users of the road system.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.