Application of genetic algorithms in graph searching problem - Publikacja - MOST Wiedzy

Wyszukiwarka

Application of genetic algorithms in graph searching problem

Abstrakt

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 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 an (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 resolves around representing a search strategy as a permutation of edges.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Opublikowano w:
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne nr 18, strony 353 - 358,
ISSN: 1732-1166
Język:
angielski
Rok wydania:
2010
Opis bibliograficzny:
Wrona Ł., Jaworski B.: Application of genetic algorithms in graph searching problem// Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne. -Vol. 18., nr. No 8 (2010), s.353-358
Weryfikacja:
Politechnika Gdańska

wyświetlono 125 razy

Publikacje, które mogą cię zainteresować

Meta Tagi