[podst. teoretyczne inf.] Złożoność pesymistyczna

0

Hej,

Może ktoś z Was wie, jak się definiuje złożoność pesymistyczną dla algorytmów probabilistycznych?

Jako algorytm probabilistyczny rozumiem algorytm, który korzysta z generatora pseudolosowego. Wiadomo, że liczba kroków (lub zajętej pamięci) takiego algorytmu będzie zależna od 2. czynników:

  • rozwiązywanego problemu
  • konkretnej sekwencji z generatora

Złożoność pesymistyczną określa się zawsze dla "najgorszego przypadku". Tylko co tutaj jest najgorszym przypadkiem? Czy biorę tylko <najgorszy problem="problem"> i liczę średnią dla różnych sekwencji losowych generatora, czy biorę parę <najgorszy problem, najgorsza sekwencja>? Sensowniejsze wydaje sie to pierwsze, bo na podstawie drugiego moznaby wnioskowac, ze analiza najgorszego przypadku dla wiekszosci losowych algorytmow konczy sie zawsze jednym wnioskiem: algorytm nie dziala.

Jakoś nie mogę tego nigdzie w necie znaleźć, a pechowo jestem chory i wycieczka do biblioteki po jakąś poważną książkę na temat alg. probabilistycznych nie wchodzi w grę. W zwykłych książkach i wykładach do analizy algorytmów tego NIE MA :(

0

hmm na moje oko to wyglada tak ze jezeli algorytm nie zapamietuje wynikow z genratora to moze "bladzic" i wtedy O(+oo) czyli sie spierdolilo :>, jezeli pamieta wyniki to w najgorzym razie powinna byc standardowa zlozonosc bez randoma zaleznie od algorytmu.

0

Według mnie, jednak należy brać najgorszy zestaw danych pod uwagę.... jeśli dla takiego algo nie działa to wtedy możesz wysnuć ciekawe wnioski jeśli algo działa zbyt długo dla jakiegoś zestawu-odpowidź będzie zła/niedokładna. Ale to gdy mieszasz probalistyke z aproksymatyką... Zazwyczaj używa sie randomizacji aby przyspieszyć jakiś algo i wtedy masz doczynienia z analizą probalistyczną. pesymistyczny przypadek to pesymistyczne dane i pesymistyczna randomizacja-ciężko mi wyobrazić sobie inną definicje.

0

Dobra, dzieki za pomoc, ale udalo mi sie znalezc odpowiedz. Bierze sie pod uwage pesymistyczne zadanie i liczy srednia dla roznych sekwencji. W koncu zawsze moglaby sie trafic sekwencja np. samych zer i wtedy taki algorytm nie dzialalby zbyt dobrze. Tyle, ze jest to bardzo malo prawdopodobne. :) Zlozonosc pesymistyczna dla takich algorytmow okresla sie z odpowiednim prawdopodobienstwem. Np. ze algorytm daje zawsze poprawny wynik w czasie 2(log2(n)) z prawdopodobienstwem 1-1/(n^n).

No to moze jeszcze jedno pytanko. Moze macie pomysly, jak to rozwiazac:


Dana jest trojka <G, s, t> gdzie G to graf skierowany o n wierzcholkach i m krawedziach, s i t to dwa dowolne wezly tego grafu. Znalezc algorytm, ktory odpowie, czy istnieje sciezka z wezla s do wezla t.

Dodatkowe ograniczenia:

  • zlozonosc czasowa algorytmu nie gorsza niz O(m^O(1)) czyli wielomianowa,
  • zlozonosc pamieciowa lepsza niz O(n / 2 ^ sqrt(log n)).

W danym grafie nie mozna nic zapisywac. Graf jest dany jako jeden wierzcholek, ktory mozna "odpytac' o wychodzace z niego krawedzie i w ten sposob dostac sasiadujace wierzcholki itd...

struct wierzcholek {
	vector<wierzholek*> sasiedzi;
};

