jakiego algorytmu mam szukać

Odpowiedz Nowy wątek
2019-07-17 22:32
0

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

Pozostało 580 znaków

2019-07-17 22:39
2

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


Pozostało 580 znaków

2019-07-17 22:41
0

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

Pozostało 580 znaków

2019-07-17 22:56
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.

Pozostało 580 znaków

2019-07-17 23:06
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

Pozostało 580 znaków

2019-07-17 23:07
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

Pozostało 580 znaków

2019-07-17 23:09
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)

Nie no chyba nie tak prosto, bo te 1 to był tylko przykład, a realnie wartości mogą odnosić sie do większej liczby elementów z tego co rozumiem. Więc nie chcesz skojarzenia tylko chcesz wybrać podzbiór krawędzi taki, zeby stopnie wierzchołków po prawej stronie były jak najbardziej wyrównane. - Shalom 2019-07-18 00:30
Hmm, chyba masz rację. - Afish 2019-07-18 00:46

Pozostało 580 znaków

2019-08-25 22:14
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?

Pozostało 580 znaków

2019-08-26 01:10
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.

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-08-26 01:10
tak, napisałam już że mogę se wyobrazić taki przypadek dla którego moje rozwiązanie się w ogóle nie sprawdzi :( - Miang 2019-08-26 07:43

Pozostało 580 znaków

2019-08-27 17:32
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.

edytowany 1x, ostatnio: Kalrais, 2019-08-27 18:58
w moim rozwiązaniu za poziom do którego należy dążyć brałam x/5. gdzie x to ilość elementów ze zbiorami wartości o <=liczności,zaokrąglony w dół, Bo inaczej pętla nieskończona może wyjść ;) - Miang 2019-08-27 18:51
@Miang: Nie rozumiem czym jest x u Ciebie, ale wydaję mi się, że różnica MAX - MIN jest znacznie wygodniejsza. W Rozwiązaniu zapomniałem o jednym przypadku - patrz edit. - Kalrais 2019-08-27 19:00
a jak MAX-MIN =1 ? - Miang 2019-08-27 19:03
To ile ta różnica wynosi nie ma znaczenia. Ważne jest to czy zmniejszyła się w ostatniej iteracji, bo to oznacza, że poprawiliśmy rozmieszczenie klocków i być może dalej możemy je poprawić, no chyba że różnica się wyzerowała. Takie podejście nazywa się metodą kolejnych przybliżeń, albo w bardziej ogólnym przypadku iteracją do punktu stałego. - Kalrais 2019-08-27 19:08
sory , nie zauważyłam warunku stopu - Miang 2019-08-27 21:37

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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