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-6 z 6
    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 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ł
    Tytuł:
    An exact geometry-based algorithm for path planning
    Autorzy:
    Jafarzadeh, H.
    Fleming, C. H.
    Powiązania:
    https://bibliotekanauki.pl/articles/331494.pdf
    Data publikacji:
    2018
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    shortest possible path algorithm
    path planning
    collision free path
    algorytm najkrótszej ścieżki
    planowanie ścieżki
    ścieżka bezkolizyjna
    Opis:
    A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn’2) time, where n is the number of vertices of all polygons and n’ is the number of vertices that are considered in constructing the path network (n’ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2018, 28, 3; 493-504
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    D* Extra Lite: A dynamic A* with search-tree cutting and frontier-gap repairing
    Autorzy:
    Przybylski, M.
    Putz, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/329769.pdf
    Data publikacji:
    2017
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    shortest path planning
    incremental heuristic search
    mobile robot navigation
    video game
    planowanie najkrótszej ścieżki
    wyszukiwanie heurystyczne
    nawigacja robota mobilnego
    gra wideo
    Opis:
    Searching for the shortest-path in an unknown or changeable environment is a common problem in robotics and video games, in which agents need to update maps and to perform re-planning in order to complete their missions. D* Lite is a popular incremental heuristic search algorithm (i.e., it utilizes knowledge from previous searches). Its efficiency lies in the fact that it re-expands only those parts of the search-space that are relevant to registered changes and the current state of the agent. In this paper, we propose a new D* Extra Lite algorithm that is close to a regular A*, with reinitialization of the affected search-space achieved by search-tree branch cutting. The provided worst-case complexity analysis strongly suggests that D* Extra Lite’s method of reinitialization is faster than the focused approach to reinitialization used in D* Lite. In comprehensive tests on a large number of typical two-dimensional path-planning problems, D* Extra Lite was 1.08 to 1.94 times faster than the optimized version of D* Lite. Moreover, while demonstrating that it can be particularly suitable for difficult, dynamic problems, as the problem-complexity increased, D* Extra Lite’s performance further surpassed that of D*Lite. The source code of the algorithm is available on the open-source basis.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2017, 27, 2; 273-290
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    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ł:
    A relation of dominance for the bicriterion bus routing problem
    Autorzy:
    Widuch, J.
    Powiązania:
    https://bibliotekanauki.pl/articles/330092.pdf
    Data publikacji:
    2017
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    multicriteria optimization
    set of nondominated solutions
    bicriterion shortest path problem
    variable weights
    label correcting algorithm
    transportation problem
    optymalizacja wielokryterialna
    zbiór rozwiązań niezdominowanych
    dwukryterialny problem najkrótszej ścieżki
    zmienne wagi
    problem transportowy
    Opis:
    A bicriterion bus routing (BBR) problem is described and analysed. The objective is to find a route from the start stop to the final stop minimizing the time and the cost of travel simultaneously. Additionally, the time of starting travel at the start stop is given. The BBR problem can be resolved using methods of graph theory. It comes down to resolving a bicriterion shortest path (BSP) problem in a multigraph with variable weights. In the paper, differences between the problem with constant weights and that with variable weights are described and analysed, with particular emphasis on properties satisfied only for the problem with variable weights and the description of the influence of dominated partial solutions on non-dominated final solutions. This paper proposes methods of estimation a dominated partial solution for the possibility of obtaining a non-dominated final solution from it. An algorithm for solving the BBR problem implementing these estimation methods is proposed and the results of experimental tests are presented.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2017, 27, 1; 133-155
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-6 z 6

      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