bool czySaPolaczone(wierzcholek* s, wierzcholek* t);

[browar] dla tego, kto to rozwiaze pierwszy lub udowodni ze sie nie da. Uzywanie Googla dozwolone.

0

hmm ja bym uzyl po prostu zmodyfikowanego bfs lub dfs jezeli trafie na sciezke to break i juz, chyba ze chcesz sprawdzic czy istnieje sciezka i czy jest ona najbardziej optymalna to wtedy dijkstra

0

Gdyby to można było zrobić którymkolwiek ze standardowych algorytmów takich jak BFS, DFS, DFID, WFS, A*, Dijkstra, to bym nie pytał. Niestety żaden z nich nie spełnia założenia o złożoności pamięciowej (patrz treść zadania): ma być lepsza niż O(n / log(sqrt(n))), a więc i lepsza niż O(n). Wszystkie standardowe algorytmy przeszukiwania drzew/grafów mają O(n).

Wszelkie pomysły, nawet głupie (nie tylko propozycje całych rozwiązań) mile widziane. Od razu zaznaczam, że nie wiem, jak to zrobić, ale wierzę, że się da, choć zadanie wygląda na trudniejsze niż te z OI. Próbuję kombinować z jakimiś hybrydami BFS/DFS, ale póki co zawsze złożoność czasowa eksploduje mi wykładniczo gdy tylko chcę zejść z pamięciową poniżej O(n) :( Podstawowy problem jest taki, że NIE MOŻNA PAMIĘTAĆ, które węzły się odwiedziło, a w każdym razie nie wszystkie.

0

hmm skoro nie mozna pamietac wszystkich wezlow to moze najpierw tzreba okreslic te ktore powinno sie pamietac ? bo jezeli w danym wezle bedziesz np: 100x a w drugim 5x to nie warto pamietac drugiego tylko lepiej pamietac ten przez ktory przejdziesz 50x :P

0

Ja bym tu zrobił coś w rodzaju 'mrówki błądzącej po labiryncie':
Mrówka zawsze idzie w losową stronę z tym, że woli iść tam, gdzie jej się wydaje, że jeszcze nie była.
Mrówka zostawia ślady tam gdzie była, ale nieodświerzane ślady z czasem się zacierają.
Losowanie drogi wyglądało by w ten sposób:
Mrówka będąc w węźle A sprawdza gdzie może z niego pujść i Od razu patrzy czy tamte węzły są jusz zaznaczone. Następnie losuje sobie drogę tak by z większym prawdopodobieństwem poszła do nieoznaczonego węzła.

Można jeszcze spróbować Od razu zapisywać ile razy i kiedy ostatnio mrówka odwiedziła ten węzeł (tzn w ramach śladu).
W razie odwiedzenia nowego - nieoznaczonego węzła (gdy zaczyna nam brakować pamięci) któryś z poprzednio zostawionych sladów powinien zniknąć (tesz można to jakoś wylosować :] )

0
Sebo napisał(a)

Ja bym tu zrobił coś w rodzaju 'mrówki błądzącej po labiryncie':
Mrówka zawsze idzie w losową stronę z tym, że woli iść tam, gdzie jej się wydaje, że jeszcze nie była.

A co jeśli mrówka dojdzie do końca grafu? Tzn. jeśli będzie w grafie "ślepa uliczka" - węzeł, z którego nie wychodzi żadna krawędź?

0

...wtedy biedna mała mróweczka waląc głową o [sciana] umiera z wyczerpania i rozpaczy w niemocy znalezienia wyjścia.
A my możemy puścić kolejną mrówkę-zwiadowcę, która miejmy nadzieję nie pójdzie w jej ślady ;)

Jeszcze by się przydało dodać pamięć o przynajmniej poprzednim wierzchołku aktualnej trasy - tak by nigdy nie wracać tą samą drogą :]

1 użytkowników online, w tym zalogowanych: 0, gości: 1