Bei Münzwerten mit c 1 = 1 und c 2 < c 3 < . . < c n sind im Bereich [ 2 , N ] 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?
Die Antwort ist für 3 Stückelungen bekannt ; aber was ist mit dem allgemeinen Fall?
ds.algorithms
Ganesh
quelle
quelle
Antworten:
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.
Sie fahren fort, das zu zeigen
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
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.
quelle