Простые однопроходные эвристики

Размещено на http://www.allbest.ru/

Простые однопроходные эвристики для решения одномерной задачи покрытия

1. Постановка и математическая модель задачи

Постановка одномерной задачи максимального покрытия.

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

Для проблемы одномерного максимального покрытия имеем следующую задачу:

Задана: длинна L покрываемого материала (формы) и имеется m исходных элементов (деталей) заданной длинны li, и в заданном количестве bi, .

Требуется найти план покрытия максимального количества форм исходными деталями, т.е. найти матрицу А=[], компоненты которой указывают число i-х предметов j-ой упаковке и максимизирующую количество N покрытых форм:

, , ,

,

, .

Эта задача была сформулирована Е. Заком на встрече международной группы по интересам раскроя-упаковки (SICUP) в 2002 году.

На рисунках 1.4 и 1.5 показаны отличия между задачей одномерного раскроя и задачей покрытия:

Размещено на http://www.allbest.ru/

Графическое представление для задачи одномерного раскроя

Размещено на http://www.allbest.ru/

Графическое представление одномерной задачи максимального покрытия

2. Однопроходные простые эвристики

Рассмотрим суть однопроходных простых эвристик, на примере задачи упаковки.

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

Как правило, в обоих классах используются следующие основные стратегии выбора.

· Следующий подходящий (Next-Fit, NF). Первый предмет упаковывается в корзину №1. Каждый следующий предмет упаковывается в ту же корзину, если позволяет ее остаточная емкость. В противном случае он упаковывается в новую корзину. Он-лайн версия (NF) имеет временную сложность O(m), а версия офф-лайн (Next-Fit-Decreasing, NFD) занимает O (m*logm) времени из-за необходимости сортировки предметов.

Пример 2.4. В контейнере емкости L=100 требуется упаковать 7 предметов, веса которых заданы вектором w=(40, 9, 21, 37, 20, 53, 17).Определить с помощью алгоритма NF необходимое количество контейнеров для размещения всех предметов.

Определим вначале нижнюю границу . При этом резерв (неиспользованная вместимость) равен 100*2-97=3.

NF алгоритм. Будем укладывать предметы в заданном порядке, пользуясь стратегией «следующий подходящий». Для загрузки предметов потребуется 3 контейнера с планом загрузки ={(1; 2; 3) (4; 5) (6; 7)},

После загрузки 1-го контейнера предметами 1,2 и 3 остается свободная емкость, равная 30. Согласно стратегии NF следующим должен укладываться 4 предмет. Его вес равен 37 и в 1-й контейнер он не войдет. Во 2-м контейнере размещается 4-й и 5-й предметы, остается свободная емкость, равная 43. Следующий 6-й предмет размещается в 3-м контейнере. Там же размещается 7-й предмет. План загрузки ={(1; 2; 3) (4; 5) (6; 7)}.

покрытие раскрой эвристика структограмма

3. Метод решения, структограмма и пошаговое описание алгоритма

На входе мы имеем длину формы и длины деталей, которыми мы будем покрывать формы. Далее в зависимости от выбранной эвристики мы следуем алгоритмам и покрываем форму деталями, в последовательностях определенных выбранной эвристикой. На выходе мы получаем покрытые формы. Количество форм не ограничено, главное, чтобы все детали были использованы. И для каждой эвристики у нас получатся разные списки покрытий. В процессе анализа мы выберем наиболее удачное и оптималь-ное покрытие.

Входные данные: (W, m, , Эвристика)

Выходные данные: (N, , )

В зависимости от выбранной Эвристики упорядочить или не упорядочить длины деталей.

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

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

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

4. Листинг программы

#pragma once

#include «resource.h»

#include «Form_d.h»

kusok *c;

kusok *b;

kusok *m; // инициализация и заполнение масcива заготовок

list<mqueue> glist; // глобальный список контейнеров

double v;

namespace KA_2_4

