Лабораторная 6

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

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

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

Пример задачи

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

Next-Fit Decreasing Height

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

First-Fit Decreasing Height

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

Best-Fit Decreasing Height

2

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

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

3

ПРАКТИЧЕСКАЯ ЧАСТЬ

1) Алгоритм NFDN

Рисунок 1 - Полный вывод программы для алгоритма NFDH

На рисунке 1 продемонстрирован полный вывод программы для алгоритма NFDH. Первое значение – порядковый номер, второе – текущая высота, дальнейшие значения – список объектов, входящих в данный ряд (их ширина), затем значение незаполненной ширины.

2) Алгоритм FFDN

Рисунок 2 - Полный вывод программы для алгоритма FFDH

На рисунке 2 продемонстрирован полный вывод программы для алгоритма FFDH. Первое значение – порядковый номер, второе – текущая высота, дальнейшие значения – список объектов, входящих в данный ряд (их ширина), затем значение незаполненной ширины.

5

ИСХОДНЫЙ КОД ПРОГРАММЫ

#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std;

struct block { int width; int height;

};

struct L {

int width; int height;

vector<int> array_of_bloks;

};

bool blocks_compare(block a, block b) { return (a.height > b.height);

}

6

void show_vector(vector<block> a) {

for (vector<block>::iterator i = a.begin(); i != a.end(); i++) cout << i->height << " " << i->width << endl;

}

void Next_Fit_Decreasing_Height(vector<block> list, int number, int backpack, int pointer, int *level, int step) { *level += list[pointer].height;

cout << step << "|Height = " << *level << "|Blocks: "; for (size_t i = pointer; i < number; i++) {

if (backpack - list[i].width >= 0) { backpack -= list[i].width;

cout << list[i].width << " "; } else {

cout << "|Remainder = " << backpack; cout << endl;

backpack = 1000;

Next_Fit_Decreasing_Height(list, number, backpack, i, level, step + 1); return;

}

}

cout << "|Remainder = " << backpack;

7

void First_Fit_Decreasing_Height(vector<block> list, int number, vector<L> LVL, int pointer, int *level, int *max_level)

{

*level += list[pointer].height; LVL[*max_level - 1].height = *level; bool flag;

for (size_t i = pointer; i < number; i++) { flag = false;

for (size_t j = 0; j < *max_level; j++) {

if (LVL[j].width - list[i].width >= 0) { LVL[j].width -= list[i].width; LVL[j].array_of_bloks.push_back(list[i].width); flag = true;

break;

}

}

if (!flag) { *max_level += 1;

LVL.resize(*max_level);

LVL[*max_level - 1].width = 1000;

First_Fit_Decreasing_Height(list, number, LVL, i, level, max_level);

8

return;

}

}

for (size_t i = 0; i < *max_level; i++) {

cout << i << "|Height = " << LVL[i].height << "|Blocks: "; for (size_t j = 0; j < LVL[i].array_of_bloks.size(); j++) {

cout << LVL[i].array_of_bloks[j] << " ";

}

int main() { ifstream file;

file.open("lab6.txt");

int number = 133, backpack = 1000, level = 0, max_level = 1; vector<block> list_of_blocks(133);

vector<L> LVL(1); LVL[0].width = 1000;

for (size_t i = 0; i < number; i++) {

9

file >> list_of_blocks[i].width; file >> list_of_blocks[i].height;

}

sort(list_of_blocks.begin(), list_of_blocks.end(), blocks_compare); //show_vector(list_of_blocks);

Next_Fit_Decreasing_Height(list_of_blocks, number, backpack, 0, &level, 0); level = 0;

First_Fit_Decreasing_Height(list_of_blocks, number, LVL, 0, &level, &max_level); return 0;

}

10