jakiego algorytmu mam szukać

1

Może ktoś się orientuje pod jakim hasłem szukać rozwiązania następującego problemu
jest n elementów które mogą przyjąć wartość od 1 o 5, przy czym każdy z nich ma określony podzbiór dozwolonych wartości np {1,3} lub {2,4}
trzeba tak przydzielić wartości do elementów żeby ilości elementów dla każdej z wartości były wyrównane

2

Wyrównane, czy może równe? Podaj jakieś przykłady, co na wejściu i wyjściu.

0

no jak n=6 to całkiem równe nie będą, raczej chodzi o możliwie jak najbardziej zbliżone

0

Tez nie ogarniam polecenia. Co oznacza to ostatnie zdanie. Podaj przykład dla jakiegoś malego n i możliwe wartosci które moze przyjac i jaki powinien byc wynik i dlaczego.

0

Pewnie zadanie jest proste, tylko dziwnie wyjaśnione. Z tego co rozumiem z Twojej wersji, to byłby to problem sumy podzbioru, który należy do klasy problemów NP-trudnych więc pewnie nie o to chodzi.
https://en.wikipedia.org/wiki/Subset_sum_problem

0

n1 {1,2}
n2 {2,3}
n3 {1,4}
n4 {1}
n5 {3,5}

przypisujemy n4 wartość 1 bo nie ma wyboru
n1=2 , n3=4 bo skoro mamy już element z wartością 1 to też nie ma wyboru
n2=3
n5=5
i dla każdej z wartości jest taka sama ilość elementów czyli 1

0

Robisz graf dwudzielny z n* po lewej stronie i wartościami po prawej, a potem szukasz skojarzenia
https://en.wikipedia.org/wiki/Matching_(graph_theory)

0

zrobiłam tak jak podałam w przykładzie na dużo większą skale, najpierw przydzielam elementy które mają jednoelementowy zbiór możliwych wartości, potem dwuelementowe dbając o możliwie równe rozłożenie żeby dla poszczególnych wartości była podobna liczna elementów,(biorąc pod uwagę te przydzielone w pierwszym kroku), potem to samo dla coraz liczniejszych zbiorów. Wychodzi nawet ładnie dla danych które mam, ale oczywiście potrafię se wyobrazić zbiór danych gdzie ta metoda będzie najgorsza a nie najlepsza. Nadal się zastanawiam jaki to problem, znaczy jaką ma oficjalną nazwę. A także jaką nazwę ma opisany przeze mnie algorytm?

0

@Miang algorytm opisany wyżej to zwykłe podejście zachłanne, tzn wybierasz najlepszy krok w danej chwili. Nie wygląda to na rozwiązanie optymalne, bo problem nie ma własności optymalnej podstruktury. Jeśli wiemy jak optymalnie podzielić wartości dla zbiorów o liczności mniejsze niż k, to czy możemy łatwo wygenerować rozwiązanie dla problemu rozszerzonego o kolejny zbiór? W twoim pomyśle przydzielisz wartość, która aktualnie ma najmniejszą liczność wystąpień w elementach, ale co jeśli jest takich więcej niż jedna?

  1. Możesz przydzielić losowo, ale wtedy możesz "wybrać źle" i uzyskać rozwiązanie suboptymalne. Przykład: zaczynamy od {1,2}, {3,4}. Wydawać by się mogło że możemy wybrać losowo, bo każdy przydział daje równie dobre rozwiązanie. Ale teraz jeśli mamy dalej zbiór {1,2,3} to nagle nie jest to już prawdą, bo optymalne rozwiązanie wymaga e2=4 i e3=3 (e1 dowolnie 1 lub 2).
  2. Możesz analizować to na bazie rekurencji z powrotami, testując który z tych równorzędnych wyborów jest lepszy "dalej", ale wtedy automatycznie mamy O(2^n) / problem NP, bo możemy tak analizować przez wiele wiele kroków.
0

Powiedzmy, że masz n różnokolorowych klocków (w sensie 1 klocek może mieć wiele kolorów). Klocki są w kolorach ze zbioru {1,...,5} i każdy kolor ma swój własny kubełek. Chcesz rozmieścić klocki jak najrówniej w kubełkach, ale w kubełku mogą być tylko klocki w kolorze kubełka. Innymi słowy chcesz zminimalizować różnicę pomiędzy MAX - MIN, gdzie MAX - to kubełek z największą liczbą klocków, a MIN - to kubełek z najmniejszą ilością. Algorytm wygląda następująco:

  1. wygeneruj jakieś poprawne, ale nie minimalne rozwiązanie (np. losując kubełek)
  2. Powtarzaj dopóki MAX - MIN się zmienia:
    2.1. Przeglądaj kubełki od MAX do MIN jeśli rozpatrywany kubełek ma klocki w kolorze MIN to przenieś je do MIN (ale nie więcej niż MAX-MIN)
    2.2. Jeśli MIN przestał być minimalny lub MAX maksymalny to uaktualnij wskaźniki i zacznij od początku.

W każdym przebiegu zmniejszamy cel, więc pętla wykona się co najwyżej n razy. Przebieg pętli można zaimplementować różnie ale nie powinien chyba zająć więcej niż O(n) (plus sortowanie kubełków, ale to jest stałe jak rozumiem), więc cały algorytm działałby w O(n^2). Pewnie da się szybciej.

Tak jak teraz o tym myślę to formalnie dałoby się to chyba przedstawić jako kolorowanie grafu z list z jak najmniejszą ilością konfliktów gdzie w grafie jest krawędź jeśli listy kolorów się niepusto przecinają.

Edit: Zapomniałem o jednym przypadku. Kiedy nie ma żadnych klocków do dorzucenia do MIN-a, możemy próbować wyrzucić coś z MAX-a. Robimy to analogicznie jak w pkt. 2.1. Złożoność się nie zmienia.

1 użytkowników online, w tym zalogowanych: 0, gości: 1