{

using namespace System;

using namespace System: ComponentModel;

using namespace System: Collections;

using namespace System: Windows: Forms;

using namespace System: Data;

using namespace System: Drawing;

public ref class Form1: public System: Windows: Forms: Form

{

public:

Form1 (void)

{

InitializeComponent();

}

protected:

~Form1 ()

{

if (components)

{

delete components;

}

}

private: System: Void Form1_Load (System: Object^ sender, System: EventArgs^ e)

{

srand (unsigned(time(NULL)));

list_is_ready=0;

}

private: System: Void button1_Click (System: Object^ sender, System: EventArgs^ e)

{

list_is_ready=1;

switch(evr)

{

case0: {upakovka(m);

break;}

case 1: {

quick1 (b, num);

c=new kusok[num];

for (int i=0; i<num; i++)

c[i]=b[i];

for (int i=0; i<num/2; i++)

{

b [2*i]=c[i];

b [2*i+1]=c [num-i-1];

}

upakovka(b);

break;}

case 2: {quick1 (b, num);

c=new kusok[num];

for (int i=0; i<num; i++)

{c[i]=b[i];

}

switch(num)

{

case 20:

{

for (int i=0; i<18; i++)

{b[i]=c [i - (i/3)];

b [i+1]=c [i - (i/3)+1];

b [i+2]=c [num - ((i/3)+1)];

i=i+2;

}

b[18]=c[12];

b[19]=c[13];

break;}

case 50:

{

for (int i=0; i<48; i++)

{b[i]=c [i - (i/3)];

b [i+1]=c [i - (i/3)+1];

b [i+2]=c [num - (i/3) - 1];

i=i+2;

}

b[48]=c[32];

b[49]=c[33];

break;}

case 100:

{

for (int i=0; i<99; i++)

{b[i]=c [i - (i/3)];

b [i+1]=c [i - (i/3)+1];

b [i+2]=c [num - (i/3) - 1];

i=i+2;

}

b[99]=c[66];

break;}

}

upakovka(b);

break;}

case 3: {quick1 (b, num);

c=new kusok[num];

for (int i=0; i<num; i++)

{c[i]=b[i];

}

switch(num)

{

case 20:

{

for (int i=0; i<18; i++)

{b[i]=c [num - ((i/3)+1)];

b [i+1]=c [num - ((i/3)+2)];

b [i+2]=c [i - (i/3)];

i=i+2;}

b[18]=c[13];

b[19]=c[12];

break;}

case 50:

{

for (int i=0; i<48; i++)

{b[i]=c [num - ((i/3)+1)];

b [i+1]=c [num - ((i/3)+2)];

b [i+2]=c [i - (i/3)];

i=i+2;}

b[48]=c[33];

b[49]=c[32];

break;}

case 100:

{

for (int i=0; i<99; i++)

{b[i]=c [num - ((i/3)+1)];

b [i+1]=c [num - ((i/3)+2)];

b [i+2]=c [i - (i/3)];

i=i+2;}

b[99]=c[66];

break;}

}

upakovka(b);

break;}

case 4: {quick1 (b, num);

c=new kusok[num];

for (int i=0; i<num; i++)

{c[i]=b[i];

}

switch(num)

{

case 20:

{

for (int i=0; i<18; i++)

{b[i]=c [num - ((i/3)+1)];

b [i+1]=c [i - (i/3)];

b [i+2]=c [i - (i/3)+1];

i=i+2;}

b[18]=c[13];

b[19]=c[12];

break;}

case 50:

{

for (int i=0; i<48; i++)

{b[i]=c [num - ((i/3)+1)];

b [i+1]=c [i - (i/3)];

b [i+2]=c [i - (i/3)+1];

i=i+2;}

b[48]=c[33];

b[49]=c[32];

break;}

case 100:

{

for (int i=0; i<99; i++)

{b[i]=c [num - ((i/3)+1)];

b [i+1]=c [i - (i/3)];

b [i+2]=c [i - (i/3)+1];

i=i+2;}

b[99]=c[66];

break;}

}

upakovka(b);

break;}

case 5: {quick1 (b, num);

c=new kusok[num];

for (int i=0; i<num; i++)

{c[i]=b[i];

}

switch(num)

{

case 20:

{

for (int i=0; i<18; i++)

{

b[i]=c [num - ((2*i/3)+1)];

b [i+1]=c [num - ((2*i/3)+2)];

b [i+2]=c [i - (2*i/3)];

i=i+2;}

b[18]=c[7];

b[19]=c[6];

break;}

case 50:

{

for (int i=0; i<48; i++)

{b[i]=c [num - ((2*i/3)+1)];

b [i+1]=c [num - ((2*i/3)+2)];

b [i+2]=c [i - (2*i/3)];

i=i+2;}

b[48]=c[17];

b[49]=c[16];

break;}

case 100:

{for (int i=0; i<99; i++)

{b[i]=c [num - ((2*i/3)+1)];

b [i+1]=c [num - ((2*i/3)+2)];

b [i+2]=c [i - (2*i/3)];

i=i+2;}

b[99]=c[23];

break;}

}

upakovka(b);

break;}

case 6: {quick1 (b, num);

c=new kusok[num];

for (int i=0; i<num; i++)

{c[i]=b[i];

}

switch(num)

{

case 20:

{

for (int i=0; i<18; i++)

{b[i]=c [i - (i/3)];

b [i+1]=c [num - ((i/3)+1)];

b [i+2]=c [i - (i/3)+1];

i=i+2;}

b[18]=c[12];

b[19]=c[13];

break;}

case 50:

{

for (int i=0; i<48; i++)

{b[i]=c [i - (i/3)];

b [i+1]=c [num - ((i/3)+1)];

b [i+2]=c [i - (i/3)+1];

i=i+2;}

b[48]=c[32];

b[49]=c[33];

break;}

case 100:

{

for (int i=0; i<99; i++)

{b[i]=c [i - (i/3)];

b [i+1]=c [num - ((i/3)+1)];

b [i+2]=c [i - (i/3)+1];

i=i+2;}

b[99]=c[66];

break;}

}

upakovka(b);

break;}

}

this->Invalidate();

textBox1->Text=v. ToString();

}

void quick1 (kusok* a, int N)

{

int i = 0, j = N; // поставить указатели на исходные места

kusok temp, p;

p = a [N>>1]; // центральный элемент

 // процедура разделения

do {while (a[i].l < p.l) i++;

while (a[j].l > p.l) j -;

if (i <= j)

{

temp = a[i]; a[i] = a[j]; a[j] = temp;

i++; j -;

}

} while (i<=j);

 // рекурсивные вызовы, если есть, что сортировать

if (j > 0) quick1 (a, j);

if (N > i) quick1 (a+i, N-i);

}

void upakovka (kusok* m) // функция упаковки

{

while (! glist.empty())

glist.clear(); // очистка глобального списка

mqueue std_set; // стандартная очередь

std_set.len=con;

glist.push_back (std_set);

for (int j=0; j<num; j++)

{

if((glist.back().len)>=0)

{

glist.back().Q.push (m[j]);

glist.back().len-=m[j].l;

}

else

{

glist.push_back (std_set);

glist.back().Q.push (m[j]);

glist.back().len-=m[j].l;

}

}

}

private: System: Void Form1_Paint (System: Object^ sender, System: Windows: Forms: PaintEventArgs^ e) {

if (list_is_ready) // рисование стержней с заготовками (из списка)

{

int w=int (ClientSize. Width);

int h=int (ClientSize. Height);

array<Pen^>^ pens=gcnew array<Pen^>(2); // массив карандашей

pens[0]=gcnew Pen (Color: Green);

pens[1]=gcnew Pen (Color: Red);

Drawing: Font^shrift=gcnew System: Drawing: Font («Courier New», 10); // шрифт для строкового вывода

Drawing: Brush^pencil1=gcnew System: Drawing: SolidBrush (Color: Black); // крандаш для строкового вывода

Drawing: Brush^pencil2=gcnew System: Drawing: SolidBrush (Color: Blue);

Drawing: Point oxy (240,10); // точка начала для стержня

int dx=(w-400)/100;

int dy=(h-20)/(glist.size());

int n1=1, n2=1;

queue<kusok> bufer;

for (list<mqueue>:iterator i=glist.begin(); i!=glist.end(); i++)

{

e->Graphics->DrawString («L»+n1. ToString(), shrift, pencil1, oxy.X-10, oxy.Y);

e->Graphics->DrawLine (pens[0], oxy.X, oxy.Y, oxy.X+100*dx, oxy.Y);

while(! ((*i).Q.empty()))

{bufer.push((*i).Q.front());

oxy.X+=dx*(*i).Q.front().l/10;

e->Graphics->DrawLine (pens[1], oxy.X, oxy.Y-2, oxy.X, oxy.Y+2);

e->Graphics->DrawString («x»+(*i).Q.front().x. ToString(), shrift, pencil2, oxy.X, oxy.Y+2);

(*i).Q.pop();

}

while (! bufer.empty())

{(*i).Q.push (bufer.front());

bufer.pop();

}

oxy.X=240;

oxy.Y+=dy;

n1++;

}

oxy.X=20;

oxy.Y=60;

int k=1;

n1=(int) ceil((double) (h-60)/15.);

n2=(int) ceil((double) num/((double) n1));

for (int i=0; i<n2; i++)

{

for (int j=0; (j<n1)&&(k<=num); j++)

{

e->Graphics->DrawString («x»+b [k-1].x. To String()+ "="+b [k-1].l, shrift, pencil1, oxy.X-10, oxy.Y);

oxy.Y+=15;

k++;

}

oxy.Y=60;

oxy.X+=75;

}

}

}

private: System: Void button3_Click (System: Object^ sender, System: EventArgs^ e)

{

this->Invalidate();

}

private: System: Void button2_Click (System: Object^ sender, System: EventArgs^ e)

{

Close();

}

private: System: Void button4_Click (System: Object^ sender, System: EventArgs^ e)

{

Form_d^ SecondForm;

SecondForm=gcnew Form_d;

SecondForm->Show();

}

private: System: Void button5_Click (System: Object^ sender, System: EventArgs^ e)

{

m=new kusok[num];

v=0;

for (int i=0; i<num; i++)

{m[i].l=v1+rand()%(v2-v1); // случайное заполнение массива заготовок

m[i].x=i+1; // назначение номера заготовке

v=(v+m[i].l);

}

v=v/1000;

b=new kusok[num];

for (int i=0; i<num; i++)

{b[i].l=m[i].l;

b[i].x=i+1;

}

}

};

}

4. Описание параметров программы

Пользователь выбирает количество деталей(m), диапазон длины деталей и эвристику.

Далее генерируются длины деталей в заданном диапазоне.

Рассчитывается идеальное покрытие

И производится покрытие форм:

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

Для классов c большими размерами покрывающих деталей лучше работают эвристики NF и NFD (с сортировкой элементов по принципа LLS, LSS и SLS). Для остальных классов все эвристики равноценны между собой.

Размещено на Allbest.ru

...