> 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.

do góry

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/

do góry

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

do góry

> Masz ścisłe pojęcie że dorga to droga, a rozluznij wyobraznie
No spróbujmy rozluźnić ją :)

>
> 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).

Ok, a co zrobić jeśli graf nie przypomina mapy? Np. gdy graf nie ma
określonego
położenia węzłów, określone jest tylko które węzły są połączone a
które nie?
Długość połączeń może być dodatnią wartością stałą albo zmienną o
jakimś rozkładzie?

> 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.
Tak, uzyskam, ale czy mniejszym kosztem? Stoję w punkcie źródłowym.
Sprawdzam
drogę do najbliższych państw. Skąd mogę wiedzieć w jakim państwie
leży
punkt docelowy? Nie wiem tego, bo wierzchołki w grafie nie mają
określonych
współrzędnych. Więc po dotarciu w zgrubnym grafie do węzła
reprezentującego
państwo, muszę odszukać listę wszystkich punktów w tym państwie i całą
przejrzeć? Czy jest jakiś szybszy sposób?

> 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

Zgadzam się dla grafu który reprezentuje punkty w przestrzeni N
wymiarowej
W grafie z podaną listą połączeń i wagami połączeń nadal nie rozumiem
jakby
to mogło pomóc. Jedyny zysk jaki widzę, to brak nastawiania głowicy
podczas
sekwencyjnego odczytywania listy najbliższych sąsiadów.

Pozdrawiam

do góry

Wez ze sklepu jakąkolwiek nawigację samochodową na PocketPC, WCE wyznacz
tras z lizbony do helsinek, 30 - 90s w zal. od produktu.
Orientacyjna ilośc segmentów(krawędzi) w europie to 20 pare mln.
Ilośc ram to 32 albo 64 a o szybkości procka nie wspomne.
Opisanym sposobem ( ale z innymi homeomorfizmami ) wyznacza sie trasy w
oparciu o grafy zgrubne pozwalajace ustalic minimalny zestaw krawedzi do
poprowadzenia trasy dokladnej.

do góry

On 8 Paź, 09:14, arturbac <artur_no_spam@no_spam.ebasoft.com.pl>
wrote:
> Wez ze sklepu jakąkolwiek nawigację samochodową na PocketPC, WCE wyznacz
> tras z lizbony do helsinek, 30 - 90s w zal. od produktu.
> Orientacyjna ilośc segmentów(krawędzi) w europie to 20 pare mln.
> Ilośc ram to 32 albo 64 a o szybkości procka nie wspomne.

Zgadzam się i rozumiem że to nie stanowi problemu. Sam bym umiał
to wymyślić i zaimplementować. Ułatwienie stanowią współrzędne
węzłów na mapie 2D bądź 3D. Jeśli ktoś szuka przykładowej
Warszawy na mapie, to po współrzędnych Warszawy i współrzędnych
Polski w grafie zgrubnym, od razu wiadomo że Warszawa nie
leży w Afryce. Ale to jest przypadek szczególnego grafu.

Wyobraź sobie inny graf. Jest kula o promieniu jednostkowym.
Wewnątrz tej kuli na losowych współrzędnych są rozmieszczone
miliony węzłów. Pomiędzy losowymi węzłami przebiegają
połączenia o losowej długości z przedziału od 10 do 50 jednostek,
czyli długość każdego połączenia przekracza średnicę kuli.
Np wszystkie połączenia stanowią bardzo kręte tunele.

Jak taki graf zaindeksować? Jak do niego stworzyć graf zgrubny?

> Opisanym sposobem ( ale z innymi homeomorfizmami ) wyznacza sie trasy w
> oparciu o grafy zgrubne pozwalajace ustalic minimalny zestaw krawedzi do
> poprowadzenia trasy dokladnej.
No właśnie, nie wiem jak w tym grafie który przytoczyłem ustalić
minimalny zestaw krawędzi zawierający rozwiązanie dokładne?

Pozdrawiam

do góry

Mariusz Marszałkowski pisze:
> On 8 Paź, 09:14, arturbac <artur_no_spam@no_spam.ebasoft.com.pl>
> wrote:
>> Wez ze sklepu jakąkolwiek nawigację samochodową na PocketPC, WCE wyznacz
>> tras z lizbony do helsinek, 30 - 90s w zal. od produktu.
>> Orientacyjna ilośc segmentów(krawędzi) w europie to 20 pare mln.
>> Ilośc ram to 32 albo 64 a o szybkości procka nie wspomne.
>
> Zgadzam się i rozumiem że to nie stanowi problemu. Sam bym umiał
> to wymyślić i zaimplementować. Ułatwienie stanowią współrzędne
> węzłów na mapie 2D bądź 3D. Jeśli ktoś szuka przykładowej
> Warszawy na mapie, to po współrzędnych Warszawy i współrzędnych
> Polski w grafie zgrubnym, od razu wiadomo że Warszawa nie
> leży w Afryce. Ale to jest przypadek szczególnego grafu.

Jesli zastosujesz ta logike szukania tylko w danym kierunku to nie
sprawdzi sie na Europie. Przyklad Gdynia -> Malme i prom do karskrony
idący w przeciwnym kierunku z Gdyni i wiele tym podobnych polaczen.

>
> Wyobraź sobie inny graf. Jest kula o promieniu jednostkowym.
> Wewnątrz tej kuli na losowych współrzędnych są rozmieszczone
> miliony węzłów. Pomiędzy losowymi węzłami przebiegają
> połączenia o losowej długości z przedziału od 10 do 50 jednostek,
> czyli długość każdego połączenia przekracza średnicę kuli.
> Np wszystkie połączenia stanowią bardzo kręte tunele.
>
> Jak taki graf zaindeksować? Jak do niego stworzyć graf zgrubny?

Cala istota homeomorfizmow polega na sepcyfice danych.
Drogi -> Miasta, Powiaty,Gminy, Granice, Przejscia Graniczne, typy i
kategorie drog, ich przepustowosci etc
Sieci komputerowe -> przepustowosci sieci, typy sieci, opoznienia,
fizyczny nosnik, funkcje wezlow ( routery , bramy )
Sieci energetyczne -> Napiecia, natezenia -> rola sieci

itd.

Jesli cos jest kompletnym chaosem to nie ma na czym ustalic homeomorfizmu

do góry

On 9 Paź, 12:39, arturbac <artur_no_spam@no_spam.ebasoft.com.pl>
wrote:

> Jesli cos jest kompletnym chaosem to nie ma na czym ustalic homeomorfizmu
Tak też sądziłem.
Pozdrawiam

do góry