Задача упаковки в контейнеры

Оглавление

Введение

Существуют  три класса задач: P-задачи, NP-задачи и E-задачи. Наша задача относится к NP-полных задач.

Самыми лучшими  являются линейные алгоритмы порядка O(n), где n — размерность входных данных, например алгоритм поиска эйлеровых циклов в графе.

Другие «хорошие»  алгоритмы имеют сложность, представляющую собой многочлен заданной степени, не зависящей от входных данных:

О(n * m), O(n²), O(n³) и т.д.

Все до сих пор изученные нами алгоритмы относятся к классу Р-задач: полиномиальные алгоритмы.

Есть задачи, которые по своей природе имеют экспоненциальную сложность порядка Aⁿ, где A — константа или полином от n. Это задачи, в которых требуется построить все подмножества данного множества, все клики (полные подграфы) данного графа и т.д. Число ответов в этих задачах уже само по себе экспоненциально, поэтому только их перечисление потребует экспоненциальное число шагов. Эти алгоритмы относятся к классу Е-задач: экспоненциальные алгоритмы.

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

Вот неполный список таких задач:

Ÿ Решение систем уравнений в целых числах.

Ÿ Определение гамильтонова цикла.

Ÿ Составление расписаний и раскрасок.

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

Ÿ Оптимизация пути коммивояжера через сеть городов.

Ÿ Отбор файлов при запросе в информационный банк данных для получения информации с наименьшей стоимостью.

Ÿ Размещение обслуживающих центров для максимального числа клиентов при минимальном числе центров.

Ÿ Оптимальная загрузка емкости, оптимальный раскрой.

Ÿ Диагностика (болезни, поломки).

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

Ÿ упорядочение операций;

Ÿ размещение персонала;

Ÿ оптимизация перевозок;

Ÿ управление производством;

Ÿ проектирование в области электроники.

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

Назовем его  класс NP-задач: недетерминированные полиномиальные задачи.

1. Для небольших n экспоненциальный алгоритм часто более эффективен, чем полиномиальный.
2. Для реальных задач с уточненными данными всегда можно построить полиномиальный алгоритм. Единственное, что утверждает теория — не существует единого полиномиального алгоритма для общего случая.

Если все же постановка задачи остается из класса NP, можно поискать для нее приближенный полиномиальный алгоритм

1. Условие задачи

 

7. УПАКОВКА В  КОНТЕЙНЕРЫ

УСЛОВИЕ. Заданы конечное множество A и размеры s(a) Є [0, 1] каждого предмета.

ВОПРОС. Найти такое разбиение множества A на непересекающиеся

A₁, A₂, …, A_k, чтобы сумма размеров предметов в каждом A_i не превосходила 1 и k было минимальным.

2. Решение задачи

В настоящей статье рассматривается  одна из таких задач – задача упаковки в контейнер. В общем  случае, задача упаковки в контейнер  заключается в упаковке объектов предопределенной формы в конечное число контейнеров предопределенной формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объем объектов (которые упаковывают

1. Допустимое решение любая упаковка;

   а) Все предметы упакованы;

   б) Сумма размеров предметов  в любом контейнере ≤1;

2. Оптимальное решение допустим  решение у которого количество  использованных контейнеров минимально, упаковка в минимальное число  контейнеров.

Целевая функция: Количество контейнеров.

Ограничение: Условие допустимости упаковки.

Сумма размеров предметов в контейнере больше или равно вместимости  контейнера.

3. Листинг программы на С++

Далее представим код программы  на языке С++.

1. Точный алгоритм

 

#include <vcl.h>

#pragma hdrstop

#include<iostream.h>

 

#pragma argsused

//предмет -> контейнер -> упаковка (упаковка - это разные вариации  контейнеров и предметов, нам  надо найти такую, чтобы там  было мин.число контейнеров

const N=6;   // число предметов

float A[N+1]={0,0.1, 0.2, 0.3, 0.7, 0.8, 0.9}, //размеры предметов

V[N];    //заполненность контейнеров

int Box,  // кол-во контейнеров в текущей упаковке

OptBox,   //кол-во контейнеров в оптимальной упаковке

Cont[N],   //текущая упаковка

OptCont[N];  //оптимальная упаковка (ее как раз надо найти)

 

void pack(int i)

