wtorek, 25 marca 2014

Ogólny problem plecakowy

Problem plecakowy

Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg?

Dyskretny problem plecakowy (ang. discrete knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart $c_{j}$ oraz waży $w_{j}$ . Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Podobny problem pojawia się często w kombinatoryce, teorii złożoności obliczeniowej, kryptografii oraz matematyce stosowanej.

Decyzyjna wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej C może być osiągnięta bez przekraczania wagi W?"

Definicja

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności $B$ oraz zbiór $N$ elementów $\{x_1, x_j, ..., x_N\}$ , przy czym każdy element ma określoną wartość $c_{j}$ oraz wielkość $w_{j}$ .

Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.$

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.$

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).

W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.

W przypadku, gdy problem jest rozważany przy założeniach, że

jest problemem decyzyjnym
jest dyskretny
dla każdego elementu waga równa się wartości $w_j=c_j$

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie W? Zagadnienie to nazywane jest problemem sumy podzbioru.

Problem plecakowy może być rozwiązany przy użyciu programowania dynamicznego, ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są problemami NP trudnymi, co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach kryptografii asymetrycznej takich jak Merkle-Hellman. Algorytmy takie używały grup, nie liczb całkowitych. Merkle-Hellman oraz kilka podobnych algorytmów zostało w późniejszym czasie złamanych, ponieważ szczególny problem sumy podzbioru użyty w tych algorytmach były rozwiązywalne w czasie wielomianowym^.

Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem NP zupełnym i jest jednym z 21 NP zupełnych problemów Karpa.

Realizacje algorytmu

Przegląd zupełny

