Temat badań

Od momentu rozpoczęcia pracy magisterskiej zajmuję się poszukiwaniem grafów o maksymalnej liczbie drzew, stopniowo rozszerzając zakres analizowanych grafów: od grafów cyklicznych nieskierowanych (praca magisterska), poprzez cykliczne skierowane (konferencja ECCTD - Budapeszt 1997), regularne skierowane (konferencja KAEiOG - Rytro 1997). Właśnie zakończoną pracę nad grafami regularnymi nieskierowanymi chciałbym zaprezentować jesienią bieżącego roku. W tej chwili zmieniam nieco model problemu - przechodzę do grafów ważonych.

Skąd się takie zagadnienie wzięło?

Otóż w skrócie: gdy mamy p punktow (np. miast) i mamy za zadanie zapewnić pomiędzy nimi łączność za pomocą pewnych połączeń (np. kabli telefonicznych), które to połączenia są po pierwsze kosztowne, a po drugie zawodne to jeżeli przyjmiemy, że mamy pieniadze na q kabli chcemy wiedzieć między którymi punktami te kable położyć, żeby prawdopodobieństwo, że każde dwa punkty będą miały ze sobą łącznosć było największe. Przy pewnych dodatkowych założeniach (omawiam je poniżej) problem ten sprowadza się właśnie do maksymalizacji liczby drzew w grafie.

Dlaczego drzewa?

Nawet gdy awarie wszystkich połączeń są niezależne i zachodzą z jednakowym prawdopodobieństwem sytuacja nie jest prosta. Odpowiedź na pytanie który z dwóch grafów jest lepszy może zależeć od prawdopodobieństwa awarii. Problem uważa się za rozwiązany dla krawędzi niezawodnych (prawdopodobieństwo awarii bliskie 0), natomiast dla krawędzi zawodnych rozwiązaniem będzie właśnie graf o maksymalnej liczbie drzew rozpinających.

Metodyka badań

Grafy cykliczne analizowałem metodą pełnego przeglądu (wyszukiwania wyczerpującego). Dla grafów poniżej pewnej wielkości dawało się to zrobić (p<30). Mam w planach opracowanie metody, która znacznie rozszerzy ten zakres.
Później badania były kontynuowane (bez mojego udziału) za pomocą strategii ewolucyjnej. Po czym zająłem się porównaniem tych wyników z metodą 2-optymalną.
Grafy regularne badałem również za pomocą tych dwóch metod.

Niejednakowe prawdopodobieństwa

Obecnie zmieniłem model - założyłem, że prawdopodobieństwa awarii nie muszą być jednakowe, ale są przypisane do konkretnych par węzłów. Uzasadnienie tego modelu może być na przykład takie: sieć należy zrealizować w terenie, w którym wystepują czynniki uszkadzające łącza. Wiemy w którym miejscu z jaką intensywnością działają, więc możemy powiedzieć, że jeżeli zostanie położony kabel pomiędzy punktem A i B to prawdopodobieństwo jego uszkodzenia będzie x. Przyjąłem, że miarą niezawodności takiej sieci będzie suma prawdopodobieństw przetrwania wszystkich drzew. Do rozwiązania tego zagadnienia stosuję już tylko metodę ewolucyjną - z dobrym skutkiem.
W ramach seminarium PATIA: Zastosowania kombinatoryki i optymalizacja dyskretna wygłosiłem w dniu 8 kwietnia 1998 seminarium pt. Generacja grafów regularnych o maksymalnej liczbie drzew rozpinających.
W wystąpieniu tym krótko omówiłem postawiony problem, oraz przedstawiłem próby jego rozwiązania za pomocą metod przybliżonych: metody 2-optymalnej oraz strategii ewolucyjnej. Pokazałem, że strategia ewolucyjna jest odpowiednim narzędziem do rozwiązywania tego problemu, opisałem zastosowane operatory genetyczne oraz wskazałem planowany kierunek dalszych badań. Tu jest streszczenie mojego wystąpienia.
UWAGA:
Ta strona jest eksperymentem - wszystko co do tej pory publikowałem w internecie miało służyc głównie mi samemu (patrz: Kilka wyjasnień). Dlatego bardzo proszę w wszelkie uwagi na temat tej nietypowej dla mnie strony. Rozumiem, że jest ona bardzo uboga, ale zanim się ciężko nad nią napracuję chciałbym wiedzieć, że ktoklwiek na nią zagląda (i ew. co spodziewa się znaleźć).

Powrót do strony głównej