Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytm sekwencyjny pakowania

Sortuj według:

Ogranicz wyniki do:

Analiza probabilistyczna wybranych sekwencyjnych algorytmów pakowania

Horzelski W.

Zeszyty Naukowe Wyższej Szkoły Informatyki

2008

Vol. 7, Nr 1

39-48

Streszczenie – Zadanie pakowania w klasycznym ujęciu polega na rozmieszczeniu listy ładunków L={a1,a2,…,an} o rozmiarach nieprzekraczających 1 w minimalnej ilości pojemników o rozmiarze jednostkowym, wymaga się przy tym, aby żaden z pojemników nie był przeładowany. Wśród metod rozwiązania takiego zadania jest też klasa algorytmów sekwencyjnych. Od algorytmu sekwencyjnego wymaga się dodatkowo aby zadania umieszczane w pojemniku tworzyły sekwencję: Dla każdego i należy do Jn for all j,k,l należy do Di j należy do A(Li) (s)iloczyn logiczny l należy do A(Li) (s) iloczyn logiczny j mniejsze niż k mniejsze niż l implikacja k należy do A(Li)(s), dla s element of J IA(Li)I W niniejszej pracy przedstawiono przykład algorytmu sekwencyjnego S1k oraz przeprowadzono pełną analizę jego zachowania. Dowiedziono twierdzenia określającego wartość współczynnika sprawności algorytmu (RS1kwiększe lub równe 0.5) dla najgorszego przypadku. Analiza probabilistyczna przeprowadzona została dla nieskończonego ciągu niezależnych zmiennych losowych o jednakowym rozkładzie L={E1,E2,......}. W pracy pokazano ograniczenie dla asymptotycznego współczynnika nadwyżki algorytmu S1k (R nieskończoność S1k,U(0,1) większe niż 0.7288).

The bin-packing problem in the classical approach is to arrange the list of tasks L={a1,a2,…,an} of a size not exceeding 1 in the minimum number of bins of size 1, however, that none of the bins was overloaded. Among the ways to do such a task is a class of sequential algorithms. From sequential algorithm is required in addition to pack the tasks in such a way that tasks placed in each container (bin) consisted of a sequence: For all i element of Jn for all j,k,l element of Di j element of A(Li) (s)logical and l element of A(Li) (s) logical and j less than k less than l implication k element of A(Li)(s), dla s element of J IA(Li)I In this paper is an example of sequential algorithm called S1k and carried out a full analysis of its behavior. It demonstrate the value of lower bound for efficiency factor of the algorithm (R S1k greater-than or equal to 0.5). Probability analysis was carried out for the infinite sequence of independent random variables of equal distribution L={E1,E2,......}. This paper also show a bound of asymptotic waste ratio of S1k (R infinity S1k,U(0,1) greater than 0.7288).