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

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

("nonpreemptive один-машина планирование с приоритетом, веса, и общего опоздание наказания")

вход:

• задания 1,..., n

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

• гирей Вт₁,..., w_n

• неотрицательная штрафная функция запаздывания L (t) от {1, ..., n} до Z₊

выход:

• перестановка π из {1,..., n} минимизация ∑_j w_j L(π(j)) с учетом ограничений, что для всех I prec j мы имеем π(i)

соответствие: работа продукт; I prec j i имеет более низкий цена чем j; вес количество; L (t) t^е низкие цены

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

1. для всех J найдите связный набор заданий, содержащий только j и его преемников, средний вес которых максимален. Например, если n = 6 и ограничения приоритета равны 1 prec 2 и 2 prec 3 и 2 prec 4 и 4 prec 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 Theory Stack Exchange будет идея.

[1] W. A. Horn. Одномашинная последовательность заданий с древовидным порядком приоритета и линейными штрафами за задержку. SIAM Journal on Applied Mathematics, Vol. 23, Вып. 2 (Отд., 1972), РР. 189-202.

поскольку я думал, что проблема была забавной, я сделал модель для поиска решений с использованием программирования ограничений. Модель написана на языке моделирования под названием 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 back-end для решения проблемы примера генерируется следующий вывод (предполагая, что модель находится в модель.мзн и данные в данных.дзн)

$ 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

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

размещение некоторых мыслей в качестве сообщества Вики, не стесняйтесь редактировать.

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

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

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

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.

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

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

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

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

со ссылкой на результат от А SWAT 2010 paper

---

это кросс-сообщение из того же ответ в cstheory.

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

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

• переменные:N² двоичные переменные. Для ясности я проиндексирую их двумя целыми числами:x_ij и 1 если и только если продукт Я присваивается метка j.
• целевая функция: уменьшить сумму свыше Я и j на S_ЯP_j x_ij (представляет исходную целевую функцию).
• ограничения: для каждого k сумма j на P_j x_Akj – P_j x_Bkj и ≤ 0 (представляет исходные ценовые ограничения).
• ограничения: для каждого Я сумма j на x_ij и 1; для каждого j сумма Я на x_ij и 1 (говорит, что x кодирует a перестановка.)

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

генерировать перестановки цен в лексикографическом порядке, и вернуть первый, который соответствует ограничениям.

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

1. Set l[k] = k+1 на 0 <= k < n и l[n] = 0. Затем установите k = 1.
2. Set p = 0, q = l[0].
3. Set 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. Set k = k - 1, и расторгнуть, если k = 0. В противном случае установите p = u[k], q = M[k], l[p] = q и перейти к 5.

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

Edit:

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