Modelowanie problemów strażniczych jako grafów dynamicznych - przykładowy sposób analizy skuteczności systemów strażniczych

• Autorzy: Noga P.

Warianty tytułu

EN

Modeling the guarding problems as a dynamic graphs. Example of algorithmm for efficiency evaluation of a guard system

• Języki publikacji: PL

Abstrakty

PL

W problemach strażniczych rozważamy przestrzeń (graf), w której znajduje się intruz i pewna liczba agentów przechwytujących, zaś celem większości algorytmów jest jak najszybsze przechwycenie intruza lub też uniknięcie przez niego detekcji. Zaprezentowany model pozwala na praktyczne rozważanie problemów z życia wziętych przez matematyczne przedstawienie różnorodnych agentów przechwytujących (kamery mobilne i stacjonarne, strażnicy i wiele innych) i możliwość analizy skuteczności danego systemu. W drugiej części pracy przedstawiony będzie algorytm wyszukujący najlepszą (w sensie uniknięcia przechwycenia) ścieżkę pomiędzy dwoma zadanymi wierzchołkami w grafie dynamicznym.

EN

In guard problems we consider a space (graph), a thief inside, and a certain number of agents whose task is to capture the thief. Algorithms usually create a strategy for most efficient capture of thief, or the opposite - best strategy for a thief to avoid detection. Presented model of dynamic graphs allow us to consider practical problems by mathematically describing any kind of guarding agents (cameras: mobile and stationary, guards etc.). In the second part an algorithm is presented for finding the best route for thief (between two points in a dynamic graph) - also known as the worst case scenario for the system.

Słowa kluczowe

PL

modelowanie problemów strażniczych; grafy dynamiczne; systemy strażnicze

EN

modeling the guarding problems; dynamic graphs; algorithm for efficiency evaluation of a guard system

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2010
• Tom: T. 19
• Strony: 385--388
• Opis fizyczny: Bibliogr. 2 poz., rys.

Twórcy

autor

Noga P.

• Politechnika Gdańska Katedra Algorytmów i Modelowania Systemów

Bibliografia

• [1] D. Alberts, G. Cattaneo, G. F. Italiano: An Empirical Study of Dynamic Graph Algorithms ACM Journal On Experimental Algorithmics, volume 2 (1997), article no.: 5.
• [2] E. W. Dijkstra: A note on two problems in connexion with graphs in Numerische Mathematik 1, (1959), s. 269–271.