Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "shortest path" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 29
Tytuł:
A simple linear algorithm for the connected domination problem in circular-arc graphs
Autorzy:
Hung, Ruo-Wei
Chang, Maw-Shang
Powiązania:
https://bibliotekanauki.pl/articles/744451.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph algorithms
circular-arc graphs
connected dominating set
shortest path
Opis:
A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 137-145
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A scaling out-of-kilter algorithm for minimum cost flow
Autorzy:
Ciupala, L.
Powiązania:
https://bibliotekanauki.pl/articles/970996.pdf
Data publikacji:
2005
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
network flow
minimum cost flow
shortest path
scaling technique
Opis:
The out-of-kilter algorithm is one of the basic algorithms that solve the minimum cost flow problem. Its drawback is that it can improve the objective function at each iteration by only a small value. Consequently, it runs in pseudo-polynomial time. In this paper, we describe a new out-of-kilter algorithm for minimum cost flow that runs in polynomial time. Our algorithm is a scaling algorithm and improves the objective function at each time by a "sufficiently large" value.
Źródło:
Control and Cybernetics; 2005, 34, 4; 1169-1174
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distributed asynchronous algorithms in the Internet - new routing and traffic control methods
Autorzy:
Karbowski, A.
Powiązania:
https://bibliotekanauki.pl/articles/309014.pdf
Data publikacji:
2005
Wydawca:
Instytut Łączności - Państwowy Instytut Badawczy
Tematy:
computer networks
optimization
shortest path
traffic control
decomposition
distributed computations
asynchronous algorithms
Opis:
The paper presents several new algorithms concerning the third (network) and the fourth (transport) layer of ISO/OSI network model. For the third layer two classes of the shortest paths algorithms - label correcting and auction algorithms - are proposed. For the fourth layer an application of price decomposition to network optimization and Internet congestion control is suggested.
Źródło:
Journal of Telecommunications and Information Technology; 2005, 3; 29-36
1509-4553
1899-8852
Pojawia się w:
Journal of Telecommunications and Information Technology
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Modeling shortest path games with Petri nets: A Lyapunov based theory
Autorzy:
Clempner, J.
Powiązania:
https://bibliotekanauki.pl/articles/908393.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Oficyna Wydawnicza
Tematy:
Nash equilibrium point
shortest path game
game theory
Lyapunov equilibrium point
Bellman’s equation
Lyapunov-like fuction
stability
teoria gier
funkcja Lapunowa
równanie Bellmana
stabilność
Opis:
In this paper we introduce a new modeling paradigm for shortest path games representation with Petri nets. Whereas previous works have restricted attention to tracking the net using Bellman’s equation as a utility function, this work uses a Lyapunov-like function. In this sense, we change the traditional cost function by a trajectory-tracking function which is also an optimal cost-to-target function. This makes a significant difference in the conceptualization of the problem domain, allowing the replacement of the Nash equilibrium point by the Lyapunov equilibrium point in game theory. We show that the Lyapunov equilibrium point coincides with the Nash equilibrium point. As a consequence, all properties of equilibrium and stability are preserved in game theory. This is the most important contribution of this work. The potential of this approach remains in its formal proof simplicity for the existence of an equilibrium point.
Źródło:
International Journal of Applied Mathematics and Computer Science; 2006, 16, 3; 387-397
1641-876X
2083-8492
Pojawia się w:
International Journal of Applied Mathematics and Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms
Autorzy:
Tarapata, Z.
Powiązania:
https://bibliotekanauki.pl/articles/929638.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Oficyna Wydawnicza
Tematy:
problem najkrótszej ścieżki
złożoność algorytmu
algorytm aproksymacji
multiobjective shortest path
stochastic shortest path
algorithm complexity
routing problem
terrain-based modeling
approximation algorithm
Opis:
The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multiobjective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi-weighted graph problems (using modified Dijkstra’s algorithm) is given. Experimental results of using the presented methods for multicriteria path selection in a terrain-based grid network are given.
Źródło:
International Journal of Applied Mathematics and Computer Science; 2007, 17, 2; 269-287
1641-876X
2083-8492
Pojawia się w:
International Journal of Applied Mathematics and Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A parallel decomposition algorithm for shortest path problem in large-size mesh networks
Równoległy algorytm dekompozycyjny dla problemu dróg najkrótszych w sieciach dużych rozmiarów typu krata
Autorzy:
Tarapata, Z.
Powiązania:
https://bibliotekanauki.pl/articles/210048.pdf
Data publikacji:
2010
Wydawca:
Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
Tematy:
dekompozycyjny algorytm dróg najkrótszych
równoległy algorytm dróg najkrótszych
planowanie tras wielorozdzielczych
decomposition shortest paths algorithm
parallel shortest paths algorithm
multiresolution path planning
Opis:
The paper presents parallel approach for shortest path problem and it extends some decomposition shortest path algorithm (DSP). It is based on rectangular mesh graph of large size which may represent, e.g., network of streets in the city, network of squares of terrain (as a model of a battlefield). A method of parallelization DSP algorithm is proposed. The main advantage of the method is negligible communication between processors. Acceleration and effectiveness of the PDSP algorithm in a case of parallelization and without parallelization of some internal steps of the algorithm are defined and simulation results of these functions for two types of structure of parallel computation systems (hypercube and mesh) are shown. Moreover, some suggestions for further improvements in the PDSP algorithm are proposed.
W artykule opisano metodę zrównoleglenia pewnego algorytmu dekompozycyjnego wyznaczania dróg najkrótszych (DSP). Bazuje on na sieciach dużych rozmiarów o strukturze typu krata, które mogą reprezentować sieć dróg w mieście, sieć kwadratów podziału terenu w grach komputerowych. Zaproponowano metodę (PDSP) zrównoleglenia algorytmu DSP. Podstawową cechą proponowanej metody jest minimalizacja konieczności komunikacji między procesorami wykonującymi obliczenia równoległe. Oszacowano przyspieszenie i efektywność algorytmu równoległego w przypadku zrównoleglenia i niezrównoleglenia niektórych wewnętrznych kroków algorytmu, jako funkcję liczby procesorów równoległych oraz podano wyniki symulacji przebiegu wartości tych funkcji dla różnych wielkości sieci i dwóch typów struktur systemu obliczeń równoległych (hipersześcian i krata). Ponadto podano pewne sugestie, co do zwiększenia efektywności proponowanego algorytmu.
Źródło:
Biuletyn Wojskowej Akademii Technicznej; 2010, 59, 3; 295-306
1234-5865
Pojawia się w:
Biuletyn Wojskowej Akademii Technicznej
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An improved approximation algorithm for optimal routes generation in public transport network
Poprawiona wersja pewnego aproksymacyjnego algorytmu generującego optymalne trasy w sieci transportu publicznego
Autorzy:
Koszelew, J.
Powiązania:
https://bibliotekanauki.pl/articles/341189.pdf
Data publikacji:
2010
Wydawca:
Politechnika Białostocka. Oficyna Wydawnicza Politechniki Białostockiej
Tematy:
sieć transportu publicznego
optymalna trasa
algorytm genetyczny
genetic algorithm
public transport network
time-dependent shortest path
optimal routes
Opis:
This paper presents a new version of Routes Generation Matrix Algorithm, called Routes Generation Matrix Improved Algorithm (RGMIA), for determining routes with optimal travel time in public transport network. The method was implemented and tested on the real public transport network in Warsaw city. This network was completed with walk links and therefore resultant routes are more practical and can perform various users’ preferences. Effectiveness of the improved method was compared in two aspects: time complexity and quality of results, with another two algorithms - previous version of Routes Generation Matrix Algorithm (RGMA) and Routes Generation Genetic Algorithm (RGGA). RGMA and RGGA algorithms were described in previous author’s papers [9,10].
Artykuł zawiera opis poprawionej wersji algorytmu generującego optymalne trasy w sieci transportu publicznego uzupełnionej o linki piesze, nazywanego przez autora Routes Generation Matrix Improved Algorithm (RGMIA). Trasy generowane przez RGMIA są optymalne pod względem czasu realizacji i mogą zawierać odcinki piesze, co sprawia, że wynikowe ścieżki są bardziej praktyczne i mogą spełniać określone preferencje użytkowników środków transportu. Algorytm został zaimplementowany i przetestowany na danych realnej sieci transportowej. Efektywność poprawionej metody została porównana w dwóch aspektach: złożoności czasowej i jakości wynikowych tras, z poprzednią wersją algorytmu nazwaną Routes Generation Matrix Algorithm (RGMA) oraz z metodą genetyczną Routes Generation Genetic Algorithm (RGGA). Algorytmy RGMA oraz RGGA zostały opisane w poprzednich artykułach autora.
Źródło:
Zeszyty Naukowe Politechniki Białostockiej. Informatyka; 2010, 5; 5-17
1644-0331
Pojawia się w:
Zeszyty Naukowe Politechniki Białostockiej. Informatyka
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A comparison between Dijkstra algorithm and simplified ant colony optimization in navigation
Analiza porównawcza algorytmu Dijkstry i uproszczonego algorytmu mrówkowego w nawigacji
Autorzy:
Dramski, M.
Powiązania:
https://bibliotekanauki.pl/articles/360173.pdf
Data publikacji:
2012
Wydawca:
Akademia Morska w Szczecinie. Wydawnictwo AMSz
Tematy:
poszukiwanie najkrótszej drogi
akwen ograniczony
nawigacja
shortest path routing
restricted area
navigation
Opis:
In this paper, two different shortest path routing algorithms in respect of basic navigation problems are discussed. First of them is a “state of art” in computer science – well known Dijkstra algorithm. The second one is a method based on artificial intelligence – simplified ant colony optimization proposed originally by Marco Dorigo. Author used both ways to find an optimal / suboptimal route for a ship in a restricted area. Results showed the advantages and disadvantages of both algorithms in simple static navigation situations.
W artykule omówiono dwa różne algorytmy poszukiwania najkrótszej drogi w odniesieniu do zagadnień nawigacji. Pierwszym z nich jest algorytm Dijkstry, stanowiący podstawę rozwiązywania tego typu problemów. Drugi to metoda bazująca na sztucznej inteligencji – uproszczony algorytm mrówkowy, zaproponowany przez Marco Dorigo. Autor używał obu sposobów w celu uzyskania optymalnej, bądź suboptymalnej trasy dla statku na akwenie ograniczonym. Rezultaty badań pokazały korzyści i wady ze stosowania obu rozwiązań w prostych sytuacjach nawigacyjnych.
Źródło:
Zeszyty Naukowe Akademii Morskiej w Szczecinie; 2012, 29 (101); 25-29
1733-8670
2392-0378
Pojawia się w:
Zeszyty Naukowe Akademii Morskiej w Szczecinie
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Lazy shortest path computation in dynamic graphs
Autorzy:
Aioanei, D.
Powiązania:
https://bibliotekanauki.pl/articles/305443.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
single-source shortest path
dynamic graph
livewire
active snake
interactive image segmentation
Opis:
We address the problem of single-source shortest path computation in digraphs with non-negative edge weights subjected to frequent edge weight decreases such that only some shortest paths are requested in-between updates. We optimise a recent semidynamic algorithm for weight decreases previously reported to be the fastest one in various conditions, resulting in important time savings that we demonstrate for the problem of incremental path map construction in usersteered image segmentation. Moreover, we extend the idea of lazy shortest path computation to digraphs subjected to both edge weight increases and decreases, comparing favourably to the fastest recent state-of-the-art algorithm.
Źródło:
Computer Science; 2012, 13 (3); 113-137
1508-2806
2300-7036
Pojawia się w:
Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Selected shortest path in the graph algorithms with a use of trapezoidal grid
Autorzy:
Dramski, M.
Mąka, M.
Powiązania:
https://bibliotekanauki.pl/articles/393451.pdf
Data publikacji:
2012
Wydawca:
Polskie Stowarzyszenie Telematyki Transportu
Tematy:
nawigacja
najkrótsza trasa
ograniczony teren
shortest path
safe route
restricted area
navigation
trapezoidal grid
Opis:
This paper presents the possiblities of the use of the shortest path in the graph algorithms in ship’s safe route choice process in a restricted area. To create a graph, a trapezoidal mesh based on the S-57 digital map data was used. Numerical experiments were carried out and their results are discussed.
Źródło:
Archives of Transport System Telematics; 2012, 5, 4; 3-7
1899-8208
Pojawia się w:
Archives of Transport System Telematics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Tło teoretyczne dla adaptacyjnego, dynamicznego modelu wyboru ścieżki w modelu ruchu
Theoretical background for adaptive and dynamic path choice model in traffic modelling
Autorzy:
Kucharski, R.
Powiązania:
https://bibliotekanauki.pl/articles/248174.pdf
Data publikacji:
2012
Wydawca:
Stowarzyszenie Inżynierów i Techników Komunikacji Rzeczpospolitej Polskiej
Tematy:
najkrótsza ścieżka
dynamiczny problem najkrótszej ścieżki
próbowanie ścieżek
wybór ścieżki w sieci transportowej
adaptacja modeli ruchu
shortest path
dynamic problem of the shortest path
path sampling
route choice in transportation network
adaptation of traffic models
Opis:
Niniejszy artykuł stanowi podstawę teoretyczną dla zagadnienia adaptacyjnego wyboru ścieżki w sieci transportowej. Na jego podstawie możliwe będzie sformułowanie adaptacyjnego modelu wyboru ścieżki na potrzeby makroskopowego modelowania ruchu, co jest przedmiotem pracy doktorskiej autora. W artykule autor omawia w szczególności podstawy i najnowsze teorie dla następujących trzech obszarów modelowania: - wyszukiwania najkrótszej ścieżki w sieci transportowej (ang. shortest path search), - próbkowania ścieżek (ang.: path sampling), - wyboru ścieżki (ang.: route choice). W części pierwszej opisano podstawowe i bardziej zaawansowane algorytmy wyszukiwania najkrótszej ścieżki w sieci transportowej. Pokazano zarówno klasyczne algorytmy, ich modyfikacje, jak i najnowsze propozycje. Omówiono przypadki dla sieci statycznej, dynamicznej i stochastycznej. Część ta jest podstawą dla dalszych części, w których omawiane są modele zawierające implicite algorytmy wyszukiwania najkrótszej ścieżki. Część druga to omówienie metod próbkowania ścieżek, czyli określania zbioru potencjalnie efektywnych ścieżek łączących źródło z celem. Pokazano próby rozwiązania tego problemu, który (jak argumentuje wielu badaczy) jest dotąd nierozwiązany w praktyce, a istniejące metody dostarczają jedynie heurystycznych przybliżeń. Pokazano tu w szczególności autorską propozycje rozszerzenia istniejącej metody próbkowania Łańcuchem Markowa Metropolisa-Hastingsa na przypadek zmiennej w czasie sieci stochastycznej. Część trzecia to omówienie modeli wyboru ścieżki spośród możliwych. Pokazano tu zarówno klasyczne modele logitowe, ich modyfikacje, jak i nieliczne alternatywne metody wyboru ścieżki. W końcowej części omówiono podejście do adaptacyjności w każdej z metod omawianych wcześniej. Wiele użytych w artykule nazw jest własną próbą tłumaczenia nazw angielskich, jako że autor zdaje sobie sprawę z ułomności własnych tłumaczeń, w nawiasach przy każdym pierwszym użyciu podano odpowiednik angielski.
Article is a theoretical background needed to define adaptive route choice model for transport modelling. The aim is to define state-of-the-art and state-of-the-practice in theoretical models which constitute route choice modelling, namely shortest path search, route sampling, and route choice modelling. Article shows basic and advanced techniques of solving mentioned models. Static, dynamic, and stochastic cases of transport networks are discussed. Examples include the most recent proceedings. Adaptive aspects of models are emphasized.
Źródło:
Zeszyty Naukowo-Techniczne Stowarzyszenia Inżynierów i Techników Komunikacji w Krakowie. Seria: Materiały Konferencyjne; 2012, 2(98); 134-150
1231-9171
Pojawia się w:
Zeszyty Naukowo-Techniczne Stowarzyszenia Inżynierów i Techników Komunikacji w Krakowie. Seria: Materiały Konferencyjne
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Artificial intelligence in solving collision problem in restricted area
Autorzy:
Mąka, M.
Dramski, M.
Powiązania:
https://bibliotekanauki.pl/articles/359349.pdf
Data publikacji:
2013
Wydawca:
Akademia Morska w Szczecinie. Wydawnictwo AMSz
Tematy:
shortest path
safe route
restricted area
trapezoidal grid
area discretization
simplified ant algorithm
A* algorithm
Opis:
This paper presents one of the approaches to solve the collision problem in restricted area for two moving objects using artificial intelligence (SACO algorithm). Although AI should be used only when the classic methods fail, a simple comparison between them is very interesting. As we know the main task of navigation is to conduct safely an object from the point of departure to destination. This problem does not seem easy, especially if we consider the movement in restricted areas such narrow passages, ports etc.
Źródło:
Zeszyty Naukowe Akademii Morskiej w Szczecinie; 2013, 36 (108) z. 2; 118-122
1733-8670
2392-0378
Pojawia się w:
Zeszyty Naukowe Akademii Morskiej w Szczecinie
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bi-directional search in route planning in navigation
Autorzy:
Dramski, M.
Powiązania:
https://bibliotekanauki.pl/articles/360091.pdf
Data publikacji:
2014
Wydawca:
Akademia Morska w Szczecinie. Wydawnictwo AMSz
Tematy:
shortest path
safe route
restricted area
bi-directional search
Dijkstra algorithm
Opis:
The shortest path problem is one of the most significant ones in the field of maritime navigation. One of the most efficient algorithms was proposed by E. Dijkstra in 1959. Taking into account the development of computer technology was offered another interesting approach to the issue. The main idea is to execute the shortest path algorithm simultaneously forward from the source and backward from the target. The results are presented and discussed.
Źródło:
Zeszyty Naukowe Akademii Morskiej w Szczecinie; 2014, 39 (111); 57-62
1733-8670
2392-0378
Pojawia się w:
Zeszyty Naukowe Akademii Morskiej w Szczecinie
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Method of Path Selection in the Graph - Case Study
Autorzy:
Neumann, T.
Powiązania:
https://bibliotekanauki.pl/articles/116904.pdf
Data publikacji:
2014
Wydawca:
Uniwersytet Morski w Gdyni. Wydział Nawigacyjny
Tematy:
Path Selection
Method of Path Selection
graph theory
Dijkstra algorithm
route planning
Cutting-Edge Thinking Mechanisms
New Paths Searching
shortest path
Opis:
This paper presents a different perspective on the Dijkstra algorithm. In this paper algorithm will be used in the further analysis to find additional paths between nodes in the maritime sector. In many cases, the best solution for a single criterion is not sufficient. I would be the search for more effective solutions of the starting point to use for subsequent analysis or decision making by the captain of the ship. Using cutting-edge thinking mechanisms, it is possible to create a decision support system based on known Dijkstra's algorithm.
Źródło:
TransNav : International Journal on Marine Navigation and Safety of Sea Transportation; 2014, 8 no. 4; 557-562
2083-6473
2083-6481
Pojawia się w:
TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria
Autorzy:
Góngora, P. A
Rosenblueth, D. A.
Powiązania:
https://bibliotekanauki.pl/articles/329934.pdf
Data publikacji:
2015
Wydawca:
Uniwersytet Zielonogórski. Oficyna Wydawnicza
Tematy:
shortest path
Bellman–Ford algorithm
Nash equilibrium
BDD
model checking
najkrótsza ścieżka
równowaga Nasha
sprawdzanie modelu
Opis:
Consider games where players wish to minimize the cost to reach some state. A subgame-perfect Nash equilibrium can be regarded as a collection of optimal paths on such games. Similarly, the well-known state-labeling algorithm used in model checking can be viewed as computing optimal paths on a Kripke structure, where each path has a minimum number of transitions. We exploit these similarities in a common generalization of extensive games and Kripke structures that we name “graph games”. By extending the Bellman–Ford algorithm for computing shortest paths, we obtain a model-checking algorithm for graph games with respect to formulas in an appropriate logic. Hence, when given a certain formula, our model-checking algorithm computes the subgame-perfect Nash equilibrium (as opposed to simply determining whether or not a given collection of paths is a Nash equilibrium). Next, we develop a symbolic version of our model checker allowing us to handle larger graph games. We illustrate our formalism on the critical-path method as well as games with perfect information. Finally, we report on the execution time of benchmarks of an implementation of our algorithms.
Źródło:
International Journal of Applied Mathematics and Computer Science; 2015, 25, 3; 577-596
1641-876X
2083-8492
Pojawia się w:
International Journal of Applied Mathematics and Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 29

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies