Witajcie moi drodzy! chcialbym zapytac, kiedy oplaca sie stosowac kopiec Fibonacciego do algorytmow wyszukiwania ort! sciezek w grafie, opierajacych sie na strategii zachlannej. mianowicie zaimplementowalem owy kopiec ( implementacja kursorowa), ale czy mimo znacznie mniejszej sredniej zlozonosci asymptotycznej, czy nie oplaca mi sie bardziej zastosowac zwyczajnego kopca? w sumie zwyczajny kopiec ma asymptotyczne oszacowanie kosztow zamortyzowanych znacznie gorsze niz Fibonacci, ale przy kazdej zmienie struktury w fibonaccim musze przestawiac sporo kursorow. w samej operacji insert musze zainicjowac osiem kursorow, i jeszcze zmienic 3 wartosci... Czy moze mi napisac ktos kto mial doswiadczenie przy jakim rozmiarze danych wejsciowych oplaca sie robic kopiec Fibonacciego ? grafem na ktorym ja szukam sciezki jest plansza do gry o rozmiarze 200 x 200, gdzie z kazdego punktu moge wykonac ruch w gore, w dol w prawo i w lewo.
na konkursach rzadko sprawdzarki są wstanie odróżnić (nlogn) od (n), a tymbardziej przy tym kopcu - mniej wyraźna różnica będzie. przede wszystkim kwestia implementacji. tego jak zaimplementujesz to wyszukiwanie i jak zaimplementujesz kopiec.
jak masz plansze 200x200 to jest 40000 pól z każdego możesz przeskoczyć do 400 więc jest 16 000 000 dróg, to dosyć smutna liczba i może sie okazać że trzeba powalczyć żeby takie wyszukiwanie działało mniej niż te 0,5 sekundy.
algorytm nie jest strikte na konkurs, nie on bedzie oceniany, tylko to co zrobi robot bedacy na planszy i korzystajacy miedzy innymi z tego algorytmu aby wypelnic zadania. Robie to na kopcu Fibbonaciego poniewaz bardzo zalezy nam na szybkiej analizie planszy, a nie ma na to za wiele czasu... podobno fibonacci jest najlepszy, ale ponoc stale przy zlozonosci sa wysokie. Ciekaw jestem czy przy rozmiarze danych wejsciowych 40000 oplaca sie go implementowac. i jeszcze jedno, z jednego pukntu nie mozemy dojsc do dowolnego, tylko do przyleglych, czyli mozemy wykonac 4 ruchy, z tych punktach przy brzegu - 3 a w rogach 2, co daje jednak troche mniej sciezek...
nie sprawdzone empirycznie ale według mnie sie nie opłaca przy nie wielkich danych, zresztą, nie możesz wykonać w pętli X operacji na kopcu i X operacji na stercie i zmierzyć czas?
wiem ze nie oplaca sie dla "nieduzych danych"... pytanie o ktore caly czas mi chodzi brzmi - co to znaczy "nieduze". Jaki jest konkretny rozmiar, a dokladnie - czy dla 40000 sie oplaca. Dzieki z odpowiedzi, buzi, pozdro! a testowac mi sie nie chce bo juz to skonczylem ... moze kiedys ...