Przeszukiwanie struktur grafowych - Projekt - MOST Wiedzy

Wyszukiwarka

Przeszukiwanie struktur grafowych

Problematyka przeszukiwania struktur grafowych zyskuje obecnie na znaczeniu, a jednocześnie stanowi już dojrzałą i silnie ugruntowaną dziedzinę badań. Wśród głównych powodów tego faktu można wymienić potencjalne zastosowania oraz silne związki z klasyczną teorią grafów. Dotychczas opisano bardzo wiele modeli przeszukiwania grafów, które zazwyczaj znajdują swoje motywacje w jednym z dwóch powyższych źródeł. W ogólności problem przeszukiwania grafu definiowany jest jako gra pomiędzy dwiema stronami. Jedna ze stron (\emph{poszukujący}) jest odpowiedzialna za odnalezienie celu znajdującego się w odpowiedniej strukturze (grafowej lub geometrycznej), natomiast celem drugiej strony jest pozostanie ukrytym lub nieschwytanym tak długo jak to możliwe. Różnorodne modele znajdują swoje źródła w potencjalnych charakterystykach obu stron, a także w cechach struktury, w której odbywa się powyższa gra. Do typowych charakterystyk obu stron można zaliczyć mobilność, wiedzę czy widoczność. Cechy struktury dyktują podział na problemy grafowe lub geometryczne, prowadząc do kolejnych podziałów w każdej z kategorii. Związki problemów i modeli przeszukiwania grafów z klasyczną teorią grafów stoją niejako u podstaw tego nurtu badań --- odkrycia pozwalające na uzyskanie równoważnych definicji takich parametrów grafowych jak pathwidth, treewidth czy bandwidth, właśnie za pomocą gier przeszukiwawczych, spowodowały gwałtowny rozwój tej nowych modeli przeszukiwania grafów. W konsekwencji odkryto wiele powiązań powyższego typu. Potencjał ku dalszym odkryciom w tym kierunku jest nadal olbrzymi, co stanowi silną motywacją ku podejmowaniu tej tematyki badań. W tym upatrujemy jedną z motywacji ku podjęciu tego tematu --- wyniki uzyskane dla problemów przeszukiwania grafów mogą mieć szerszy wpływ na inne działy teorii grafów. Potencjalne zastosowania podejmowanej problematyki obejmują zagadnienia modelowania ruchu mobilnych autonomicznych jednostek w celu przeszukiwania terenu. Pewne nurty badań w tym kierunku dotyczą kwestii modelowania terenu. W tym zakresie podstawowym akceptowanym modelem jest graf, jako dyskretyzacja ciągłej przestrzeni przeszukiwania, ale także znaczący nurt obecnych badań dotyczy matematycznej analizy struktur geometrycznych. Grafowe i geometryczne modele są niejednokrotnie komplementarne, stąd w niniejszym wniosku planujemy badania w obydwu kierunkach.

Informacje szczegółowe

Finansowanie projektu:
OPUS
Porozumienie:
UMO-2015/17/B/ST6/01887 UMO-2015/17/B/ST6/01887 z dnia 2016-01-27
Okres realizacji:
2016-01-27 - 2019-01-26
Kierownik projektu:
dr hab. inż. Dariusz Dereniowski
Realizowany w:
Wydział Elektroniki, Telekomunikacji i Informatyki
Wartość projektu:
287 280.00 PLN
Typ zgłoszenia:
Krajowy Program Badawczy
Pochodzenie:
Projekt krajowy
Weryfikacja:
Politechnika Gdańska

wyświetlono 31 razy