Asymptotyki do wymiany monet

Podano nominałów monet, przy czym i są liczbami losowymi równomiernie rozmieszczonymi w przedziale . Asymptotycznie, dla jakiej części monet chciwy algorytm generuje optymalną zmianę przy użyciu tego zestawu nominałów? $n$ $c_1=1$ $c_2<c_3<..<c_{n}$ $[2,N]$

Odpowiedź jest znana z 3 nominałów ; ale co z ogólnym przypadkiem?

ds.algorithms

— Ganesh
źródło

Ustalenie prawdopodobieństwa dla 4 denominacji postawił Thane Plambeck, który również przedstawił wyrażenie prawdopodobieństwa dla 3 denominacji (patrz link podany przez PO). OP zadaje bardziej ogólne pytanie na temat asymptotycznego zachowania tego prawdopodobieństwa. Może to być bardziej odpowiednie dla matematyki.SE i MO, z tagami asymptotycznymi. @Ganesh: Jaka jest twoja motywacja TCS lub powód, dla którego znacznik ds.algorithms?

— András Salamon,

@ Andras, jest to bardzo problem teorii złożoności. Na przykład, jeśli chciwe podejście uzyska optymalne rozwiązanie, powiedzmy 90% czasu, równie dobrze mogę zapomnieć o programowaniu dynamicznym i zadowolić się rozwiązaniami suboptymalnymi przez pozostałe 10% czasu. Być może jest to bardziej odpowiednie w Math. *, Ale motywacja leży w TCS. Wreszcie „właściwy znacznik” uciekł mi - więc pomyślałem, że algorytm ds. jest najlepszym przybliżeniem.

— Ganesh,

To nie jest odpowiedź, ale może to skieruje ciebie lub kogoś innego we właściwym kierunku.

Znalazłem artykuł D. Kozen i S. Zaksa zatytułowany „Optymalne granice dla problemu dokonywania zmian”, w którym podają warunki, w których algorytm zachłannej zmiany instancji zmiany monety jest optymalny. Wykorzystam ich notację.

Biorąc pod uwagę wystąpienie zmiany monety różnych monet funkcja reprezentująca optymalną liczbę monet potrzebną do zmiany oraz funkcja reprezentująca liczbę monet potrzebnych do chciwej zmiany , to jeśli , istnieje kontrprzykład w zakresie $m$
$(c_{1}, c_{2}, c_{3}, \dots, c_{m - 1}, c_{m})$ $( c_1, c_2, c_3, \cdots, c_{m-1}, c_{m} )$ $c_{1} = 1 < c_{2} < c_{3} < \dots < c_{m - 1} < c_{m}$ $c_1 = 1 < c_2 < c_3 < \cdots < c_{m-1} < c_m$ $M(x)$ $x$ $G(x)$ $x$ $M(x) \ne G(x)$ $c_{3} + 1 < x < c_{m - 1} + c_{m}$ $c_3 + 1 < x < c_{m-1} + c_m$

Idą dalej, aby to pokazać

Jeśli dla każdego w zakresie to (tzn. Chciwy algorytm jest optymalny). $x$ $c_3 + 1 < x < c_{m-1} + c_m$
$G (x) \leq G (x - c) + 1$ $G(x) \le G(x-c) + 1$ $c \in (c_{1}, c_{2}, \dots, c_{m})$ $c \in (c_1, c_2, \cdots, c_m )$ $G(x) = M(x)$

To daje nam „efektywny” test (do czasu pseudo wielomianu) w celu ustalenia, czy instancja wymiany monety jest zachłanna, czy nie.

Korzystając z powyższego, przeprowadziłem krótką symulację, której wyniki są wykreślone na skali log-log poniżej

wprowadź opis zdjęcia tutaj

Każdy punkt reprezentuje średnią z 10000 kreacji instancji dla pokazanego , a każdy element został wybrany jako odrębny, ale poza tym jednolity i losowy z zakresu . $m$ $[1 \cdots N]$

Biorąc pod uwagę, że prawdopodobieństwo optymalnego algorytmu zachłanności dla jest takie, jak , od samego spojrzenia na wykres zaryzykowałbym zgadnij, że prawdopodobieństwo optymalnego algorytmu zachłannego jest następujące: $m=3$ $\frac{8}{3} N^{-\frac{1}{2}}$

p_{m} (N) \propto N^{- \frac{(m - 2)}{2}}

$p_m(N) \propto N^{-\frac{(m-2)}{2} }$

gdzie jest prawdopodobieństwem, że różne monety losowane losowo z zakresu są optymistycznie zachłanne (znane również jako „kanoniczne”). $p_m(N)$ $m$ $N$

W dużym granicach, prawdopodobieństwo tego, że optymalne rozwiązanie chciwy szybko przechodzi do 0 dla każdej nietrywialną wartości . Jeśli powyższe równanie się zachowuje, łatwo to zauważyć, ale mogą istnieć inne sposoby patrzenia na to, które dają ten sam wniosek. Na przykład patrząc na prace Borga, Chayesa, Mertensa i losowego modelu energii Naira wskazują, że energia jest zbyt postrzępiona na dole, aby oczekiwać lokalnych ruchów (tj. Zachłannych ruchów), aby dać optymalne rozwiązanie. Jest to oczywiście problem z partycjami liczbowymi i służy jedynie intuicji, a nie jednoznacznej odpowiedzi. $m$ $N$

Na ryzyko udzielenia odpowiedzi na pytanie, które nie zadałeś, chciałem zauważyć, że systemy monet w „realnym świecie” nie mają jednolitego rozkładu nominałów monet. Na przykład USA ma co najmniej 12 nominałów (w tym rachunki: ), które nie wydają się być jednolicie rozmieszczone. Być może spojrzenie na inne rozkłady generujące nominały monet przyniosłoby nietrywialne wyniki w dużym limicie systemu. Na przykład rozkład prawa energetycznego może dawać nominały monet bardziej zbliżone do amerykańskich. $(1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$

— użytkownik834
źródło