Asymptotique pour changer de pièce

Étant donné dénominations, avec et étant des nombres aléatoires uniformément répartis dans l'intervalle . De manière asymptotique, pour quelle fraction de pièces l'algorithme gourmand génère-t-il un changement optimal en utilisant cet ensemble de dénominations? $n$ $c_1=1$ $c_2<c_3<..<c_{n}$ $[2,N]$

La réponse est connue pour 3 dénominations ; mais qu'en est-il du cas général?

ds.algorithms Ganesh
la source

Thane Plambeck a posé la probabilité de 4 coupures, qui a également fourni une expression pour la probabilité de 3 coupures (voir le lien fourni par le PO). L'OP pose une question plus générale sur le comportement asymptotique de cette probabilité. Cela pourrait peut-être être plus approprié pour math.SE et MO, avec des asymptotiques de balises. @Ganesh: Quelle est votre motivation TCS ou la raison de la balise ds.algorithms?

András Salamon

@ Andras, c'est vraiment un problème de théorie de la complexité. Par exemple, si l'approche gourmande obtient une solution optimale, disons 90% du temps, je pourrais aussi bien oublier la programmation dynamique et me contenter des solutions sous-optimales les 10% restants. C'est peut-être plus approprié à Math. *, Mais la motivation réside dans TCS. Enfin, la «bonne balise» m'a échappé - j'ai donc pensé que ds.algorithms était la meilleure approximation.

Ganesh

Réponses:

Ce n'est pas une réponse mais peut-être que cela vous orientera, vous ou quelqu'un d'autre, dans la bonne direction.

J'ai trouvé l'article de D. Kozen et S. Zaks intitulé "Limites optimales pour le problème de changement" dans lequel ils donnent les conditions pour lesquelles l'algorithme de changement gourmand d'une instance de changement de pièce est optimal. J'utiliserai leur notation.

Étant donné une instance de changement de pièce de pièces distinctes a fonction représentant le nombre optimal de pièces nécessaires pour changer et une fonction $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$ représentant le nombre de pièces nécessaires pour changer goulûment de , alors si , il existe un contre-exemple dans la gamme $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$

Ils montrent ensuite que

$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)$

Cela nous donne un test "efficace" (jusqu'à un temps pseudo polynomial) pour déterminer si une instance de changement de pièce est gourmande ou non.

En utilisant ce qui précède, j'ai exécuté une courte simulation dont les résultats sont tracés sur une échelle log-log ci-dessous

entrez la description de l'image ici

$m$ $[1 \cdots N]$

$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} }$

$p_m(N)$ $m$ $N$

$m$ $N$

$(1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$ ) qui ne semblent pas être uniformément répartis. Peut-être que regarder d'autres distributions pour générer les dénominations de pièces de monnaie donnerait des résultats non triviaux dans la grande limite du système. Par exemple, une distribution de loi de puissance pourrait produire des coupures de pièces plus similaires à celles des États-Unis.

user834
la source