Задача на оптимизацию, реквестирую умных ананасов в тред, которые знакомы с алгоритмами.Есть поле, на котом есть набор фигур, которые можно двигать и крутить на 90 градусов. Известны координаты сторон этих фигур (или координаты вершин, не важно), ну и соответственно их площадь тоже известна. Задача разместить фигуры таким образом, чтобы площадь оболочки которая их описывает была наименьшей.Я знаю, что задача нетривиальная, но на нее наверняка есть алгоритм который я не могу нагуглить и который наверняка знает какой-то местный студент. Бампать буду до конца.
Генетика это хорошо, оставлю его как вариант, но это очень долго а алгоритм полюбому должен существовать, это наверняка задача уровня упаковки рюкзака.Поэтому бамп
На самом деле это даже для двух фигур с ебаными поверхностями не очень просто придумать. Реши сначала эту задачу, думаю общая из нее будет довольно просто получаться.
>>212385459Генетический алгоритм. Там вариаций масса его, но в целом это должно быть как-то так: фигуры выкладываются на стол, считаются потери площади, и делается это n раз. Берутся годные варианты (где потери меньше всего), некоторые элементы фиксируются, некоторые меняются, снова считаются потери, снова берутся лучшие. Через букву тучу итераций находим наилучший вариант, который даёт наименьшие потери.
>>212385773> думаю общая из нее будет довольно просто получатьсяНет лол, это NP задача частное решение которого очень простое, но общее нетривиально.
>>212385722Иди геометрию учи. И вообще тут 12 элементов , то есть 12!, Плюс ещё 2д пространство, то есть 12!*2. И выходит примерно 958,003,200 комбинации расстановки этой хуйнии как минимум 16 из них будут самым минимальным периметром. Вывод иди учи производные, и возвращайся когда решишь.
>>212385931Я эти фигуры рандомно в фотошопе накидал для примера, их может быть дохуя, а может быть пять.
Довольно много на колене сделанных раскладчиков для всяких плоттеров и прочей ебанины с ЧПУ, поэтому думаю вполне реально>>212385935
>>212385722>задача уровня упаковки рюкзакаАХахах блять np полную задачу пихать сукаЕсли ты конечно не о разложение числа на подчисла с которых можно его собрать
>>212385931Ебач, ты даже две фигуры можешь расположить бесконечным числом способов, а если они со всякими ебаными выемками (т.к. выпуклый тут только прямоугольник), то зашивайся.
>>212385931>>212385975И ещё, на решение этой задачи потребуется 10мин обычного компьютера, только нужно написать алгоритм (программу) и всё.Там можно использовать метод провидения, то есть подставить первое несколько фигур на своё усмотрение.
>>212386070Воооооооооо вот это уже ближе. Благодарю анон, ты меня наставил на путь, теперь я хоть знаю по каким ключевым словам гуглить.
>>212386125Ебач, во-первых плоскость у тебя ограничена(10класс), во-вторых у тебя есть количество и значение этих фигур,и а третьих ты не ахуел ли, тебе тут советы дают, акты выебываешся.
>>212386286Кому мне, маня? Хуй соси, губой тряси, советчик. Плоскость у него ограничена, пиздец вообще, ты в 10м классе видимо уже спайсуху хуярил.
Ну кто-то про рюкзак упомянул. Так во, дп это решается. Остаётся только жадина/математика. Дп это не решится, ибо чтобы знать, можем ли мы поместить фигуру на заданную сторону, придётся дополнительно хранить маску этой стороны. А так как разность между максимальной высотой и минимальной на этой стороне больше еденицы, то это уже даже не двоичная маска будет. Что делает сложность n макс_разность ^ (4n) что не лучше ( а мб и хуже полного перебора) на таких числах. Так что решай математикой или перебором (жадный тоже не получится).
>>212386501У тебя здесь явно не генетический алгорит, чесли за 30 решается такая задача. Значит как я и думал есть алгоритм. Я сейчас усиленно гуглю доклады и статью на тему чпу.
>>212386501Если это какая-нибудь расчетка или диплом - я сильно сомневаюсь, что ему можно использовать йоба-решения из коробки
>>212386485Ебать ты тупой. На тебе теорему.Есть точки принадлежащие даной плоскости, и не принадлежащие ей. И обратно: есть плоскость принадлежащие точке, и не принадлежащие ей. Точки твои это-n угольники, и хуельники Харкнул безграмотности в ебало
>>212386595По большей части приоритизация элементов бОльшей площади + условия с какой стороны начинать заполнять. Ещё немаловажный именно для ЧПУ элемент помимо % использования ресурса - оптимизация длины маршрута.Судя по тому, что ты сам выбираешь в большинстве таких хуевин количество попыток, никаких эволюций тут нет
>>212386959Да хуй знать вас!Короче вот пример того как решить, наверху все сказали пиздуй в матан, или можешь искать в Гугле, если найдешь скинь сюда, ну или трехд создай
>>212387056Ты случайно не оп вчерашнего треда про продавщицу товара, из за которой ты боишься туда ходить?
Все, мои поиски увенчались успехом, я нашел и демку и алгоритмы на гитхабе.https://svgnest.comВсем спасибо, особенно тем кто сказал про чпу.
>>212387267Это не ты ли тот чел, который ввёл себе печеньку внутривенно?А то мне кажется что ты такой же человек как и он.
>>212387424Точного решения не может быть. Можно только перебрать кучу вариантов и отобрать из них самое удачное, но не факт, что это будет лучшее.
>>212385215 (OP)Задача разместить фигуры таким образом, чтобы площадь оболочки которая их описывает была наименьшей.Граничные условия заданы не корректно. Оболочка какой формы? Прямоугольной, квадрат, круг, правильный n-угольник?
>>212387909Самое очевидное, что мне пришло в голову - посчитать кол-во единиц в каждом столбе. Если бы это была функция, я бы помог
>>212385215 (OP)Аноны уже сказали. Это NP полная задачаhttps://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0
>>212385215 (OP)1. Вычисляешь площадь фигур.2. Берёшь фигуру с наибольшей площадью и с соотношением длины и ширины наиболее близким к 1.3. Ставишь фигуру как можно ближе к началу системы отсчёта.4. Моделируешь все случаи постановки и вращения фигуры на поле.5. Выбираешь тот вариант, где оставшаяся площадь наибольшая.6. Отметаешь эту фигуру из множества доступных7. Записываешь этот шаг, позволяя к нему вернуться или его отметить.8. Вернуться к шагу 2.Дерзай, анонМимо гум
>>212390132кривофикс*5. ...где в отсечённой части можно поместить как можно больше фигур/поместить фигуру (..?)А вот тут просчёт
>>212385215 (OP)брутфорспревращаешь в граф где фигурка это нода а соединяя их создаёшь ребросоединять фигуры есть смысл только угол к углуи буртфорсь какой угол с каким соединить можно образуя новые фигуры
