Grupowa eksploracja

Wyobraźmy sobie sytuację, w której grupa speleologów chce wyeksplorować nieznaną jaskinię. Przy każdym rozgałęzieniu muszą podejmować decyzję, ilu z nich pójdzie każdym z nowych tuneli.

Być może czasami będzie się opłacało zostawić część z nich przy rozgałęzieniu. Niektóre z tuneli będą się, być może, kończyły ślepo, a niektóre będą się dalej rozgałęziały. Speleolodzy mają telefony i mogą się ze sobą komunikować, więc gdy jeden z nich odkryje tunel z dużą liczbą rozgałęzień, może wezwać posiłki. Intuicyjnie rozsądne wydaje się wysyłanie większej liczby speleologów w te rejony jaskini, w których jest więcej tuneli. Chcielibyśmy jakoś sformalizować (i nieco uprościć) ten problem i przeanalizować takie naturalne podejście. Uproszczenia będą dwa: jaskinia będzie przedstawiona jako drzewo, czyli spójny graf bez cykli, a zespół speleologów będzie dość liczny...

Problem definiujemy następująco: mamy danych $k$ agentów, początkowo umieszczonych w korzeniu $r$ nieznanego drzewa

T = (V ,E)

o znanej liczbie wierzchołków

n = V .

Drzewo jest nieznane, to znaczy, że nasza początkowa wiedza to tylko liczba krawędzi wychodzących z korzenia. W pierwszym kroku nasz algorytm musi wybrać, ilu agentów przetrawersuje krawędzie wychodzące z $|r,$ a ilu zostanie w $|r$ do następnej rundy. Jeżeli agentowi przydzielimy trawersowanie krawędzi z $r$ do pewnego sąsiada $v,$ to przejście krawędzi zajmie agentowi całą rundę i pojawi się on w wierzchołku $v$ na początku następnej rundy. W następnej rundzie będzie on mógł przetrawersować dowolną krawędź wychodzącą z $v.$ Wszyscy agenci, którzy w danej rundzie przechodzą krawędzie, robią to równocześnie.

Przez $D$ będziemy oznaczać odległość od korzenia $|r$ do najdalszego liścia $|l$ w drzewie $|T.$ Odległość jest liczona jako liczba krawędzi na ścieżce łączącej $r$ z $l.$ Oczywiście, nie jesteśmy w stanie wyeksplorować w czasie mniejszym niż $, D$ ponieważ przejście ścieżki z $|r$ do $l$ zajmuje $D$ rund.

Gdy wierzchołek jest odwiedzony przez pewnego agenta po raz pierwszy, to otrzymujemy informację o jego stopniu (liczbie wychodzących krawędzi). Ponadto dostajemy też informację o tym, która krawędź prowadzi do korzenia. Po pewnej liczbie kroków eksploracji już coś wiemy o wyglądzie drzewa $T .$ Oznaczmy przez $|T t$ poddrzewo drzewa $T ,$ składające się z wierzchołków, które zostały poznane do chwili $|t.$ Na przykład $|T 1$ to korzeń razem z dziećmi korzenia, ponieważ już na początku pierwszej rundy wiemy, ile dzieci ma korzeń. Drzewo $T t$ zatem zawiera pewne wierzchołki, które nie są jeszcze odwiedzone, ale są już znane. Dla $v ∈ V$ oznaczmy przez $|T t (v)$ poddrzewo drzewa $|T t$ zawierające tylko te wierzchołki, dla których $v$ jest przodkiem (ucinamy krawędź łączącą $v$ z jego rodzicem i dostajemy $T t (v)$ ). Przez $|L(T t (v))$ oznaczamy liczbę wierzchołków znanych, ale nieodwiedzonych w drzewie $T t (v).$ Czasami na wierzchołki znane, ale nieodwiedzone będziemy mówili "nieukończone ścieżki", ponieważ każdy taki wierzchołek jest korzeniem, być może dużego, nieznanego drzewa.

Dostajemy do dyspozycji pokaźnych rozmiarów zespół agentów

c n⌉, k = ⌈D

