Asymptotika für den Geldwechsel

Bei Münzwerten mit und sind im Bereich gleichmäßig verteilte Zufallszahlen . Asymptotisch, für welchen Bruchteil von Münzen erzeugt der Gier-Algorithmus eine optimale Änderung unter Verwendung dieses Satzes von Stückelungen? $n$ $c_1=1$ $c_2<c_3<..<c_{n}$ $[2,N]$

Die Antwort ist für 3 Stückelungen bekannt ; aber was ist mit dem allgemeinen Fall?

ds.algorithms Ganesh
quelle

Die Ermittlung der Wahrscheinlichkeit für 4 Stückelungen wurde von Thane Plambeck gestellt, der auch einen Ausdruck für die Wahrscheinlichkeit für 3 Stückelungen lieferte (siehe den vom OP bereitgestellten Link). Das OP stellt eine allgemeinere Frage zum asymptotischen Verhalten dieser Wahrscheinlichkeit. Dies ist möglicherweise besser für math.SE und MO mit dem Tag asymptotics geeignet. @Ganesh: Was ist Ihre TCS-Motivation oder der Grund für das Tag ds.algorithms?

András Salamon

@Andras, das ist sehr viel ein komplexitätstheoretisches Problem. Wenn der gierige Ansatz beispielsweise in 90% der Fälle eine optimale Lösung liefert, kann ich auch die dynamische Programmierung vergessen und die verbleibenden 10% der Zeit mit suboptimalen Lösungen auskommen. Vielleicht ist dies bei Math. * Angemessener, aber die Motivation liegt in TCS. Schließlich ist mir das "richtige Tag" entgangen - daher dachte ich, dass ds.algorithms die beste Annäherung ist.

Ganesh

Dies ist keine Antwort, aber vielleicht weist dies Sie oder eine andere Person in die richtige Richtung.

Ich fand die Arbeit von D. Kozen und S. Zaks mit dem Titel "Optimale Grenzen für das Änderungsproblem", in der sie Bedingungen dafür angeben, wann der gierige Änderungsalgorithmus einer Münzwechselinstanz optimal ist. Ich werde ihre Notation verwenden.

Bei einer gegebenen Münzwechselinstanz von verschiedenen Münzen a Funktion die die optimale Anzahl von Münzen darstellt, die zum Ändern von und einer Funktion erforderlich sind $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$ , die die Anzahl der Münzen zu gierig make Änderung erforderlich , dannwenn $G(x)$ $x$ , gibt es ein Gegenbeispiel im Bereich von $M(x) \ne G(x)$ $c_{3} + 1 < x < c_{m - 1} + c_{m}$ $c_3 + 1 < x < c_{m-1} + c_m$

Sie fahren fort, das zu zeigen

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

Dies gibt uns einen "effizienten" Test (bis zu Pseudo-Polynom-Zeit), um festzustellen, ob eine Münzwechselinstanz gierig ist oder nicht.

Unter Verwendung des Obigen habe ich eine kurze Simulation durchgeführt, deren Ergebnisse in einer Log-Log-Skala unten aufgezeichnet sind

Bildbeschreibung hier eingeben

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

Auf die Gefahr der Beantwortung einer Frage, die Sie nicht gestellt haben, möchte ich Sie darauf hinweisen, dass Münzsysteme der "realen Welt" keine einheitliche Verteilung für Münzwerte verfolgen. Zum Beispiel haben die USA mindestens 12 Stückelungen (einschließlich Rechnungen: $(1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$ ), die nicht gleichmäßig verteilt zu sein scheinen. Vielleicht würde ein Blick auf andere Verteilungen, um die Münzwerte zu ermitteln, in der großen Systemgrenze nicht triviale Ergebnisse bringen. Zum Beispiel könnte eine Verteilung nach dem Stromgesetz Münzwerte ergeben, die denen der USA ähnlicher sind.

user834
quelle

Asymptotika für den Geldwechsel

Antworten: