P3 || Cmax

[veelck 0]

algorytm nastepujacy - tworze tablice 3-wymiarowa, gdzie jeden wymiar to ilosc zadan, a kolejne dwa to dlugosc zadan na 1 i na 2. procesorze. Pytanie - jak wybrac odpowiednio dlugosc zadan na 1. i 2. procku, zeby wynik wyszedl optymalny. Na pocztaku wzialem 1/3 sumy wszystkich zadan zaokraglona do gory - wygladalo ze dziala, do czasu jak przyszedl zestaw 1 7 7 1 1 i wyszlo szeregowanie:

p1 = 1 1 1

p2 = 0

p3 = 7 7

bo zadne zadanie 7 sie nie zmiescilo (1/3 sumy to 6)

to zmienilem na taki sposob, ze biore pod uwage jeszcze element maksymalny przy ustawianiu tablicy, czyli rozmiar jest 1/3 sumy zaokr. w gore albo wartosc maksymalna - no i wszystko byloby pieknie, poprzednia instancja rozwiazana prawidlowo, ale jak przyszla instancja postaci 1 4 5 6 8, to rozwiazanie bylo:

p1 = 5 1

p2 = 8

p3 = 6 4

bo 1/3 sumy wyniosla 8, tak jak dlugosc najdluzszego zadania, a optymalne rozwiazanie to np.

p1 = 5 4

p2 = 6 1

p3 = 8

 

czy ktos wie/ma pomysl jak to rozwiklac ? Prosze o w miare szybka odpowiedz...

tia

 

pozdrawiam

veelck

[januzi 24]

to jest tak, ze te 3 maszyny sa identyczne i zadania moga byc wykonywane dowolnie na kazdej z nich ?

 

jak tak, to problem jest takiego typu: podzielic zbior liczb na 3 podzbiory tak, zeby suma elementow w kazdym zbiorze byla zblizona do siebie

 

rozwiazania zachlanne beda w tym przypadku zwracac nieprawidlowe rozwiazanie; lepsze bedzie tworzenie drzewa mozliwych rozwiazan; albo wyznaczasz permutacje wstepna, a nastepnie sprawdzasz ktore z zadan mozna zamienic maszynami, zeby czas zakonczenia sie zmniejszyl

[veelck 0]

ok, kwestia wyboru algorytmu troche za pozno - mam juz za duzo kodu, to pierwsze, drugie - mialo byc wlasnie przez programowanie dynamiczne i na tablicach(wektorach) 'trojwymiarowych'

 

Ale nic to - problem mniej/wiecej rozwiazany, prowadzacy stwierdzil, ze wazne zeby dla wiekszosci przypadkow chodzilo, bo zawsze mozna jakis wredny przyklad dac (tzn. powiedzial to po tym, jak mu pokazalem ze algorytm ktory prezentuje wywala sie juz po wprowadzeniu np. pieciu zadan wszystkich o wartosci 3 )

 

Wiem ze moglem to zrobic np. na drzewie i przechodzi je pozniej czyms w stylu Branch and Bound, ale mialo byc prog. dynamiczne, wiec... A rozwiazanie musi byc optymalne, wiec generowanie przyblizonych permutacji tez niewiele mi daje (mozna zapuscic jakis algorytm LSA, LPT albo cos w tym stylu, ale one nie daja optimum...)