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