Интересная алгоритмическая задачка от Airbus

[manul91]

sergey zhukov в сообщении #1669764 писал(а):

Получается фигура, ограниченная тремя окружностями диаметрами, равными 1 и 2

Если не ошибся, площадь выходит $0.221485...$ Вдвое больше чем $(+\frac{7\pi-16}{64})\approx0.0936$ (это последнее выражение расчета для прежнего случая - верно? Как-то кажется больше чем десятая часть квадрата)

[sergey zhukov]

manul91
Не, $\frac{7\pi-16}{64}$ - это добавка к площади, не заметаемой дверью. Т.е. насколько такой алгоритм прибавляет площади в сравнении с базовым "статическим" вариантом.

[A_I]

(Оффтоп)

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

[Mihaylo]

Я предлагаю искать численное решение как две кривые R0(angle) и R1(angle), которые определят форму фигуры.
R0 ограничивается только дверью, а R1 - только стенками будки. Это такое допущение.
Фигура должна перемещаться по часовой стрелке (если взять за основу предложенное выше графическое отображение), на каждом шаге максимизируя угол поворота.
Изначально кривые R0 и R1 заполняют всё отведённое пространство, но по мере касания двери и стенок будки должны пересчитываться (сокращаться).

[manul91]

sergey zhukov в сообщении #1669785 писал(а):

Т.е. насколько такой алгоритм прибавляет площади в сравнении с базовым "статическим" вариантом.

Т.е. $1 - \pi/4 + (7\pi - 16)/64\approx 0.308214$, заметно больше чем $0.221485...$ ("базовый вариант": $1 - \pi/4\approx0.214602$). Вроде потверждается интуиция что "поворот" лучше сосредотачивать при максимальном зазоре.
По этой логике первой вариант (где весь поворот происходит при максимальном зазоре) и должен выйти близко к максимальным. Из-за необходимости урезания кончиков, не совсем понятно... Не соображу, если поворот начнется чуть раньше максимального зазора, что будет с концами - больше (или меньше) их придется урезывать, или все то же самое?

(Оффтоп)

A_I в сообщении #1669786 писал(а):

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

Не знаю как там Airbus, но по моему задача далеко не решена... Так догадки одни. А должно быть ведь точное решение максимизирующее площадь (для которого можно и нужно доказать, что любое отклонение от него уменьшит площадь фигуры)

-- 13.01.2025, 21:33 --

Mihaylo в сообщении #1669794 писал(а):

Фигура должна перемещаться по часовой стрелке (если взять за основу предложенное выше графическое отображение), на каждом шаге максимизируя угол поворота.

Так вроде дело в том, что в любой позиции открытия двери, мы вольны истратить какой угодно поворот из того что осталось (полный поворот фигуры - такой как и у двери - $\frac{\pi}{2}$; если абстрагироваться от проблемой "упирания кончиков"); понятно что при этом фигура выйдет разной (и тратить бОльшую часть поворота на малом угле раскрытия зазора двери - невыгодно).

[sergey zhukov]

manul91
Вариант с поворотом в середине не слишком оптимален. Если принять его за единицу, то вот этот вариант, подобранный руками, дает 1,14:

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

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

Я уже даже не уверен, что в оптимальном случае закрывание двери должно происходить монотонно.

[Sender]

sergey zhukov, по-моему, в последнем варианте отрезать лишнее нижней стороной квадрата не нужно, ведь это открытый выход.

[wrest]

sergey zhukov
Слушайте вы прям мастер иллюстрирования и быстрого скетчинга. Браво!
У меня в голове примерно такая каринка была, но как реализовать...
Вот вас бы наверное взяли в эйрбас!

sergey zhukov в сообщении #1669834 писал(а):

вот этот вариант, подобранный руками, дает 1,14:

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

[mihaild]

sergey zhukov, впечатляет. А можете поделиться кодом? Попробую генетику накидать.

[Утундрий]

А кто-нибудь пробовал оценить максимальный габарит тела в этой задаче?

[manul91]

sergey zhukov в сообщении #1669834 писал(а):

Вариант с поворотом в середине не слишком оптимален. Если принять его за единицу, то вот этот вариант, подобранный руками, дает 1,14:

Это прям круто.

sergey zhukov в сообщении #1669834 писал(а):

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

Нда. Что тут скажешь.
Не хочется верить что есть задача которая "решается" только методом тыка. Должна же быть хоть какая-то эмпирика.
Из каких соображений вы выбирали вручную центр вращения на каждом такте в последнем варианте?

sergey zhukov в сообщении #1669834 писал(а):

Я уже даже не уверен, что в оптимальном случае закрывание двери должно происходить монотонно.

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

[sergey zhukov]

Вот вариант, который больше варианта "весь поворот в середине" на 1,25:


Вырез дверью получился довольно симметричным. Может это критерий оптимальности?

Sender в сообщении #1669845 писал(а):

отрезать лишнее нижней стороной квадрата не нужно, ведь это открытый выход.

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

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

wrest
Спасибо. Люблю картинки. Но вообще-то они не быстро получаются.

mihaild
Да я программист так себе. Это расчет в экселе. Причем самым примитивным и ресурсоемким методом: поле из большого числа точек, которое движется и поворачивается, и на каждом шаге проверяются граничные условия. Вышедшие за границы точки удаляются.

manul91 в сообщении #1669888 писал(а):

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

Я попробовал, но не особо. Это приводит к тому, что "завитушка" не опускается до нижнего края, и ее длина сокращается. Вообще я заметил, что оптимально, когда "завитушка" максимально длинная и касается всех стенок. Даже если она при этом не самая толстая. Вот в расчете выше я сделал так, чтобы "завитушка" не отходила от верхней и правой боковой стенки.

manul91 в сообщении #1669888 писал(а):

Из каких соображений вы выбирали вручную центр вращения на каждом такте в последнем варианте?

Да я даже не знаю, где там в точности центр вращения. Вообще она вращается вокруг точки касания двери, но я ее периодически руками "двигал" еще, так что там и проскальзывание тоже есть.

[Padawan]

sergey zhukov
В последнем варианте какая площадь фигуры получается, если площадь квадрата равна единице?

[sergey zhukov]

Padawan
$0.305$

[Padawan]

sergey zhukov в сообщении #1669834 писал(а):

Решение (если речь о конкретном способе пропихивания) дается координатами мгновенного центра вращения и угловой скоростью исходного квадрата, как функциями угла поворота двери.

Может проще координаты центра квадрата и угла его поворота как функции угла поворота двери?

В ряд Фурье их разложить по $\{\sin{(2n-1)t\}_{n=1}^\infty$ на отрезке $t\in[0, \pi/2}$ ($t$ - это угол поворота двери), и коэффициенты методами численной оптимизации подбирать.