Да, всё-таки поступило уточнение, нельзя картинку повторно пропечатать на другом наборе красок.
Так что считаем, что это скорее ткацкий станок с нитями и каждое изделие должно быть целиком соткано на заправленном наборе нитей, (типа нельзя полотнище повторно воткнуть в станок и вплести в середину нити из другого набора :)

>банки представлены по убыванию рейтинга использования и
ну в экселе отсортировал

>нет ни одной банки, которая не используется вообще)....
а зачем они нужны? первое что делается - отбрасываются неиспользуемые краски и засчет этого уменьшается матрица
представь, что банок 100, как в исходной постановке, но 30 из них не используются вообще ни в одной картинке

>но есть вышеупомянутые хвосты (банки с 46 по 70 используются всего один раз) см. запрос
да, хвосты есть в данных

Тут мысль пришла с рекурсивным обходом дерева.

Берём картинку №1 и начинаем мёрджить её массив рекурсивно с остальными картинками.
Условие выхода из рекурсии - количество элементов в мёрдже >= 30

Итого при каждом выходе из рекурсии получаем набор красок (мёрдж), а картинки, покрываемые этим набором - это путь до узла.
По идее дерево получается кособокое (т.к. каждый узел имеет смысл складывать только со следующими по порядку) и условие выхода из рекурсии довольно быстро достигается (глубина дерева не оч большая)
То бишь до какого-то количества картинок будет работать даже быстро.

Потом отсортировать полученные наборы по количеству покрытых картинок - выкинуть эти картинки из списка.
Для оставшихся картинок повторить всё заново.

Ща попробую закодить весь этот бред, мож чего получится.

maytonПо поводу объема работ.

Думаю что алгоритм должен работать для пачки картинок.
Что такое пачка? Возможно это 1 рабочий цикл издательства.
Получили флешку с картинками. Пульнули ее в алгоритм.
Оптимизировали порядок. Отпечатали. Всё. Цикл закончен.

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

anvano, верно?

Да, именно так.

Я закодил уже первую часть своего алгоритма с рекурсией - вобщем для пачек до 30 штук канает, получается оч хорошо.
В районе 30 штук рекурсия длится около 3 минут.

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

В общем, допилил скрипт с рекурсивным алгоритмом для тестовых данных (25 штук) выполняется секунд 40.

За 4 перенастройки палитры можно распечатать все 25 картинок :)

Для 50 картинок Execution time уже 364.8032 сек. в 10 раз больше.

maytonanvano, делись софтом, хвастун!

Да какой там софт, обычный скрипт на PHP :)

maytonanvanoДля 50 картинок Execution time уже 364.8032 сек. в 10 раз больше.
50 картинок оптимизирует 6 минут?????

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

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

maytonanvanoДля 50 картинок Execution time уже 364.8032 сек. в 10 раз больше.
50 картинок оптимизирует 6 минут?????

Это язык интерпретируемый, плюс функции используются тяжелые ( array_merge, sort, array_unique) на каждой итерации.

Для 25 картинок там всего-лишь 240 тыс итераций, а оно целых 40 секунд их молотит. Это очень долго, согласен.

Простор для оптимизации алгоритма широк - можно заменить операции с массивами на какие-то битовые манипуляции, переписать всё на более низкоуровневом языке типа C++ - должно ускориться существенно.

Но всё равно, рекурсивный обход - сложность возрастает экспонециально (если не факториально) от количества элементов.

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

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