Почему проблема с рюкзаком псевдополиномиальна?

Ответ 1

Время работы O (NW) для задачи неограниченного рюкзака с N элементами и рюкзаком размера W. W не является многочленом по длине ввода, что делает его псевдополиномиальным.

Рассмотрим W = 1,000,000,000,000. Для представления этого числа требуется всего 40 бит, поэтому размер ввода = 40, но вычислительная среда выполнения использует коэффициент 1,000,000,000,000, который равен O (2 ⁴⁰).

Таким образом, время выполнения более точно указано как O (N.2 ^{бит в W}), что является экспоненциальным.

Также смотрите:

• Как понять проблему с рюкзаком NP-complete?
• NP-полнота рюкзака
• Сложность алгоритма динамического программирования для проблемы с рюкзаком 0-1
• Псевдополиномиальное время

Ответ 2

В большинстве наших проблем мы имеем дело с большими списками номеров, которые удобно размещаются внутри стандартных типов данных int/float. Из-за того, что большинство процессоров построено для обработки 4-8 байтовых номеров за один раз без каких-либо дополнительных затрат (по сравнению с числами, чем размер, например, 1 байт), мы редко сталкиваемся с изменением времени выполнения от масштабирования наших номеров или вниз в пределах диапазонов, с которыми мы сталкиваемся в реальных проблемах - поэтому доминирующим фактором остается только огромное количество точек данных, n или m факторов, к которым мы привыкли.

(Вы можете себе представить, что нота Big-O скрывает постоянный множитель, который делит 32 или 64 бита за датум, оставляя только количество точек данных, когда каждый из наших чисел подходит к тому, что многие бит или меньше)

Но попробуйте переработать с другими алгоритмами, чтобы действовать на наборах данных, содержащих большие ints - числа, для представления которых требуется более 8 байтов - и посмотреть, что это делает для среды выполнения. Величина задействованных цифр всегда имеет значение, даже в других алгоритмах, таких как двоичная сортировка, после того, как вы выходите за пределы буфера безопасности, обычные процессоры дают нам "бесплатно", обрабатывая 4-8-байтовые партии.

Трюк с алгоритмом Knapsack, который мы обсуждали, заключается в том, что он необычно чувствителен (относительно других алгоритмов) к величине конкретного параметра W. Добавьте один бит в W и удвоите время работы алгоритма. Мы не видели такого драматического ответа на изменения в стоимости в других алгоритмах до этого, поэтому может показаться, что мы рассматриваем Knapsack по-разному - но это настоящий анализ того, как он реагирует не-полиномиальным образом к изменениям размера ввода.

Ответ 3

Время выполнения алгоритма Knapsack привязано не только к размеру ввода (n - количеству элементов), но также от величины входа (W - емкость рюкзака) O (nW), которая экспоненциальна в как он представлен на компьютере в двоичном формате (2 ^ n). Сложность вычислений (то есть, как обработка выполняется внутри компьютера через биты) связана только с размером входов, а не с их величин/значений.

Не обращайте внимания на список значений/веса на мгновение. Скажем, у нас есть экземпляр с мощностью ранца 2. W будет принимать два бита во входных данных. Теперь мы увеличим мощность ранца до 4, оставив остальную часть ввода. Наш вклад вырос только на один бит, но вычислительная сложность увеличилась в два раза. Если мы увеличим емкость до 1024, у нас будет всего 10 бит ввода для W вместо 2, но сложность увеличится в 512 раз. Сложность времени растет экспоненциально в размере W в двоичном (или десятичном) представлении.

Еще один простой пример, который помог мне понять псевдополиномиальную концепцию, - это алгоритм наивного примитивного тестирования. Для заданного числа n мы проверяем, равномерно ли оно делится на каждое целое число в диапазоне 2..√n, поэтому алгоритм принимает шаги √ (n-1). Но здесь n - величина ввода, а не размер.

                     Now The regular O(n) case

В отличие от этого, поиск массива для данного элемента выполняется в полиномиальное время: O (n). Это занимает не более n шагов, и здесь n - размер ввода (длина массива).

[см. здесь]

Вычисление битов, необходимых для хранения десятичного числа