Группировка объектов по размерам.

[Vadim_PDF]

Предположим у нас есть 100 объектов разных размеров (50*90; 54*92; 150*160; 151*162 и т.д.)
есть допуск - допустим +/- 2 мм.
Необходимо сгруппировать их так, что бы было минимальное количество групп.
Я пока вижу только метод тупого перебора - брать первый объект за основу - и проверять каждый последующий на допуск, если подходит - перемещать из общего массива в массив - "Просчет 1, первый объект". Затем брать первый из оставшихся, и сравнивать с остальными оставшимися. - и так повторять пока ничего не останется.
Затем возвращаться к исходному массиву и сравнивать повторно, начиная со 2-го объекта. и т.д. В конце выбрать проход с минимальным количеством получившихся групп.
Короче, числодробилке работы хватит, но есть ли более оптимальный алгоритм, может что то из комбинаторики. Куда вообще копать?

P.s Для разъяснения: в примере размеров выше получается 3 группы 1-я 50*90, 2-я - 54*92 (54 в допуск к 50 не попадает) и 3-я (150*160 + 151*162)

 

[splxgf]

Можно все разместить в виде точек на плоскости и подобрать минимальное количество прямоугольников 4*4.
Эта задача проще оптимизируется имхо, и по крайней мере оптимальность решения наглядно проверяется.

 

[splxgf]

54 в допуск к 50 не попадает

допустим +/- 2 мм

Если добавить элемент на 52 мм, то уже попадать будет?

 

[Vadim_PDF]

да.. 52 уже попадает.
согласен.. в Excel втянул, создал график.. но мне бы программно алгоритм, как эти прямоугольники расставить.
Массив что ли многомерный сделать, х,у размеры, а внутри ссылка объект.
Но как потом проходить этот массив...

 

[splxgf]

Немного не понял, добавим в начальный список элемент 52*91.
При наличии этого элемента будет группа 52*91, 50*90, 54*92. А при отсутствии группировка распадается на две части 50*90 и 54*92?

 

[Vadim_PDF]

в идеале, желательно найти несуществующий виртуальный объект 52*91 - и от него сгруппировать 50*90 и 54*92.
Задачка не такая простая как кажется на первый взгляд. Поэтому и спрашиваю, про теорию. вдруг уже есть подобные алгоритмы кластеризации. Что то вроде wikipedia
Конечно, когда я за этот скриптик брался - думал по проще будет... Но, задача насущная решена, а это осталась идея, разминка для мозгов

 

[Eugenyus]

Может быть, тогда из файла настроек считывать список исходных размеров и допуски, а отдельной функцией перед запуском проверять, чтобы данные не "пересекались"?

 

[splxgf]

в идеале, желательно найти несуществующий виртуальный объект 52*91

Зачем искать несуществующий объект, ваши +/- 2 мм, превращаются в допуск 4 мм. Вывести все точки в двухмерный массив и обвести скопления точек квадратиками 4*4.
Конечно Нюансов больше чем при прямом переборе, ну тут уж как всегда скорость vs память.
Но зато открывается простор для других оптимизаций, к примеру при допуске 6 мм групп может быть на две меньше и так далее.
Ну или вбить сразу стоимость и будет оптимизироваться экономическая составляющая.

 

[_MBK_]

Не пойму, а чем, собственно, стандартные алгоритмы кластерного анализа не подходят? Это ж классическая задача и идентифицирована правильно. Если лениво реализовывать, сродни этой задаче, например, задача уменьшения цветов в палитре. Допустим, каждому прямоугольнику ставим в соответствии точку цветом (x,y,0). Затем преобразовываем полученное изображение в палитровое с размером палитры N. Значения цветов из этой палитры будут центрами N разных базовых групп прямоугольников.