Метка «bin packing»

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

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

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

Если интересен мой велосипед на эту тему, добро пожаловать под кат.
Читать полностью »

Про двумерную упаковку: online алгоритмыЭто продолжение поста про оффлайн алгоритмы упаковки.

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

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

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

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

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

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

Читать полностью »

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

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

Постановка задачи

Если в двух словах, то задача упаковки в контейнеры ставится следущим образом: имеется набор контейнеров определенного объема, и набор предметов, которые в эти контейнеры требуется уложить (вЧитать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js