Проблема: Bob Sale

Ответ 1

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

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

Для сокращения мы устанавливаем N = kb, и каждый бит представлен b ценовыми метками той же цены (думаю, что P _i увеличивает каждую метку bth). Пусть 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 (так как общее количество продуктов с ценой t _i равно 2b).
  
• Рассмотрим оптимальное решение Bob Sale. Прежде всего, обратите внимание, что в любом решении более трех корневых продуктов используют одну и ту же метку цен, для каждого такого корневого продукта, который "слишком много", есть более дешевый ценник, который придерживается менее 3 корневых продуктов. Это хуже, чем любое решение, было ровно 3 корневых продукта на метку цены (если они существуют).
  Теперь все еще может быть решение Bob Sale с 3-мя корневыми этикетками за цену, но их продукты для отпуска не носят одинаковые метки цен (например, поток бункеров). Скажем, самые дорогие метки метки цены - корневой продукт w _i, который имеет более дешевый помеченный продукт отпуска. Это означает, что три корневых метки 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, это так. Это также имеет место, если не самый дорогой ценовой тег - это "плохой", но любой другой.

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

Ответ 2

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

Проблема ( "Непрерывное одномашинное планирование с приоритетом, весами и общим штрафом за опоздание" )

Input:

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

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

• веса w ₁,..., w _n

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

Вывод:

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

Соответствие: job <= > product; я prec j <= > я имеет более низкую цену, чем j; вес <= > количество; L (t) <= > t ^th самая низкая цена

Когда L линейно, существует эффективный алгоритм полиномиального времени из-за Horn [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}. Нам нужен только максимальный средний вес, который можно вычислить снизу динамическим программированием.

• Планируйте задания с жадностью в порядке среднего веса их связанных наборов.

В примере 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

• job 8: 8

• задание 9: 9

• job 10: 10

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

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

[1] W. A. ​​Horn. Одиночное машинное упорядочение с предварительным заказом Treelike и линеарными штрафами за задержку. Журнал SIAM по прикладной математике, Vol. 23, № 2 (сент. 1972), стр. 189-202.

Ответ 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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

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

Это перекрестно вывешено из того же ответа в cstheory.

Ответ 6

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

Ответ 7

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

• Переменные: N ² двоичные переменные. Для ясности я буду индексировать их двумя целыми числами: x _ij 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 кодирует перестановку).

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

Ответ 8

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

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

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

Это (небольшая модификация) Алгоритм X из Knuth Art of Computer Programming, том 4, Fascicle 2, Section 7.2.1.2. Как и в большинстве алгоритмов Кнута, он использует индексирование на основе 1. Взломав его, чтобы он соответствовал индексированию вашего типичного языка программирования на основе 0, я оставляю в качестве упражнения для читателя.

Edit:

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