Szybkość przeszukiwania grafu - Publikacja - MOST Wiedzy

Wyszukiwarka

Szybkość przeszukiwania grafu

Abstrakt

Przeszukiwanie grafu pojawiło się jako problem matematyczny ponad 40 lat temu i w najogólniejszej wersji zajmuje się odszukiwaniem jednostki-uciekiniera niezależnie od jego poczynań. Od tamtej pory uzyskano wiele wyników odpowiadających na pytanie o minimalną ilość poszukujących jednostek w różnorodnych modelach, czyli odpowiednią liczbę przeszukiwawczą (ang. serach number) grafu. Popularne warianty problemów przeszukiwania obejmują widzialnych i niewidzialnych uciekinierów, ograniczenie możliwości ruchów jednostek i wymuszenie istnienia pojedynczego, połączonego czystego obszaru. Stosunkowo niewiele uwagi poświęcono czasowi jaki jest potrzebny do przeszukania grafu, wyrażonemu w ilości kroków, zadowalając się ich wielomianową ilością w problemach monotonicznych, czyli takich gdzie uciekinier nie może odwiedzać ponownie przeszukanych obszarów. Skupiając się na szybkości problem przeszukiwania można rozważać pod względem zarówno minimalizacji długości dekompozycji o określonej szerokości jak i formułowania modeli, które ograniczają ilość wykonywanych kroków kosztem zdefiniowania nowego rodzaju liczby przeszukiwawczej, potencjalnie wyższej niż klasyczna. Niniejsza praca ma na celu zebranie informacji na ten temat, przedstawienie głównych idei uzyskanych rozwiązań i otwartych problemów.

Robert Ostrowski. (2017). Szybkość przeszukiwania grafu, 132-138.

Informacje szczegółowe

Kategoria:
Publikacja monograficzna
Typ:
rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
Tytuł wydania:
Badania i Rozwój Młodych Naukowców w Polsce, Nauki techniczne i inżynieryjne : Część VIII strony 132 - 138
Język:
polski
Rok wydania:
2017
Opis bibliograficzny:
Ostrowski R.: Szybkość przeszukiwania grafu// Badania i Rozwój Młodych Naukowców w Polsce, Nauki techniczne i inżynieryjne : Część VIII / ed. dr inż. Jędrzej Nyćkowiak, dr hab. Jacek Leśny prof. UPP Poznań: Młodzi Naukowcy, 2017, s.132-138

wyświetlono 20 razy

Publikacje, które mogą cię zainteresować

Meta Tagi