Проблема: продажа Боба

Question

Примечание. Это абстрактная формулировка реальной проблемы, связанной с упорядочением записей в SWF-файле.Решение поможет мне улучшить приложение с открытым исходным кодом.

У Боба есть магазин, и он хочет сделать продажу.В его магазине есть несколько товаров, и у него есть определенное целое количество единиц каждого товара на складе.У него также есть несколько смонтированных на полках ценников (столько же, сколько продуктов), на которых уже напечатаны цены.Он может разместить любой ценник на любом товаре (единая цена за один предмет для всего его запаса этого товара), однако некоторые товары имеют дополнительное ограничение - любой такой товар не может быть дешевле, чем определенный другой товар.

Вы должны найти способ расстановки ценников так, чтобы общая стоимость всех товаров Боба была как можно ниже.Общая стоимость - это сумма назначенного ценника каждого товара, умноженная на количество этого товара на складе.

---

Дано:

• N - количество товаров и ценаэтикетки
• S _i , 0≤ i

Answer 1

Задача является NP-полной для общего случая.Это можно показать с помощью сокращения на 3 раздела (который все еще является сильной версией NP-полной упаковки бункеров).

Let w ₁ , ..., w _n - веса объектов экземпляра с 3 разделами, пусть b - размер ячейки, а k = n / 3 - числоконтейнеры, которые разрешено заполнять.Следовательно, существует 3-секционное разделение, если объекты могут быть разделены таким образом, чтобы в каждом бине было ровно 3 объекта.

Для сокращения мы устанавливаем N = kb , и каждый бин представляется как b ценники той же цены (представьте себе, что P _i увеличивается с каждым b -ым ярлыком).Пусть t _i , 1≤ i ≤ k , будет ценой этикеток, соответствующих i мусорное ведроДля каждого w _i у нас есть один продукт S _j количества w _i + 1 (назовем это корневым продуктом w _i ) и другим w _i - 1 продуктов количества 1, которые требуютсябыть дешевле, чем S _j (назовите эти продукты отпуска).

Для t _i = (2b+ 1) ⁱ , 1≤ i ≤ k , существует 3 раздела, если и только если Боб может продать за 2b Σ _{1≤ i ≤ k} t _i :

• Если есть решениедля 3-х разделов, то все b продуктов, соответствующих объектам w _i , w _j , w _l , назначенные одному и тому же контейнеру, могут быть помечены по одной цене без нарушения ограничений.Таким образом, решение обошлось в 2b Σ _{1≤ i ≤ k} t _i (поскольку общее количество продуктов с ценой т _i равно 2b ).
  
• Рассмотрим оптимальное решение продажи Боба.Сначала обратите внимание, что в любом решении более 3 корневых продуктов имеют одинаковую ценовую метку, для каждого такого «слишком большого» корневого продукта есть более дешевый ценник, который привязан к менее чем 3 корневым продуктам.Это хуже, чем любое решение, если есть ровно 3 корневых продукта на ценовую метку (если таковые существуют).
  Теперь все еще может быть решение Bob's Sale с 3 корневыми этикетками на цену, но их отпускные продукты не носят то же самоеценники (с течением времени вид мусора).Скажем, самые дорогие ценники помечают корневой продукт w _i , который имеет более дешевый маркированный отпускный продукт.Это означает, что 3 корневых метки w _i , w _j , w _l Теги с самой дорогой ценой не составляют b .Следовательно, общая стоимость продуктов, помеченных по этой цене, составляет не менее 2b + 1 .
  Следовательно, такое решение стоило t _k (2b + 1) + некоторые другие расходы.Поскольку оптимальная стоимость для существующего 3-х разделов составляет 2b Σ _{1≤ i ≤ k} t _i, мы должны показать, что только что рассмотренный случай хуже.Это тот случай, если t _k > 2b Σ _{1≤ i ≤ k-1} t _i (обратите внимание, что в сумме сейчас k-1 ).Настройка t _i = (2b + 1) ⁱ , 1≤ i ≤ k , этодело.Это также справедливо, если не самый дорогой ценник - «плохой», а любой другой.

Итак, это деструктивная часть ;-) Однако, если число различных ценников является постоянным, вы можете использовать динамическое программирование для его решения за полиномиальное время.

Answer 2

Эта проблема напоминает многие проблемы планирования, рассмотренные в литературе по CS.Позвольте мне переформулировать его как единое целое.

