Pull to refresh

Про двумерную упаковку: offline алгоритмы

Algorithms *
Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?


Читать дальше →
Total votes 33: ↑33 and ↓0 +33
Views 56K
Comments 14

Упаковка в контейнеры (bin packing) при помощи генетического алгоритма

Algorithms *
Доброго времени суток, коллеги.
Этой статьей я продолжаю цикл посвященный EvoJ — Java фреймворку для решения задач генетическим алгоритмом.
В своей предыдущей заметке я познакомил читателей Хабра с основными принципами работы с EvoJ.

Сегодня мы рассмотрим, как при помощи EvoJ можно решить задачу упаковки в контейнеры.
Читать дальше →
Total votes 25: ↑24 and ↓1 +23
Views 16K
Comments 4

Про двумерную упаковку: online алгоритмы

Algorithms *
Это продолжение поста про оффлайн алгоритмы упаковки.

Суть задачи: имеем полубесконечную полосу — как в тетрисе, только без game over'а, и конечный набор прямоугольников. Данные о прямоугольниках поступают в режиме реального времени; каждый новый прямоугольник необходимо немедленно разместить и больше не двигать с места. Цель — минимизировать общую высоту упакованных прямоугольников.
Это online-вариация задачи об упаковке прямоугольников в полуограниченную полосу (2 Dimensional Strip Packing, 2DSP).

Чуть больше теоретических сведений можно найти в предыдущей статье, а пока, без лишних слов, перейдем к алгоритмам.
Читать дальше →
Total votes 42: ↑39 and ↓3 +36
Views 27K
Comments 14

Дробление непрерывного потока данных на структурные единицы

Network technologies *
Sandbox


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

Такие задачи возникают, к примеру, при передаче телеметрии и для управления удаленным оборудованием. С одной стороны обычно стоит простейший микроконтроллер, с другой стороны стоит компьютер. Связь между ними может осуществляться по старому, доброму RS232. Хотя бывает и сложнее, например, выход микроконтроллера UART преобразуется в 802.11b, затем идет распространение радиосигнала до радиомачты и в сервер приходит Ethernet.

Если интересен мой велосипед на эту тему, добро пожаловать под кат.
Читать дальше →
Total votes 8: ↑6 and ↓2 +4
Views 8.3K
Comments 13

Оптимизация размещения виртуальных машин по серверам

High performance *Virtualization *Server optimization *Cloud computing *
Sandbox
Какое-то время назад один мой коллега рассказал, что место в ДЦ кончается, сервера ставить больше некуда, а нагрузка растет и непонятно, что делать, и наверно придется все имеющиеся сервера поменять на более мощные.

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

Для продвинутых сразу скажу, что в этой статье речь пойдет про bin packing, а остальным, кто хочет узнать, как с помощью относительно несложных расчетов сэкономить до 30% серверных ресурсов, добро пожаловать под кат.
Читать дальше →
Total votes 11: ↑11 and ↓0 +11
Views 8.8K
Comments 19