Witam,
mam następujący problem do rozwiązania - mam graf gdzie każdy z elementów nacechowany jest liczbą naturalną. Suma wszystkich liczb w grafie wynosi S.
Potrzebuje podzielić ten graf na X mniejszych podgrafów tak aby suma liczb każdego z nich była jak najbliższa S/X.
W podgrafach nie mogą być zmienione połączenie tzn jeżeli węzeł A jest połączony z B, a B z C to mogę wydzielić podgraf zawierający A, B, C ale nie mogę A,C.
Byłbym wdzięczny za sugestię jakiego algorytmu powinienem użyć.
Nie podałeś funkcji celu, właściwie podałeś ale w postaci rozmytej. Np z opisu nie wynika jaki podział jest lepszy 5 5 5 4 4 czy 7 4 4 4 4.
Witam dziękuję za podpowiedź - jeżeli chodzi o funkcję celu to żaden zbiór nie powinien mieć sumy większej niż S/X * 120% ani mniejszej niż S/X * 80%, w obrębie tych kryteriów zadowala mnie każde rozpisanie (problem jest bardziej praktyczny niż teoretyczny).
Nie oczekuję kompletnego rozwiązania tylko jakiegoś odesłania do linków / literatury.
Pozdrawiam
Oczekiwałem raczej rozwinięcia tematu. Nadal masz sporo nie zdefiniowanych rzeczy, np:
Cześć, dzięki za odpowiedź
X jest wartością zadaną
wartość w grafie jest cechą wierzchołka - krawędzie nie posiadają cech i wszystkie są równoważne (tzn. liczy się tylko jest krawędź/połączenie albo go nie ma).
Tzn. zakładając że chcemy otrzymać zbiór o sumie bliskiej 8 lepiej wybrać 5 pozycji grafu 3-2-2-2-1 (suma 10 - przeciwległe liczby są od siebie odległe o 4 krawędzie), niż np. 3-8 (suma 11, blisko siebie). Odległość nie ma dla mnie znaczenia.
Wydaje mi się że nić lepszego nie wymyślisz niż sprawdzanie wszystkich wariantów po kolei, owszem można dodać trochę heurystyki zmniejszającej ilość kroków (S/X120%, S/X80%) ale nadal wg mojej opinii jest to problem NP-trudny.
To co chcesz zrobić to chyba algorytm aproksymacyjny: http://pl.wikipedia.org/wiki/Algorytm_aproksymacyjny Poszukaj w Google tego hasła, być może trafisz na coś pomocnego.
Możesz zastosować algorytm genetyczny o strukturze chromosomu takiej:
{nr-węzła}|{nr-podzbioru}
(powtórzone k razy dla wszystkich węzłów)
Funkcja celu (do maksymalizacji) to np:
f() = 1 / (1 + (suma-liczb-podzbioru - S/X)^2) + 1 / (1 + liczba-połączeń-poza-zbiór)
liczba-połączeń-poza-zbiór to liczba węzłów które nie łączą się z żadnym węzłem z tego samego podzbioru
witam, przepraszam że odświeżam wątek, jaką polecanie książkę do algorytmów kombinatorycznych??
witam, przepraszam że odświeżam wątek, jaką polecanie książkę do algorytmów kombinatorycznych??
"Kombinatorykę dla programistów" Witolda Lipskiego.
a jakieś notatki z wykładów w formie pdf??