dla pewnej stałej $|c > 1,$ ale chcemy eksplorować szybko, czyli w czasie jak najbliższym $. |D$

Propozycja algorytmu

Na początku wszyscy agenci w korzeniu są nieaktywni. W każdej rundzie aktywujemy $x$ agentów w korzeniu ( $x$ wyznaczymy później). Wszyscy aktywni agenci w każdej rundzie idą w dół drzewa. Agentów dzielimy proporcjonalnie do liczby nieukończonych ścieżek w poddrzewach. Drobnym niuansem są zaokrąglenia; w pseudokodzie zapiszemy wszystko dokładnie:

$Algorithm 𝒜 T,r,x attime step s: Aktywujx agentó w w korzeniur. for each odwiedzonyv > V T s do:{ustalamy,gdzieposł aćagentó w zv} s Niech 𝒜v – zbió ragentó w w vnapoczątku rundy s. Oznaczm y przez v1,v2,... ,vsd wszystkiedzieciv. Niech i argmax is L T vi .{dziecko znajwiększą liczbą„nieukoń czonychścieżek” } Podziel𝒜v na rozłącznezbiory 𝒜v1,𝒜v2,...,𝒜vd,takieże: @@@S𝒜 sv S L--T--s---vi---AAA (i) S𝒜viS @@ L T s v AA ,dlakażdegoi > 1,2,...,d i , > s ? (ii) S𝒜vi S S𝒜v S Pi> 1;2;:::;d i S𝒜viS. foreachi > 1,2,...,d do foreach agentg > 𝒜vi domove s g tovertexvi. endalgorithm 𝒜.$

Analiza

Algorytm $𝒜$ nie robi niczego odkrywczego, po prostu wysyła więcej agentów tam, gdzie jest więcej ścieżek do odkrycia. Ale jego analiza nie jest oczywista. Algorytm, odkrywając kolejne wierzchołki drzewa, na bieżąco zmienia wartości liczby nieukończonych ścieżek w poddrzewach (funkcja $L$ ), co ma wpływ na proporcje podziału liczby agentów. Wydaje się, że jest to kluczowa własność algorytmu, więc w naszej analizie musimy ją zbadać. Oczywiście, musimy też wyznaczyć odpowiednią wartość parametru $x.$ Na razie ustalmy tylko, że $x > 2n.$

Weźmy dowolny liść $f$ z drzewa $|T$ i ścieżkę długości $⩽DD f$ łączącą $f$ z korzeniem $r.$ Oznaczmy tę ścieżkę przez $fℱ = ( f0, f1, f2,..., fD ),$ gdzie $| f0 = r$ i $f | fD = f.$ Chcemy się przyjrzeć, jak liczne grupy agentów będą wędrowały po ścieżce $ℱ.$ Liczba agentów wysyłana wzdłuż ścieżki zależy od liczby nieukończonych ścieżek w odpowiednich poddrzewach. Jeżeli oznaczymy $i i λ j = L(T ( f j)),$ to $|i$ -tym w kroku z wierzchołka $| f j$ wyślemy do $f j+1$ mniej więcej (z dokładnością do zaokrągleń) $λ i |- j+1 λ i j$ -tą część agentów znajdujących się w $f j$ na początku rundy $i.$ Zapomnijmy na chwilę o zaokrągleniach i pójdźmy dalej tym tropem. Do liścia $| f$ dotrze

−1 i+D ff λ i λ i+1 λ D −1 αi = x-1-i---2i+1-⋯ -- i+D--- ff−1 λ0 λ 1 λ D

agentów wysłanych w rundzie $i$ z korzenia. Zauważmy, jak wyglądają pierwsze dwie wartości:

$pict$