Задача («Непрерывное планирование на одной машине с приоритетом, весами и общими штрафами за задержку»)

Ввод:

• заданий 1,…, n

• «древовидное» отношение приоритета на заданиях (диаграмма Хассе - лес)

• весовые коэффициенты w ₁ ,…, w _n

• неубывающая функция штрафа за запаздывание L (t) из {1,…, N} - Z ₊

Выход:

• перестановка π из {1,…, N} минимизация 10 _j w _j L (π (j)) с учетом ограничений, которые для всех i prec j имеют π (i) <π (j).</li>

Переписка: работа <=> product;у меня заранее j <=> у меня цена ниже, чем у j;вес <=> количество;L (t) <=> t ^th самая низкая цена

Когда L линейно, существует эффективный алгоритм полиномиального времени благодаря Рогу [1].Статья находится за стеной оплаты, но основная идея -

1. Для всех j найдите связанный набор заданий, содержащий только j и его преемников, средний вес которых максимален.Например, если n = 6, а ограничения предшествования - 1 пред 2 и 2 пред 3 и 2 пред 4 и 4 пред 5, то рассматриваемые множества для 2: {2}, {2, 3}, {2, 4}, {2, 3, 4}, {2, 4, 5}, {2, 3, 4, 5}.На самом деле нам нужен только максимальный средний вес, который можно вычислить снизу вверх с помощью динамического программирования.

2. Жадно планируйте задания в порядке среднего веса их соответствующих наборов.

В примере с CyberShadow имеем n = 10 и 1 prec 10 и w _j = j и L (t) = t.Значения, вычисленные на шаге 1:

• задание 1: 5,5 (среднее от 1 и 10)

• задание 2: 2

• задание 3: 3

• задание 4: 4

• задание 5: 5

• задание 6: 6

• задание 7: 7

• задание 8: 8

• задание 9: 9

• задание 10: 10

Оптимальный порядок 9, 8, 7, 6, 1,10, 5, 4, 3, 2.

---

Этот алгоритм может хорошо работать на практике даже для другого выбора L, поскольку доказательство оптимальности использует локальное улучшение.В качестве альтернативы, возможно, у кого-нибудь из биржи стеков теории CS есть идея.

[1] WA Horn. Последовательность заданий для одной машины с древовидным порядком приоритетов и штрафами за линейную задержку .Журнал SIAM по прикладной математике, вып.23, No. 2 (Sep., 1972), стр. 189–202.

Answer 3

Так как я думал, что проблема была забавной, я сделал модель для поиска решений, используя программирование ограничений. Модель написана на языке моделирования под названием MiniZinc .

include "globals.mzn";

%%% Data declaration
% Number of products
int: n;
% Quantity of stock
array[1..n] of int: stock;
% Number of distinct price labels
int: m;
% Labels
array[1..m] of int: labels;
constraint assert(forall(i,j in 1..m where i < j) (labels[i] < labels[j]),
              "All labels must be distinct and ordered");
% Quantity of each label
array[1..m] of int: num_labels;
% Number of precedence constraints
int: k;
% Precedence constraints
array[1..k, 1..2] of 1..n: precedences;

%%% Variables
% Price given to product i
array[1..n] of var min(labels)..max(labels): prices :: is_output;
% Objective to minimize
var int: objective :: is_output;

%%% Constraints
% Each label is used once
constraint global_cardinality_low_up_closed(prices, labels, num_labels, num_labels);

% Prices respect precedences
constraint forall(i in 1..k) (
            prices[precedences[i, 1]] <= prices[precedences[i, 2]]
       );

% Calculate the objective
constraint objective = sum(i in 1..n) (prices[i]*stock[i]);

%%% Find the minimal solution
solve minimize objective;

Данные по проблеме приведены в отдельном файле.

%%% Data definitions
n = 10;
stock = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
m = 10;
labels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
num_labels = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
k = 1;
precedences = [| 1, 10 |];

Модель довольно наивная и прямолинейная, без излишеств. Используя серверную часть Gecode для решения примера задачи, генерируется следующий вывод (при условии, что модель находится в model.mzn, а данные в data.dzn)

