Rozwiązuję problem „mieszania” zestawów nakładających się obrazów. Te zestawy mogą być reprezentowane przez niekierowany ważony wykres, taki jak ten:
Każdy węzeł reprezentuje obraz. Nakładające się obrazy są połączone krawędzią. Ciężar krawędzi reprezentuje wielkość obszaru nakładania się ( wcześniejsze połączenie większego nakładania prowadzi do lepszej ogólnej jakości ).
Algorytm ogólnie usuwa krawędzie. Może to zrobić sekwencyjnie lub równolegle. Jednak gdy nastąpi mieszanie, węzły łączą się i zmienia się struktura wykresu. Tak więc równoległość jest możliwa tylko na połączonych komponentach, które same się nie nakładają!
Takimi nie nakładającymi się elementami są DB i FEG. Możemy uruchomić algorytm mieszania na tych komponentach bezpiecznie równolegle. Wynikiem jest następujący wykres (połączone węzły są wyświetlane na zielono):
Teraz nie jest możliwa dalsza równoległość, ponieważ dowolne dwa połączone komponenty zachodzą na siebie (mają krawędź bezpośrednio między nimi).
Równoległa wersja algorytmu wyglądałaby następująco:
1. Find connected components (no two are connected directly) and create task for each.
2. Run the tasks in parallel.
3. Update graph.
4. Until single node remains, continue with 1.
Trudna część to pierwszy krok: jak znaleźć najlepszy zestaw połączonych komponentów?
Jednym ze sposobów byłby chciwy algorytm, który po prostu znajduje największą liczbę składników przy danej iteracji. Chciwy algorytm zmaksymalizuje równoległość na początku, ale kosztem wielu iteracji później.
Optymalnym rozwiązaniem może być dostarczenie dużej ilości połączonych komponentów w każdej iteracji, aby zmaksymalizować równoległość i zminimalizować liczbę iteracji jednocześnie (więc w optymalizacji są dwie zmienne).
Nie mogę wymyślić żadnego innego algorytmu optymalizacji niż cofanie, tzn. Przeszukiwać wszystkie możliwe ewolucje i wybrać ten z maksymalną równoległością.
Wagi krawędzi można zignorować, ale ulepszona wersja algorytmu może wziąć to pod uwagę, ponieważ większe obszary wymagają więcej czasu na zmieszanie (np. Obszar o rozmiarze 200 zajmie około dwa razy więcej czasu niż dwa obszary o rozmiarze 100). Uwzględnienie wag może prowadzić do lepszej strategii wyboru komponentów (szybszy całkowity czas działania algorytmu).
Czy masz jakieś wskazówki dotyczące takiego algorytmu optymalizacji, który znajduje najlepszą strategię wyboru części wykresu, aby uzyskać maksymalną równoległość i minimalną liczbę iteracji?