:)
можно ли свести к теории графов задачу об
оптимальном расположении маленьких квадратиков х(i)
на большом квадрате х(0)?

Это вроде задача упаковки рюкзака.

(0) так задачу озвучь. Как минимум не понятны критерии оптимальности. У квадратиков есть вес?

брутфорси

(1) Причем здесь рюкзак?
Задача оптимального раскроя

(4) при чем здесь раскрой если ТС про упаковку?

(5) Где ты прочитал слово упаковка?
Я вот в (0) прочитал про маленькие и большие квадратики и это все, квадратики, замечу, а не кубики

:)
если взять квадратик как частный случай прямоугольника и мерность пространства = 2 то может и упаковка и рюкзака
зы
вес неважен

(0) Нет это задача раскроя

(8)+ Задачи раскроя не относятся к комми или рюкзаку

(9)  тьфу задача раскроя не относится к коммивояжеру, это рюкзак/ранец

(9)+ хотя должен уточнить что если раскрой производится разными инструментами то получается коммивояжер

(0) https://koha.library.nstu.ru/cgi-bin/koha/opac-search.pl?q=su:%22методы%20оптимизации%22

(7) Задача упаковки двухмерного рюкзак — это задача раскроя, но да, ничего не мешает называть эту задачу как угодно, например, задача поиска смысла во вселенной или задача максимизации изнасилования мозга окружающим

(7) Список вариантов задачи об упаковки рюкзака: https://ru.wikipedia.org/wiki/Список_задач_о_рюкзаке

(14) Не мешай человеку, у него свой глоссарий и свои инструменты

(15) Можно проще назвать: задача о комбинаторной оптимизации. Не ошибетесь.

(16) Не усложняй, просто задача

Но является ли это теорией графов, я наверняка не знаю. Теория графов это вроде подмножество комбинаторики.

(18) теория графов, это теория графов. при чем тут комбинаторика? комбинаторика вообще другой раздел математики...

(19) поиски по графу имеет комбинаторную размерность.

(15) :) не я же начал вводить новые термины

(20) :) тогда можно приплести высшую математику раздел матрицы и нео

(17) с ":)" есть только потребность рассказать, что нет просто задач

Так что является критерием оптимальности?

(24) Это часть задачи. Как обычно в жизни. :)

(24) наиболее вероятно критерием является вес пропорциональный площади квадратов, но ТС утверждает, что "вес неважен"

(0) Т.к. задача коммивояжера - NP полная задача, то свести можно. Только зачем?

(27) :) намекаешь что через матрицы проще?

(26) :) ну квадраты это я неточно выразился - прямоугольники т.е. критерий - периметр и площадь

(28) Сформулируйте задачу содержательно. Например, нужно материал размером ШхД нарезать на такие-то прямоугольники.
Или есть набор прямоугольников и полоса материала такой-то ширины. Нужно нарезать, минимизировав отходы. Такие задачи пытались решать с незапамятных времен.

(29) >> периметр и площадь
озвучь уже задачу.

:)
a(i) х b(i)-> а(0) х b(0)
оптимизация упаковки/раскроя/...

Наверное, прямоугольники можно еще и вращать (т.е. подходит b(i) x a(i))).
Попробуйте поискать в инете.
Делал похожее давно (неявный перебор методом ветвей и границ) для раскроя нестандартных кровельных элементов. Результат был не ахти.
Еще вопрос: размеры прямоугольников совсем свои для каждой задачи или более-менее стандартные?

(33) такую задачу даже запросом решали

(33) :) скажем так я упрости задачу - высота у всех одна- только вертикальное расположение
размеры в справочнике - могу тупо обработкой подобрать - их всего полтыщи
но хотелось красиво а то блин столько  в универе проходили а в 1с не пригодилось почти

(34) да еще и в 3D https://infostart.ru/1c/articles/267268/

(35) Верно ли понимаю, что нужно в прямоугольник заданных размеров накидать сколько можно прямоугольников (с одинаковой высотой) из массива, минимизировав отход?
Не понял насчет "...могу тупо обработкой подобрать" - подбирая по какому-то принципу?