$ mzn2fzn -I/usr/local/share/gecode/mznlib/ model.mzn data.dzn
$ fz -mode stat -threads 0 model.fzn 
objective = 265;
prices = array1d(1..10, [1, 10, 9, 8, 7, 6, 5, 4, 3, 2]);
----------
objective = 258;
prices = array1d(1..10, [2, 10, 9, 8, 7, 6, 5, 4, 1, 3]);
----------
objective = 253;
prices = array1d(1..10, [3, 10, 9, 8, 7, 6, 5, 2, 1, 4]);
----------
objective = 250;
prices = array1d(1..10, [4, 10, 9, 8, 7, 6, 3, 2, 1, 5]);
----------
objective = 249;
prices = array1d(1..10, [5, 10, 9, 8, 7, 4, 3, 2, 1, 6]);
----------
==========

%%  runtime:       0.027 (27.471000 ms)
%%  solvetime:     0.027 (27.166000 ms)
%%  solutions:     5
%%  variables:     11
%%  propagators:   3
%%  propagations:  136068
%%  nodes:         47341
%%  failures:      23666
%%  peak depth:    33
%%  peak memory:   237 KB

Для более крупных задач это, конечно, намного медленнее, но модель, как правило, будет генерировать последовательно лучшие решения со временем.

Answer 4

Это продолжение ответа Геро .Идея состоит в том, чтобы изменить его конструкцию, чтобы показать сильную NP-твердость.

Вместо выбора $ t_i = (2b + 1) ^ i $, выберите $ t_i = i $.Теперь вам нужно изменить аргумент, что решение с призом $ P = 2b \ sum_ {1 \ leq i \ leq k} t_i $ подразумевает, что существует 3-разбиение.

Возьмите произвольный заказ на полку.Выполните учет следующим образом: распределите $ w_i-1 $ единиц количества корневого продукта по его конечным продуктам.Тогда у каждого продукта есть количество 2. По определению ограничений это не сдвигается к более высокой цене.После этого смещения цена будет ровно $ P $.Если сдвиг сместил некоторое количество к более низкому призу, первоначальный приз был строго больше, чем $ P $.

Следовательно, получить заявленный приз можно только в том случае, если все листовые продукты имеют такой же приз, каких корневой продукт, что означает, что существует 3-секционное.

Ссылаясь на результат из SWAT 2010 paper , этот аргумент показывает, что даже при унарном кодировании чисел и $ k $В разных ценниках время выполнения $ f (k) \ cdot n ^ {O (1)} $ нарушало бы «стандартные предположения о сложности».Это заставляет намеки на динамическое программирование со временем выполнения $ n ^ {O (k)} $ выглядеть не так уж плохо.

---

Это перекрестная публикация из того же ответа в целом.

Answer 5

Публикуя некоторые мысли в вики сообщества, не стесняйтесь редактировать.

Эту проблему проще визуализировать, если вы думаете о дополнительных ограничениях, как о необходимости выкладывать или переупорядочивать набор деревьев сверху вниз таким образом, что каждый узел должен находиться справа от его родителя. (товары слева дешевле, а справа дороже).

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

Мы можем сделать несколько замечаний:

1. При «размещении» (назначении ценника) двух конфликтующих товаров они всегда будут рядом друг с другом.
2. Если вы сортируете все продукты по количеству, не принимая во внимание ограничения, а затем располагаете их оптимально, чтобы они удовлетворяли ограничениям, то конечные позиции всех продуктов в конфликтующей группе всегда будут между (включительно) самой левой и самой правой начальными позициями продукты.
3. Следовательно, если вы можете разделить дерево ограничений на два, удалив один правый край из дерева так, чтобы диапазон начальных позиций продуктов из нижнего поддерева и путь к корню дерева не перекрывались, Вы можете безопасно рассматривать их как два разных дерева ограничений (или отдельные узлы) и забыть, что между ними была зависимость. ( простой пример )

Идея алгоритма:

1. Сначала разместите все товары без ограничений.
2. Для каждого дерева ограничений:
   1. Разделите его на поддеревья по всем правым краям (ребра между неконфликтующими продуктами). Теперь у нас есть набор поддеревьев со всеми ребрами, указывающими влево.
   2. Для каждого поддерева:
      1. Получить топологически отсортированный список
      2. Попробуйте вставить этот список в каждую позицию, начиная с самой низкой до самой высокой начальной позиции товаров в этом поддереве, выберите ту, которая дает наименьшую общую цену
   3. Для каждого края, удаленного на шаге 2.1:
      1. Если новые позиции для двух поддеревьев "конфликтуют":
         1. Объединить старшее с нижним списком (особый случай топологической сортировки)
         2. Аналогичным образом попробуйте найти оптимальную позицию для составного списка
         3. Для будущего слияния рассмотрим два проверенных поддерева как одно поддерево

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

