Wyniki wyszukiwania - Biblioteka Nauki

1

A scaling out-of-kilter algorithm for minimum cost flow

100%

Ciupala L.

Control and Cybernetics

|

2005

|

tom Vol. 34, no 4

1169-1174

EN

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.

2

Shortest path problem solving based on ant colony optimization metaheuristic

100%

Głąbowski M. , Musznicki B. , Nowak P. , Zwierzykowski P.

Image Processing & Communications

|

2012

|

tom Vol. 17, no. 1-2

7--17

EN

The Ant Colony Optimization (ACO) metaheuristic is a versatile algorithmic optimization approach based on the observation of the behaviour of ants. As a result of numerous analyses, ACO has been applied to solving various combinatorial problems. The ant colony metaheuristic proves itsel I' to be efficient in solving NP-hard problems, often generating the best solution in the shortest amount of time. However, not enough attention has been paid to ACO as a means of solving problems that have optimal solutions which can be found using other methods. The shortest path problem is undoubtedly one of the aspects of great significance to navigation and telecommunications. It is used, amongst others, for determining the shortest route between two geographical locations, for routing in packet networks, and to balance and optimize network utilization. Thus, this article introduces ShortestPathACO, an Ant Colony Optimization based algorithm designed to find the shortest path in a graph. The algorithm consists of several subproblems that are presented successively. Each subproblem is discussed from many points of view to enable researchers to find the most suitable solutions to the problems they investigate.

3

Shortest path problem in static navigation situations

100%

Dramski M.

Metody Informatyki Stosowanej

|

2011

|

tom nr 5

173-180

EN

The main task of each navigator is to conduct safely the ship from the point of departure to destination. Although there are many different solutions of this problem, it's still necessary to carry out further research. This is dictated by the specific requirements that are specified, for example by the dynamics of the ship's own or reservoir characteristics. This article presents a short review of different methods such Dijkstra, Bellman-Ford, Floyd or A* algorithms applied to navigation problems. Besides some alternative methods based on artificial intelligence are mentioned. At the end a comparison of these solutions showed the advantages and disadvantages of each approach.

4

A simple linear algorithm for the connected domination problem in circular-arc graphs

100%

Hung R.-W. , Chang M.-S.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 1

137-145

EN

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.

5

A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria

88%

Góngora P. , Rosenblueth D.

International Journal of Applied Mathematics and Computer Science

|

2015

|

tom 25

|

nr 3

577-596

EN

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.

6

Bi-directional search in route planning in navigation

88%

Dramski M.

Zeszyty Naukowe / Akademia Morska w Szczecinie

|

2014

|

tom nr 39 (111)

57--62

EN

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.

7

Distributed asynchronous algorithms in the Internet - new routing and traffic control methods

75%

Karbowski A.

Journal of Telecommunications and Information Technology

|

2005

|

tom nr 3

29-36

EN

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.

8

Sequential Classification of Palm Gestures Based on A* Algorithm and MLP Neural Network for Quadrocopter Control

75%

Wodziński M. , Krzyżanowska A.

|

tom 24

|

nr 2

9

Artificial intelligence in solving collision problem in restricted area

75%

Mąka M. , Dramski M.

Zeszyty Naukowe / Akademia Morska w Szczecinie

|

2013

|

tom nr 36 (108) z. 2

118--122

EN

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.

10

Sequential Classification of Palm Gestures Based on A* Algorithm and MLP Neural Network for Quadrocopter Control

75%

Wodziński M. , Krzyżanowska A.

Metrology and Measurement Systems

|

2017

|

tom Vol. 24, nr 2

265--276

EN

This paper presents an alternative approach to the sequential data classification, based on traditional machine learning algorithms (neural networks, principal component analysis, multivariate Gaussian anomaly detector) and finding the shortest path in a directed acyclic graph, using A* algorithm with a regression-based heuristic. Palm gestures were used as an example of the sequential data and a quadrocopter was the controlled object. The study includes creation of a conceptual model and practical construction of a system using the GPU to ensure the realtime operation. The results present the classification accuracy of chosen gestures and comparison of the computation time between the CPU- and GPU-based solutions.

11

Proposal of the prediction algorithm of the object’s position in restricted area

63%

Dramski M. , Mąka M.

Archives of Transport System Telematics

|

2015

|

tom Vol. 8, iss. 2

13--16

EN

In this paper an algorithm of finding the optimal path of an object in restricted area, focusing on the position prediction, is presented. Moving in the restricted area requires not only the knowledge of this area, but also the current and future position of other objects present in it. These informations let to minimalize the possible collision risk. It’s significant not only due to the safety, but also to the economic factors. This approach is the further development of the investigations in the area of finding the optimal path in restricted area, carried out at the Maritime University of Szczecin. The authors propose the algorithm for the use in the decision support systems in maritime navigation, but it could be also applied in the other areas of transport.

12

Method of Path Selection in the Graph - Case Study

63%

Neumann T.

TransNav : International Journal on Marine Navigation and Safety of Sea Transportation

|

2014

|