{ int eps=A[i]*0.1;   //некоторое маленькое число (его можно считать = 0)

for (int j=1; j <= N; j++) { //перебираем контейнеры

if (V[j]<=eps && (Box+1)>=OptBox) break;  // если контейнер j пуст и кол-во контейнеров в текущей упаковке уже превышает оптимальное кол-во, то выходим

if (j>1&&V[j-1]<=eps) break;  //если контейнер не 1 и предыдущий контейнер пустой то выходим

if (V[j]+A[i]<=1+eps) { //если заполненость контейнера + размер предмета меньше 1 (т.е туда можно положить предмет)

int B=Box;   //в В записываем кол-во кол-во контейнеров в текущей упаковке

if (V[j]<=eps) Box+=1;  // если пустой, то увеличиваем кол-во контейнеров в этой упаковке на 1

 V[j]+=A[i];     //заполняем j контейнер на объем i предмета

Cont[i]=j;     //предмет i помещаем   в j контейнер

if (i<N) pack(i+1);  //если текущий предмет не последний, то вызываем рекурсию и пытаемся упаковать след предмет

else   //если нет, то

{

OptBox=Box;     //в оптим присваиваем текущее кол-во контейнеров в упаковке

for (int k = 1; k <= N; k++) OptCont[k]=Cont[k]; //в оптимальную упаковку = текущую упаковку

}

Box=B;        //возвращаем старое старое значение контейнеров в упаковке

Cont[i]=0;    //выкидываем текущий предмет

V[j]-=A[i];   //вычитаем объем текущего предмета

}

    }

}

int main(int argc, char* argv[])

{

for (int i = 1; i <= N; i++) {

    V[i]=0;                    // все контейнеры очищаем

Cont[i]=0;                 //все предметы никуда не помещены (лежат в сторонке)

OptCont[i]=i;             // оптимальное кол-во контейнеров в упаковке = N (тут чуть неуверен)

          }

OptBox=N;            //пока оптимально поместить каждый предмет в свой контейнер)

Cont[1]=1;          //первый предмет упаковываем в 1 вагон

 V[1]=A[1];       // увеличиваем заполненность 1го контейнера на размер 1го предмета

 Box=1;           //кол-во контейнеров в текущей упаковке =1

pack(2);          //упаковываем второй предмет

for (int i = 1; i <= N; i++) cout<<OptCont[i]<<" ";  //вывод оптимальной упаковки  (ответ)

cin.get();cin.get();

return 0;

}

2. «Жадный» алгоритм

Решим исходную задачу «жадным» алгоритмом. Данный алгоритм будет по вычислительной сложности полиномиальным. Требуется упаковать предметы в минимальное число контейнеров. В произвольном порядке упаковываем предметы по следующему правилу. Первый предмет помещаем в первый контейнер. На k-м шаге пытаемся поместить k-й предмет в текущий контейнер. Если предмет входит, то помещаем его и переходим к следующему шагу, иначе помещаем предмет в новый контейнер.

АЛГОРИТМ {задачи о упаковке в контейнерах}

Глобальные переменные :

N – число предметов(и контейнеров );

А [1…n] – размер предмета;

В [1…n] – заполнено контейнеров;

Cont [1…n] – текущая упаковка;

Cont [i] – номер контейнера в котором упакован i предмет;

Opt cont [1…n] – оптимальная упаковка;

Box – число использованных контейнеров в текущей упаковке;

Opt Box – число контейнеров оптимальной упаковке;

Можно фиксировать предмет и  перебирать контейнер поисках допустимого. Будем фиксировать i предмет и искать допустимый контейнер. Пока i предмет не упакован нельзя упаковать (i+1).

Procedure Pack (i);{покуем i предмет}

Begin

   for j:=1 to N do {перебираем контейнер}

if j-й контейнер допустим then

Begin

Покуем i-й предмет в j-й контейнер;

if i:=N then {нашли новое решение}

if новое решение оптимальное

Begin

Opt Box:= Box;

Opt Cont := Cont;

End.

Else Pack (i+1);

{возврат}

Вынимаем i-й предмет из j-го контейнера.

End;

End;

   End;{Pack}

 

 

 

 

 

Переписываем Pack подробно.

Procedure Pack (i);

Begin

 for j:=1 to N do

Begin

if (V[j] ≤ eps) and (Box +1≥ Opt Box) then break;

if (j>1) and (V[j-1] ≤ eps ) then break;

if V[j] + A[i] ≤1+ eps then // обычная проверка

 Begin

Bi = Box;

if V[j] ≤ eps then Box := Box +1;

V[j]:= V[j] +A[j]; Cont [i]:=j;

i<N then pack (i+1)

else begin

for k:=1 to n do Opt Cont [k] := Cont [k];

Opt Box := Box ;

End

{Возврат}

V[j] := V[j]-A[i];

Con [i] := 0

Box := B;

End;

   End;

End;{Pack}

Главная программа.

Begin{main}

   for j:= 1 do N V[j]:=0;

for i:=1 to N Cont [i]:=0;

Cont [1]:=1; V[1]:= A[1]; Box :=1;{начальная оптимальная упаковка }

for i:=1 to N do Opt Cont [i] := i;

Opt Box := N;

Pack(2);

Печать оптимальной упаковки

End.

4. Результаты работы программы

2 примера 

«Хороший» - точный и приближенный работают одинаково;

«Плохой» - точный и приближенный выдают разные решение;

Заключение

Мы рассмотрели задачу из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».

Библиографический список

1) В.Е. Торчинский С.И. Файнштейн Структуры и алгоритмы обработки данных на ЭВМ–Магнитогорск 2005.