В случае, если количество различных цен невелико, вы можете использовать deque (или двусвязный список) для каждой отдельной цены, удерживая все элементы с назначенной им ценой. Заказы заказываются от самой низкой до самой высокой цены. Вставка элемента в деку сдвигает последний элемент в начало следующего (для следующей более высокой цены) и так далее для всех деков после этого.

Одна вещь, которую следует отметить в отношении итеративных / пузырьковых алгоритмов сортировки: когда у вас есть конфликтующая пара продуктов, недостаточно жадно идти в любом направлении на одну позицию, пока следующая не приведет к улучшению. Вот тестовый пример, который я получил , немного поиграв с Mathematica , записав генератор тестовых примеров :

Price, $   1 2 7 9
Qty        3 2 1 4

Ограничение - наличие элемента 4-го кол-ва справа от элемента 1-кол.Как показано выше, общая стоимость составляет 50 долларов.Если вы сдвинете пару на одну позицию влево (так что 3 1 4 2), общая сумма поднимется до 51 доллара, но если вы пойдете еще раз (1 4 3 2), она снизится до 48 долларов.

Answer 6

Один из способов решения проблемы - выразить ее с помощью 0-1 линейного программирования и решить ее с помощью аддитивного алгоритма Баласа.Вот как можно закодировать проблему:

• Переменные: N ² двоичные переменные.Для наглядности я их индексирую двумя целыми числами: x _ij is 1 тогда и только тогда, когда продукту i присвоен ярлык j .
• Целевая функция: минимизировать сумму за i и j из S _i P _j x _ij (представляет исходную целевую функцию).
• Ограничение: для каждого k сумма свыше j из P _j x _{A k j} - P _j x _{B k j} равно ≤ 0 (соответствует исходным ценовым ограничениям).
• Ограничения: длякаждая i сумма сверх j из x _ij равно 1 ;за каждую j сумму свыше i из x _ij равно 1 (говорит, что x кодирует перестановку).

Я не специалист по линейному программированию, возможно, существует более эффективное кодирование.

Answer 7

Вы можете сначала попытаться решить более простой случай, когда вам просто нужно отсортировать этикетки по цене и продукты по количеству и сопоставить оба сразу, а затем использовать эволюционный процесс в этом первом приближении: генерировать случайные вариации упорядоченного списка продуктовчто у вас есть, перемещая небольшое количество случайно выбранных элементов вверх или вниз по списку всего на несколько мест, рассчитайте общую стоимость каждого варианта в списке, сохраните лучшие из них и сделайте их основой вашего следующего поколения.Я полагаю, что повторение этого процесса на протяжении нескольких поколений должно в конечном итоге дать вам правильный ответ на вашу проблему за долю времени, которое потребуется для того, чтобы перебить решение проблемы.

Answer 8

Генерирует перестановки цен в лексикографическом порядке и возвращает первое значение, соответствующее ограничениям.

При условии, что товары и цены уже отсортированы (от наименьшего к большинству и от наивысшего кнаименьший, соответственно)

1. Установить l[k] = k+1 для 0 <= k < n и l[n] = 0.Затем установите k = 1.
2. Установите p = 0, q = l[0].
3. Установите M[k] = q.Если какое-либо ценовое ограничение, касающееся P[k], не выполняется, перейдите к 5. В противном случае, если k = n, верните M[1]...M[n].
4. Set u[k] = p, l[p] = l[q], k = k + 1 и перейдите к 2.
5. Set p = q, q = l[p].Если q != 0, перейдите к 3.
6. Установите k = k - 1 и завершите, если k = 0.В противном случае установите p = u[k], q = M[k], l[p] = q и перейдите к 5.

Это (небольшая модификация) алгоритма X из Искусства компьютерного программирования Кнута, том 4, раздел 2, раздел 7.2.1.2.Как и в большинстве алгоритмов Кнута, он использует индексирование на основе 1.Подгоняя его под нумерацию индексации вашего типичного языка программирования на основе 0, я оставляю это упражнение для читателя.

Редактировать:

К сожалению, оказывается, что этоне гарантирует неубывающую последовательность.Мне придется больше подумать, чтобы понять, можно ли это спасти.