Асимптотика для смены монет

Даны монет номиналом, с и - случайные числа, равномерно распределенные в диапазоне . Асимптотически, для какой доли монет жадный алгоритм генерирует оптимальное изменение, используя этот набор номиналов? $n$ $c_1=1$ $c_2<c_3<..<c_{n}$ $[2,N]$

Ответ известен для 3 конфессий ; а как насчет общего случая?

ds.algorithms Ganesh
источник

Определение вероятности для 4 конфессий было дано Тейном Пламбеком, который также предоставил выражение для вероятности для 3 конфессий (см. Ссылку, предоставленную ФП). ОП задает более общий вопрос об асимптотическом поведении этой вероятности. Возможно, это больше подходит для математики. SE и MO с асимптотикой тегов. @Ganesh: Какова ваша мотивация TCS, или причина для тега ds.algorithms?

Андрас Саламон

@ Андрас, это очень сложная теория. Например, если жадный подход дает оптимальное решение, скажем, 90% времени, я могу также забыть о динамическом программировании и довольствоваться неоптимальными решениями в оставшиеся 10% времени. Может быть, это более уместно в Math. *, Но мотивация заключается в TCS. Наконец, «правильный тег» ускользнул от меня - поэтому я подумал, что ds.algorithms - лучшее приближение.

Ганеш

Ответы:

Это не ответ, но, возможно, это укажет вам или кому-то еще в правильном направлении.

Я нашел статью Д. Козена и С. Закса под названием «Оптимальные границы для задачи изменения», в которой они дают условия, когда алгоритм жадных изменений экземпляра монетного экземпляра является оптимальным. Я буду использовать их обозначения.

Для данного экземпляра замены монет различных монет a функция представляющая оптимальное количество монет, необходимое для внесения изменений в и функция $m$
$(с_{1}, с_{2}, с_{3}, \dots, с_{м - 1}, с_{м})$ $( c_1, c_2, c_3, \cdots, c_{m-1}, c_{m} )$ $с_{1} знак равно 1 < с_{2} < с_{3} < \dots < с_{м - 1} < с_{м}$ $c_1 = 1 < c_2 < c_3 < \cdots < c_{m-1} < c_m$ $M(x)$ $x$ представляет количество монет, необходимое для жадного внесения изменений для , тогда, если , существует контрпример в диапазоне $G(x)$ $x$ $M(x) \ne G(x)$ $с_{3} + 1 < Икс < с_{м - 1} + с_{м}$ $c_3 + 1 < x < c_{m-1} + c_m$

Они продолжают показывать, что

$x$ $c_3 + 1 < x < c_{m-1} + c_m$
$грамм (Икс) \leq грамм (Икс - с) + 1$ $G(x) \le G(x-c) + 1$ $с \in (с_{1}, с_{2}, \dots, с_{м})$ $c \in (c_1, c_2, \cdots, c_m )$ $G(x) = M(x)$

Это дает нам «эффективный» (до псевдополиномиального времени) тест, чтобы определить, является ли экземпляр замены монет жадным или нет.

Используя вышеизложенное, я провел короткую симуляцию, результаты которой представлены в масштабе лог-лога ниже

введите описание изображения здесь

$m$ $[1 \cdots N]$

$m=3$ $\frac{8}{3} N^{-\frac{1}{2}}$

п_{м} (N) α N^{- \frac{(м - 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)$ ) которые не выглядят равномерно распределенными. Возможно, просмотр других распределений для создания номиналов монет даст нетривиальные результаты в большом системном пределе. Например, распределение по степенному закону может привести к номиналу монет, более похожему на американский.

user834
источник