Jeżeli wymnożymy $α1⋅α 2,$ to dość dużo się uprości. Wymnóżmy zatem $|a$ kolejnych wartości $|α . i$ Biorąc pod uwagę, że z definicji funkcji $L$ mamy $1⩽ λ ji ⩽ n,$ to dostaniemy $a xa |M αi⩾ -----. i 1 na+D$ Czyli jeżeli ustalimy $log2n D a =⌈ log-(x/(2n))-⌉ , 2$ to dostaniemy $a a L i 1α i⩾ 2 ,$ czyli dla pewnego $∗ | j ∈ {1,2,...,a}$ mamy $α j ⩾ 2.$ Gdyby nie było zaokrągleń i każde dziecko dostawałoby należny przydział agentów, to $α j$ agentów spośród grupy, która wyrusza w rundzie $| j∗,$ dotarłoby do liścia $| f.$ W rzeczywistości liczby agentów są czasem zaokrąglane w dół, zgodnie z regułą (i) z algorytmu, ale można pokazać, że te zaokrąglenia zbyt dużo nie psują.

Przyjrzyjmy się liczbie agentów, podążających ścieżką $ℱ,$ spośród grupy, która wyrusza w rundzie $∗ j .$ Zauważmy, że w przypadku, gdy $j +i j +i |λi+1 /λi > 1/2,$ to wtedy drzewo $|T j+i ( fi+1)$ zawiera co najmniej połowę wszystkich otwartych ścieżek drzewa $|T j +i ( fi).$ W takim przypadku wierzchołek $| fi+1$ będzie tym wyróżnionym dzieckiem wierzchołka $| fi$ i dostanie swój należny przydział agentów (reguła (ii)). Zauważmy, że $α j$ jest iloczynem $|x$ i pewnej liczby czynników nie większych od $|1.$ Skoro $α j∗ ⩾ 2,$ to co najwyżej $log x − 1 2$ z tych czynników może być nie większych niż $| 1/2.$ Agenci, którzy wyruszyli z korzenia w rundzie $∗ j$ i podążali ścieżką $ℱ,$ zostali "zaokrągleni w dół" co najwyżej $|log2 x− 1$ razy. Stąd da się już łatwo wykazać, że z grupy, która wyruszyła w rundzie $j∗,$ co najmniej jeden agent dotrze do liścia $f .$ Jeżeli wypuścimy z korzenia co najmniej $log2na = ⌈--D---------⌉ log2(x/(2n))$ grup agentów, to jedna z nich wyeksploruje dowolnie wybrany liść $| f,$ czyli $|a$ grup wyeksploruje całe drzewo. Całkowity czas eksploracji to $logn −1⩽D⋅(1+2), a + D log2(x/(2n))$ ponieważ tyle rund potrzeba, żeby $a$ -ta grupa dotarła do liści. Łączna liczba użytych agentów to co najwyżej $log2n ⋅(1+). x ⋅D log2(x/(2n))$ Ustalając $x = nc/b$ dla odpowiednio dobranej stałej $|b,$ dostajemy:

Twierdzenie. Dla dowolnego ustalonego $|c > 1$ i znanego $n$ problem eksploracji drzew może być rozwiązany w czasie $1 ⋅(1++o(1)) D c−1$ przy użyciu $nc⌉ ⌈D$ agentów.

Notacja $|o(1)$ oznacza funkcję, która dąży do 0 dla $n$ dążącego do nieskończoności. Zauważmy, że znajomość $n$ jest potrzebna algorytmowi jedynie do podziału zespołu wszystkich $k$ agentów na grupy po $x.$ Da się skonstruować algorytm, który eksploruje w czasie $), |O(D$ bez znajomości $n,$ używając $nc |D$ agentów.

Uwagi końcowe

Można wykazać, że nie da się eksplorować szybciej niż w czasie $⋅(1+1−o(1)), D c$ czyli jesteśmy już dość blisko optymalnego algorytmu.
Algorytm można uogólnić na dwa sposoby. Można przerobić na wersję rozproszoną, gdzie agenci podejmują suwerenne decyzje, bazując na swojej wiedzy, i mogą się komunikować z innymi agentami będącymi w tym samym wierzchołku. Można też w ten sposób eksplorować dowolne grafy. Co ciekawe, oba uogólnienia nie dodają zbyt dużo do czasu eksploracji, czyli cała trudność problemu leżała w "centralnie sterowanej" eksploracji drzew.
Czytelników, którzy zastanawiają się, czy to podejście da się zastosować dla mniejszej grupy agentów, gorąco zachęcam do próbowania.