Przegląd zupełny (bruteforce, metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku złożoność obliczeniowa algorytmu wyniesie $\Theta(2^n)$ , co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi $\Theta(2^n)$ ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona (dwumian Newtona) podstawiając za a i b jedynki.

piątek, 21 marca 2014

Znajdowanie przybliżonej wartości miejsca zerowego

Miejscem zerowym funkcji nazywamy taki argument x,
dla którego funkcja przyjmuje wartość 0.

Metoda połowienia - bisekcji

Mamy daną funkcję f(x) oraz przedział <a,b>, w którym będziemy poszukiwali miejsca zerowego (czyli pierwiastka funkcji f(x)). Aby można było zastosować algorytm połowienia (zwany również algorytmem bisekcji), w przedziale <a,b> muszą być spełnione poniższe warunki:

1.	Funkcja f(x) jest określona - uczniowie często nie rozumieją tego pojęcia. Określoność funkcji oznacza, iż dla każdej wartości argumentu x z przedziału <a,b> potrafimy policzyć wartość funkcji. W trakcie pracy algorytm połowienia oblicza wartości funkcji dla argumentów należących do tego przedziału <a,b>. Jeśli przypadkowo trafi na punkt, dla którego wartość funkcji jest nieokreślona, obliczenia się załamią. W praktyce konsekwencje mogą być tragiczne, np. zmiana lotu samolotu z poziomego na pionowy w kierunku ziemi... Dla przykładu rozważmy prostą funkcję: Ile wynosi wartość tej funkcji dla x = 1? Musimy dzielić przez 0, a jak wiadomo jest to zadanie niewykonalne. W punkcie x = 1 tak podana funkcja ma nieokreśloną wartość.
2.	Funkcja f(x) jest ciągła. Ciągłość funkcji oznacza z kolei, iż jej wartości nie "wykonują" nagłych skoków. Funkcja przebiega przez wszystkie wartości pośrednie - nie istnieją zatem przerwy w kolejnych wartościach funkcji. Dla przykładu rozważmy taką oto funkcję: Funkcja w przedziale <-2,1> posiada następujący wykres: Nieciągłość występuje w punkcie x = 0, czyli w miejscu zmiany przepisu funkcji. Zwróć uwagę, iż funkcja jest określona w tym punkcie - nieciągłość i nieokreśloność to dwie różne sprawy - nie myl ich!!!
3.	Funkcja f(x) na krańcach przedziału <a,b> przyjmuje różne znaki. Ponieważ funkcja, zgodnie z poprzednim podpunktem, jest ciągła, to przyjmuje w przedziale <a,b> wszystkie wartości pośrednie pomiędzy f(a) i f(b). Wartości te mają różne znaki (czyli leżą po różnych stronach osi OX), zatem musi być taki punkt x_o w przedziale <a,b>, dla którego funkcja przyjmuje wartość pośrednią: f(a) < f(x_o) = 0 < f(b) lub f(a) > f(x_o) = 0 > f(b)

Gdy funkcja f(x) spełnia powyższe trzy warunki, to w przedziale <a,b> zagwarantowane jest istnienie pierwiastka i możemy go wyszukać algorytmem połowienia (bisekcji). Zasada jest następująca:

Wyznaczamy punkt x_o jako środek przedziału <a,b> zgodnie ze wzorem:

Obliczamy wartość funkcji w punkcie x_o. Sprawdzamy, czy f(x_o) znajduje się dostatecznie blisko 0:

Jeśli nierówność jest spełniona, to x_o jest poszukiwaną wartością pierwiastka. Zwracamy wynik i kończymy algorytm. W przeciwnym razie za nowy przedział poszukiwań pierwiastka przyjmujemy tą połówkę <a,x_o> lub <x_o,b>, w której funkcja zmienia znak na krańcach. Algorytm powtarzamy od początku dotąd, aż znajdziemy pierwiastek

Program wyznacza miejsce zerowe funkcji: f(x) = x³(x + sin(x²- 1) - 1) - 1. Pierwiastków należy poszukiwać w przedziałach <-1,0> i <1,2>.

Obliczanie numeryczne. Obliczanie pola obszaru ograniczonego wykresem funkcji.

Całkowanie numeryczne

– metoda numeryczna polegająca na przybliżonym obliczaniu całek oznaczonych. Termin kwadratura numeryczna, często po prostu kwadratura, jest synonimem całkowania numerycznego, w szczególności w odniesieniu do całek jednowymiarowych. Dwu- i wyżej wymiarowe całkowania nazywane są czasami kubaturami, choć wyraz kwadratura również niesie to znaczenie dla całkowania w wyższych wymiarach.

Proste metody całkowania numerycznego polegają na przybliżeniu całki za pomocą odpowiedniej sumy ważonej wartości całkowanej funkcji w kilku punktach. Aby uzyskać dokładniejsze przybliżenie dzieli się przedział całkowania na niewielkie fragmenty. Ostateczny wynik jest sumą oszacowań całek w poszczególnych podprzedziałach. Najczęściej przedział dzieli się na równe podprzedziały, ale bardziej wyszukane algorytmy potrafią dostosowywać krok do szybkości zmienności funkcji.

Metoda prostokątów

Prawdopodobnie najprostszym wzorem jest metoda punktu środkowego (midpoint rule):

$\int\limits_{x_*}^{x_*+h} f(x) dx \approx h f\left( x_* + \frac h 2 \right)$

Jeśli funkcja $f(x)$ zmienia się w niewielkim stopniu na przedziale $(x_*, x_*+h)$ , reguła taka da dobre przybliżenie całki.

Metoda trapezów

Metoda trapezów polega na tym, że figurę ABCD zastępujemy figurą złożoną z trapezów wpisanych, tzn. krzywą aproksymujemy linią łamaną w nią wpisaną. Przedział całkowania $(a,b)$ dzielimy przy tym na $n$ równych części o długościach:

$h:=\frac{b-a}{n}$ .

Punktami podziału (końcami części) są wówczas:

$x_i = a+(i-1)h, \quad i=1\dots n+1.$

Wówczas pole figury złożonej z trapezów wynosi

$S_{n}=\frac{y_{1}+y_{2}}{2}h+\frac{y_{2}+y_{3}}{2}h+...+\frac{y_{n}+y_{n+1}}{2}h=h\left(\frac{y_{1}}{2}+y_{2}+y_{3}+...+y_{n}+\frac{y_{n+1}}{2}\right)$

gdzie

$y_{i}:=f(x_{i})$ – wartości funkcji w punktach podziału.

Stąd otrzymujemy wzór przybliżony w metodzie trapezów:

$\int\limits_{a}^{b}f(x)dx \approx h\left(\frac{y_{1}}{2}+y_{2}+y_{3}+...+y_{n}+\frac{y_{n+1}}{2}\right) = \frac{h}{2}\sum_{i=1}^{n}\left(f(x_{i})+f(x_{i+1})\right)$

Oszacowanie błędu tej metody wynosi

$R_{n}:=\left|\int\limits_{a}^{b}f(x)dx-S_{n}\right|\leq{\frac{(b-a)^{3}M^\prime{'}}{12n^{2}}}$

gdzie

$M^\prime{'}:=\max_{\langle a,b\rangle}|f^\prime{'}|$

wtorek, 18 marca 2014

Wyznaczanie różnych wartości za pomocą działań algebraicznych

Wyznaczanie różnych wartości za pomocą działań algebraicznych

Metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych) – iteracyjny algorytm wyznaczania przybliżonej wartości pierwiastka funkcji.

Rozwiązywanie równania nieliniowego

Zadanie

Zadaniem jest znalezienie pierwiastka równania zadanej funkcji ciągłej f:

$\mathbb{R} \supset [a,b] \ni x \mapsto f(x) \in \mathbb{R}$

w przedziale $[a,b].$ A zatem znalezienie takiego $x^{\ast} \in [a,b],$ które spełnia następujące równanie:

$f(x^{\ast})=0$

Opis metody

Ilustracja działania metody Newtona, pokazane zostały 4 pierwsze kroki.

W metodzie Newtona przyjmuje się następujące założenia dla funkcji f:

W przedziale [a,b] znajduje się dokładnie jeden pierwiastek.
Funkcja ma różne znaki na krańcach przedziału, tj. $f\left(a\right) \cdot f\left(b\right) < 0.$
Pierwsza i druga pochodna funkcji mają stały znak w tym przedziale.

W pierwszym kroku metody wybierany jest punkt startowy x₁ (zazwyczaj jest to wartość a, b, 0 lub 1), z którego następnie wyprowadzana jest styczna w f(x₁). Odcięta punktu przecięcia stycznej z osią OX jest pierwszym przybliżeniem rozwiązania (ozn. x₂).

Jeśli to przybliżenie nie jest satysfakcjonujące, wówczas punkt x₂ jest wybierany jako nowy punkt startowy i wszystkie czynności są powtarzane. Proces jest kontynuowany, aż zostanie uzyskane wystarczająco dobre przybliżenie pierwiastka

Kolejne przybliżenia są dane rekurencyjnym wzorem:

$x_{k+1} = x_k - \frac{f(x_k)}{f^\prime(x_k)}$

Szacowanie błędu

Błąd k-tego przybliżenia można oszacować poprzez nierówności (x* to dokładna wartość pierwiastka):

$|x^{\ast} - x_k| \leqslant \frac{f(x_k)}{m}$

lub

$|x^{\ast} - x_k| \leqslant \frac{M}{2m}(x^{\ast} - x_{k-1})^2$

gdzie stałe wyznacza się ze wzorów:

$m=\min_{x \in [a,b]} |f'(x)|$

oraz

$M=\max_{x \in [a,b]} |f''(x)|$

Warunek zakończenia obliczeń

W metodzie Newtona wykonuje się iteracyjne obliczenia, aż do momentu gdy ich wyniki będą satysfakcjonujące. W praktyce stosowanych jest kilka kryteriów warunków zakończenia obliczeń dla algorytmu ( $\epsilon$ to przyjęta dokładność obliczeń):

1. wartość funkcji w wyznaczonym punkcie jest bliska 0:

$\left| f(x_k) \right| \leqslant \epsilon$

2. odległość pomiędzy kolejnymi przybliżeniami jest dość mała:

$\left| x_{k+1} - x_k \right| \leqslant \epsilon$

3. szacowany błąd jest dostatecznie mały:

$\frac{M}{2m}(x_k - x_{k-1})^2 \leqslant \epsilon$

4. kryterium mieszane (punkty 1 i 2 jednocześnie)

Zbieżność

Metoda Newtona-Raphsona jest metodą o zbieżności kwadratowej – rząd zbieżności wynosi 2 (wyjątkiem są zera wielokrotne, dla których zbieżność jest liniowa i wynosi 1), zaś współczynnik zbieżności $\frac{M}{2m}.$ Oznacza to, iż przy spełnionych założeniach błąd maleje kwadratowo wraz z ilością iteracji.

Metoda Newtona jest metodą rozwiązywania równań często używaną w solverach, ze względu na jej szybką zbieżność (w algorytmie liczba cyfr znaczących w kolejnych przybliżeniach podwaja się). Wadą jej jest fakt, iż zbieżność nie musi zawsze zachodzić. W wielu przypadkach metoda bywa rozbieżna, kiedy punkt startowy jest zbyt daleko od szukanego pierwiastka równania.

Profesjonalne solvery wykorzystują stabilniejsze, lecz mniej wydajne metody (jak np. metoda bisekcji) do znalezienia obszarów zbieżności w dziedzinie funkcji, a następnie używają metody Newtona-Raphsona do szybkiego i dokładniejszego obliczenia lokalnego pierwiastka równania. Dodatkowo solvery posiadają zabezpieczenia przed nadmierną ilością wykonywanych iteracji (przekroczenie ustalonej liczby iteracji jest równoznaczne z niepowodzeniem algorytmu w zadanym przedziale).

Przykład

Za pomocą metody Newtona można obliczyć pierwiastek $\sqrt{a}$ dla każdej liczby $a \in \Bbb R^+:$

$\sqrt{a}=x \iff a=x^2 \iff x^2-a=0$

Funkcja f(x) ma postać:

$f(x) = x^2 -a$

$f\, '(x) = 2x$

Rekurencyjny wzór wynosi:

$x_{k+1} = x_k - \frac{x_k^2 -a}{2x_k}$

$x_{k+1} =\frac{1}{2}\left(x_k+\frac{a}{x_k}\right)$

Dla danych $a=2$ i $x_0=1,5$ algorytm przebiega następująco:

$x_{0} = 1,5$

$x_{1} = \frac{1}{2} (1,5 + \frac{2}{1,5}) \approx 1,416666$

$x_{2} = \frac{1}{2} (1,416666 + \frac{2}{1,416666}) \approx 1,414214$