Mariusz Marszałkowski pisze:
> 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.

Masz ścisłe pojęcie że dorga to droga, a rozluznij wyobraznie

Weź takie

Wszystkie drogi(krawędzie) mają atrybut kraju,wojewodztwa
Niech graf A bedzie np takim przejsciem ze wezly wenwatrz wojewodztwa
grafu B staja sie jednym wezelem w calym wojewodztwie grafu A, wezly na
granicy ktore lacza drogi wojewodzkie A staja sie wezlami granicznymi B
reszta wezlow A z granic staje sie albo tymi wewnatrz B albo pomijasz
cokolwiek (kwestia wyobrazni). Teraz zaowaz ze musisz ustalic jakies
kryterium dla wag miedzy wezlami granic a wezlami srodkowymi (tj
kluczowe kwestia kalibracji i wyobrazni)

Jesli w tym grafie zgrobym ktory zalozmy reprezentuje cala europe
przeprowadzisz wyznaczaczanie drogi to zuyskasz liste wojewodztw przez
ktore musi biec droga oraz liste wezlow granicznych miedzy wojewodzkimi
przez ktore ona biegnie.
Wystarczy teraz ze dla kazdego wojewodztwa przeprowadzisz wyznaczanie
drogi od granicy do granicy na zadanych punktach.

To jest duze uproszczenie idei ale dosc dobrze oddaje cel.
Wynik takiego przeprowadzania wyznaczania najkrótszej sciezki bedzie
rozwiazaniem suboptymalnym ale jednoczesnie tak bliskim opimum jak dobry
bedie homeomorfizm i ustalone wagi grafu zgrubnego.

Mozna robic inne przejscia np aby uzyskiwac liste krajow podrozy albo
znaczacych drog itd