tom Vol. 8 no. 4

557--562

EN

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.

13

Optimisation of water distribution networks design by minimizing the total length

63%

Lahiouel Y. , Chaoui K. , Khezzar L. , Haddad A. , Azari Z.

Engineering Transactions

|

2005

|

tom Vol. 53, iss. 2

165-183

EN

The aim of the present work is to establish a new algorithm for the optimization of the design of water distribution networks. The proposed algorithm makes it possible to connect the nodes and the sources using the shortest path to obtain a final looped configuration. A novel method, the "minimal length algorithm", is proposed. It uses the advantages of existing methods and exceeds their limitations. Some of the well-known existing methods are the shortest path algorithm, the minimum spanning tree algorithm and a novel method published previously. The developed algorithm is implemented into a user-friendly interactive computer program which allows the design of looped systems with minimal length ensuring least cost, reliability of the network and hence the availability of water.

14

Selected shortest path in the graph algorithms with a use of trapezoidal grid

63%

Dramski M. , Mąka M.

Archives of Transport System Telematics

|

2012

|

tom Vol. 5, iss. 4

3-7

EN

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.

15

On a fair manifold fare rating on a long traffic line

63%

Palúch S. , Majer T.

Transport Problems

|

2017

|

tom T. 12, z. 2

5--11

EN

The paper studies the possibilities to design a fair manifold tariff on a long traffic line. If a single tariff is used on a long bus or railway line, passengers travelling long distances are favoured at the expense of those travelling short distances. The fairest approach to tariff is setting an individual tariff for every origin–destination relation of line stops that expresses real travel costs. However, sometimes the individual tariff is too complicated and is therefore replaced by double-, triple- or manifold tariff. This paper shows how to design a manifold tariff in order to minimize unfairness to passengers.

16

Tło teoretyczne dla adaptacyjnego, dynamicznego modelu wyboru ścieżki w modelu ruchu

63%

Kucharski R.

Zeszyty Naukowo-Techniczne Stowarzyszenia Inżynierów i Techników Komunikacji w Krakowie. Seria: Materiały Konferencyjne

|

2012

|

tom Nr 2(98)

134--150

PL

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.

EN

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.

17

Algorytm wyznaczania najkrótszej ścieżki w grafie skierowanym w zbiorze liczb rozmytych

63%

Neumann T.

Logistyka

|

2014

|

tom nr 6

7782--7787

PL

W artykule przedstawiono algorytm umożliwiający znalezienie najkrótszej ścieżki w grafie skierowanym. Do opisu krawędzi grafów zaproponowano użycie wartości rozmytych. Do obliczeń zaproponowano wykorzystanie prostej defuzyfikacji wartości rozmytych do wartości ostrych. Pokazano, że taka metoda w przypadku znajdowania najkrótszej ze ścieżek może znaleźć zastosowanie.

EN

The paper presents an algorithm that allows finding the shortest path in a directed graph. To describe the edges of the graph proposed to use fuzzy values. For the calculation proposed to use a simple defuzzification to the sharp values. It has been shown that this technique for finding the shortest path can be used.

18

Problem wyboru trasy w sieci telekomunikacyjnej z opisem połączeń za pomocą liczb rozmytych

63%

Neumann T.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2014

|

tom nr 11

1393--1395

PL

Przedstawiono algorytm umożliwiający znalezienie najkrótszej ścieżki w grafie. Dane opisujące krawędzie przedstawiono za pomocą trapezoidalnej funkcji przynależności. Do obliczeń zaproponowano wykorzystanie prostej defuzyfikacji wartości rozmytych do wartości ostrych.

EN

The paper presents an algorithm that allows finding the shortest path in the graph. Data describing the edges represented are by trapezoidal member-ship function. For the calculation proposed to use a simple defuzzification to the sharp values.

19

Clusterization methods in detecting the restricted areas for sea transport

63%

Dramski M.

Archives of Transport System Telematics

|

2017

|

tom Vol. 10, iss. 1

24--27

EN

Clusterization is one of the data mining techniques which is responsible for classifying data. Selection of the proper parameters leads to some desired clusters behavior. Th is fact can be used in detecting the restricted areas for ships and other units. Th e allowed area can be marked as a data cluster and vice versa. Th e other advantage is the fact that each cluster consists of the set of points which can be used to fi nd the shortest path in given area. In this paper the use of clusterization in detecting restricted areas is described. Few methods are analyzed and the conclusions presented.

20

A Label Correcting Algorithm for the Bus Routing Problem

63%

Widuch J.

Fundamenta Informaticae

|

2012

|

tom Vol. 118, nr 3

305-326

EN

This paper proposes a label correcting algorithm for solving the bus routing problem (BRP). The goal of the BRP is finding a route from the start stop to the final stop minimizing the time and the cost of travel. Additionally the time of starting travel at the start stop is given. The problem belongs to the group of multicriteria optimization problems (MOP), whose the solution is a set of non-dominated solutions. The algorithm makes possible to find all routes which belong to the set of non-dominated solutions. Apart from that the results of experimental tests are presented.