Mariusz Marszałkowski pisze:
> arturbac <artur_no_spam@no_spam.ebasoft.com.pl> napisał(a):
>
>> Piotr Domownik pisze:
>>> Poszukuje osoby, ktora podejmie sie napisania modulu wyszukujacego
>>> najkrotsza droge w grafie nieskierowanym. Problemem jest wyjatkowo duza
>>> ilosc wezlow. Szczegoly na priv po przeslaniu wstepnych informacji.
>> Proces wytworzenia jest kosztowny ale za to mozesz pozniej wyznaczac
>> najkrotsza sciezke nawet na ARM i 32MB majac na karcie pare GB danych.
>
> 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?

Homeomorfizmu tlumaczyc nie ma sensu to jest opisane nawet na wiki.
Co do implementacji oczywiscie to inna kwestia:
Np prosty przypadek 2 grafy homeomorficzne.
Graf docelowy zawierajacy mlrd wezlow i krawedzi.
Analizujesz dane pod katem znaleznienia waskich gardeł tj cechy ktora
pozwala w prosty sposob uproscic owy graf do prostszej postaci w
jednoznaczny sposób.
Np jak opisalem na przykladzie drog, mozna podzielic krawedzie na te
tworzace miasta i te laczace je.
Te łaczące je wraz z wezlami redukujesz do jednego wezla w grafie
zgrubym reszte siatki traktujesz( wyznaczasz drogi) jako poalczenia
miedzy tymi wezlami maist jako pojedyncze krawdzie.
Jesli zachowany bedzie homeomorfizm tj jednoznaczny sposob konwersji
krawedzie poza maistami ktore przypadaja na krawedz w grafie zgurbym to
po wyznaczeniu trasy w grafie zgrubnym majac krawedzie tego grafu wprost
mozna ustalic ktore krawedzie z grafu dokladnego nalezy zaladowac.
Co ciekawe jesli owy homeomorfizm jest dokladny i spojny do wyznaczanie
drogi dokladnej na subsecie krawedzi juz mozna przeprowadzac kawalkami.

Sposobow na homeomorficzne przedstawienie moze byc wiele np
punkty granic gmin, powiatow na wezly grafu zgrubnego.

Proces wytworzenia grafow homeomorficznych jest kosztowny i wymaga
niezlej mocy i pamieci ale pozniej wynik tego prztworzenia mozna
wielokrotnie uzywac do wyznaczania drog w tani i szybki sposob na
niskiej mocy obliczeniowej urzadzeniach z mala iloscia ram.