Generacja grafów regularnych o maksymalnej liczbie drzew rozpinających.

Błażej Sawionek, Jacek Wojciechowski, Jarosław Arabas

Geneza problemu

Gdy mamy p punktow (np. miast) i mamy za zadanie zapewnić pomiedzy nimi łączność za pomoca 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ą łączność było największe. Przy pewnych dodatkowych założeniach problem ten sprowadza się właśnie do maksymalizacji liczby drzew w grafie.

Ograniczenie zakresu badań

W poprzednich wystąpieniach prezentowałem rozwiązania zawężone do klasy grafów cyklicznych. Później rozszerzyłem ją na grafy regularne, ale udało mi się zbadać tylko grafy skierowane. W tym wystąpieniu przedstawię rozwiązanie dla grafów regularnych zarówno skierowanych jak i nieskierowanych.

Metody rozwiązania.

Dokładne

Przegląd wszystkich możliwych rozwiązań jest nierealny - problem jest klasy NP i juz dla 8 węzłów sieci nie daje sie w sensownym czasie przejrzeć wszystkich możliwosci.
Rozwiązania analityczne istnieja dla bardzo szczególnych przypadków.

Przybliżone

Zostaną zaprezentowane dwie metody rozwiązania zagadnienia: ewolucyjna i 2-optymalna. Dla metody ewolucyjnej zostały opracowane dedykowane operatory genetyczne: krzyżowania i mutacji, ten ostatni wzorowany jest na pojedynczym kroku metody 2-optymalnej.
 

Cele i przebieg eksperymentu

Określenie powtarzalności wyników dla algorytmu ewolucyjnego

100 uruchomień dla jednego zestawu p/d dla różnych populacji startowych.

Zbadanie możliwości znalezienia przez algorytm ewolucyjny optimum globalnego

Badanie dla takich wartosci p i d dla ktorych jest znany wynik

Porównanie metod

Badania dla wybranych wartosci p i d dla grafów rzadkich, gęstych i średnich.

Wnioski

Bez zastosowania heurystyki metoda ewolucyjna jako globalna jest wyraźnie lepsza.

Przy zastosowaniu wiedzy a priori obydwie metody staja się porównywalne, przy czym dla grafów nieskierowanych rzadkich nadal lepsza pozostaje metoda ewolucyjna, ona również ze względu na w przybliżeniu liniową obserwowana złożoność numeryczną będzie musiała być stosowana do problemów o większym rozmiarze. Poza przypadkiem grafów nieskierowanych rzadkich najlepszy osiągnięty rezultat nie przekracza wyniku heurystycznego o więcej niż 10%, więc w pewnych przypadkach można nawet zrezygnować z optymalizacji.

Harmonogram