(35) Статью в (36) имеет смысл глянуть, хотя в ней о сути алгоритма всего одна фраза. Для 2-мерного случая (особенно, если высота у всех одинаковая) жадный алгоритм может оказаться вполне приемлимым.
Попробуйте для своей задачи сформировать критерий упорядочивания.

(37) :)
да перебором
что-то типа пока сумма х(i)<х(0) цикл
потом +минимум по х(i+1)...х(к)

(39) Это похоже на жадный алгоритм в одномерном ранце (если сначала упорядочено по x(i) по убыванию).
Еще может быть важно, как будут кроить: может резать можно только на всю ширину (гильотина).

(40) :) можно по убыванию ... но еще есть подгруппы тематические ... прикину если не найду вариант в (12) и (14)

(41) (12) - это просто о методах оптимизации. Вряд ли найдете подходящее для Вашей задачи, но не вредно.
В (14) подойдет разве что мультипликативный рюкзак - если раскрой возможен только прямыми сплошными резами. В (14) собственно, только формализация, про методы ничего не сказано.
Вам скорее ближе задача раскроя (https://ru.wikipedia.org/wiki/Задача_раскроя).

(42) :) ну я с самого начала подозревал что хотя задача банальная вряд ли она формализована так как задача К.
зы
кстати а есть средства программной реализации решения?
там всего лишь нужно открыть изображение 0 и вставить туда изображение 1 в позицию [x;y]

(43) "... есть средства программной реализации решения" - решения чего? Вы задачу не сформулировали ни содержательно, ни формально.
Следующую фразу совсем не понял.

Средств для решения задач раскроя полно

(0) не думаю. граф это совокупность объектов (вершины) со связями между ними (ребра). а раскрой это комбинаторика или поиск с возвратом

(0) Похоже на Динамическое программирование - Dynamic Programming (DP)

(44) :) формулировок несколько
ты просто не понял

(45) :) программных ... например есть же dll под 1с для работы с изображением?

(49) Попросите решение из ссылки в (36). Зададите 3-й размер = 1 и вперед.

(50) :) да не я сам напишу думал может есть формализация алгоритма

(51) пока нет даже формализации задания...

(52) :)
ну если тебе будет проще вместе с (44) то формализации нет - есть примерное описание задачи
ну что мне маткад ставить чтобы создать формулу чтобы не было подобных постов?

(53) ну зачем маткад?
нужно просто нормально описывать. Типа:
Дано: есть заготовка - квадрат треугольной формы диаметром X*Y
Необходимо: разрезать на N кружков размерами V*W оптимальным способом.
резка производится ножом по всей длине заготовки
критерий оптимизации - минимальное количество резов вдоль длинной стороны квадрата...

" вдоль длинной стороны квадрата" - не подскажите, какая сторона у квадрата самая длинная?)

любой квадрат всегда можно разделить на три неравные половины

(56) у "квадрата треугольной формы диаметром X*Y" - каждая сторона всегда длиннее любой другой. по определению.

(54) Это прям надо записать - занимательная задача для ребёнка: квадрат треугольной формы с диаметром... нарезать кружочками... ножом вдоль длинной стороны! Это будет дома шоу!

(58) нож лучше убрать... будет кровопролитье

Да. "Квадрат треугольной произвольной формы, диаметром 30 на 60%, нарезали зелёными кружочками вдоль длинной стороны волнистыми линиями. Требуется найти останки квадрата... и выбросить в ведро(?)".. т.к. критерии оптимальности мы ещё не проходили.
Докручиваем задачу, пожалуйста...

(54) :) я согласился с обозначением задача раскроя условно - ничего резать не надо и точного критерия нет
это было общее описание задачи

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

(62) :) неважно для каких целей - в (7) все есть для формализации

:)
по факту технически не было нужды усложнять
простой проход после сортировки по размеру
(с учетом дискретности по одному измерению)
сводит задачу к 1 размерности
и процент брака будет около 5%
а если добавить второй проход
для учета остатков то 3.5%

:)
кстати насчет так сказать программного раскроя по схеме
в питоне есть библиотека pillow для работы с изображениями
и почти нормально отрабатывает скрипт но есть странный глюк
с ней работал кто-нить?