arturbac <artur_no_spam@no_spam.ebasoft.com.pl> napisał(a):

>
> > Mariusz Marszałkowski pisze:
> >> Możesz napisać kilka zdań o tym jaka jest idea algorytmu o którym mówisz?
> >> Nadaje się on do każdego grafu, czy tylko do niektórych?
>
> Btw to nie jest algorytm zastepujacy samo szukanie najkrotszej sciezki
> ale umozliwiajacy przeprowadzanie szukania na urzadzeniach ktore
> normalnie nie maja szans na to lub przy wielokrotnym wykonywaniu
> (serwery ? ) oszczedzajacy czas znalezienia wyniku.

Chyba nie rozumiem.

Czy chodzi o coś takiego:
1) Wybieram losowy wierzchołek X z pełnego grafu
2) Buduję minimalne drzewo rozpinające na głębokość N węzłów z wierzchołka X
3) Wstawiam do grafu zgrubnego wierzchołek X
4) Usuwam z grafu pełnego X wraz z całym drzewem rozpinającym
5) Zapisuję dodatkową informację o tym że droga z X do listy wierzchołków
nie przekracza N
6) Wracam do 1 jeśli nie warunek stopu

W ten sposób mogę utworzyć graf zgrubny o mniejszym rozmiarze. Jednak
po dojściu do węzła grafu zgrubnego, muszę odczytać z dysku listę
wierzchołków do których on prowadzić. Więc w ten sposób nie będzie
żadnego zysku. Może jedynie zysk na tym, że da się odczytać taką
listę bez losowego naprowadzania głowicy. Nie wiem.

Homeomorfizm też nie wiem jak można wykorzystać. Graf by musiał mieć
dużo prostych na których leżą węzły bez dodatkowych rozgałęzień. Tak
jest w przypadku autostrady wzdłuż której leży wiele wiosek, ale to
tylko jeden szczególny przypadek grafu.

Chyba czegoś nie rozumiem.

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/