Wyniki wyszukiwania - BazTech

1

Non-monotone graph searching models

Ostrowski R.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2018

|

T. 23

90--96

EN

Graph searching encompasses a variety of different models, many of which share a property that in optimal strategies fugitive can never access once searched regions. Monotonicity, as it is called, is vital in many established results in the field however its absence significantly impedes the analysis of a given problem. This survey attempts to gather non-monotone models, that are less researched in effort of summarizing the results concerning them and open questions left.

PL

Przeszukiwanie grafów obejmuje wiele modeli, z których wiele dzieli własność, że w optymalnych strategiach uciekinier nie może dostać się ponownie do raz przeszukanych obszarów. Własność ta, nazwana monotonicznością, jest istotna w wielu osiągnięciach dziedziny i jej brak znacząco utrudnia analizę problemów. Ten przegląd ma na celu zebranie niemonotonicznych modeli, które są mniej zbadane w celu podsumowania rezultatów i otwartych pytań.

2

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ń.

3

Application of Genetic algorithms in graph searching problem

Wrona Ł., Jaworski B.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2010

|

T. 18

353-358

EN

Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in an environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called the (edge) search strategy. Unfortunately calculating both the optimal search strategy and the search number is NP-hard for general graphs. Furthermore, due to the complexity of the pursuit rules, the application of heuristic solutions is not straightforward. In this paper we suggest a method of applying genetic algorithms to solve graph searching problem. The idea is based on LaPaugh's result on graph searching monotonicity and utilizes representation of a search strategy as a permutation of edges.

PL

Przeszukiwanie grafów to często stosowane podejście do problemu przechwytywania wrogiej jednostki przez grupę mobilnych agentów. Zadanie to jest realizowane w środowisku zamodelowanym za pomocą grafu G. Odpowiadamy na pytanie ile mobilnych agentów jest niezbędnych by przechwycić dowolnie szybkiego, niewidzialnego i bystrego intruza. Liczba ta jest nazywana (krawędziową) liczbą przeszukiwawczą G a strategia, którą realizują agenci - (krawędziową) strategią przeszukiwawczą. Zarówno wyznaczanie liczby przeszukiwawczej jak i strategii przeszukiwawczej jest trudne obliczeniowo. Dodatkowo, ze względu na złożoność zasad, według których odbywa się przechwytywanie, stosowanie podejścia heurystycznego jest utrudnione. W tej pracy sugerujemy metodę zastosowania algorytmów genetycznych w rozwiązywaniu omawianego problemu. W pomyśle wykorzystany jest lemat LaPaugha, dotyczący monotoniczności przeszukiwania grafów i zakłada reprezentację strategii przeszukiwawczej jako permutacji krawędzi.

4

Gwarantowanie bezpieczeństwa w systemie z połączeniami awaryjnymi

Wrona Ł.

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

|

2009

|

T. 13, z. 2

663-671

PL

Rozważamy zapewnianie bezpieczeństwa przed zewnętrznym intruzem w systemie o topologii drzewa, w którym wprowadzono dodatkowe połączenia awaryjne. Grupa mobilnych autonomicznych agentów musi przechwycić intruza, niezależnie od przyjętej przez niego strategii unikania. W literaturze problem ten jest modelowany jako przeszukiwanie grafów. W pracy zawężamy dotychczasowe oszacowanie na liczbę przeszukiwawczą kaktusów podkubicznych, do dwóch możliwych wartości dla każdej ilości odgałęzień z liczbą przeszukiwawczą nie większą niż k. Dokonujemy również pełnej klasyfikacji odgałęzień tzw. typu (**), posiadających rdzeń lub aleję.

EN

We are considering security guaranteeing in systems with tree topology, augmented by additional backup links. A group of mobile autonomous agents needs to capture an invader, regardless of his strategy. In literature this problem is modeled as graph searching. We narrow the currently known search number estimation for cacti of degree 3 to two possible values for each number of branches with search number less than, or equal to k. We also classify type (**) branches, which have a hub or an avenue.