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

[Parkhomuk]

У меня получилось 0,305025 тело ограничивается только дугами окружностей.
Если допускается вариант когда тело может торчать из будки в процессе манипуляций при закрывании двери, то результат чуть лучше: 0,308448 в этом случае тело ограничивается дугами окружностей и прямыми

-- 14.01.2025, 15:58 --

Утундрий в сообщении #1669874 писал(а):

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

Для моего случая 0,308448 максимальный габарит 1,04858; минимальный 0,79728; угол между этими направлениями чуть меньше $\pi$

[sergey zhukov]

Parkhomuk
Похоже на то, что у меня?

[Parkhomuk]

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

Похоже на то, что у меня?

на мой взгляд не очень, позже сделаю картинку

[Padawan]

Padawan в сообщении #1669935 писал(а):

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

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

А лучше угол поворота двери тоже функцией от $t$ считать. Вполне возможно, что в некоторые моменты времени дверь выгодно временно в обратную сторону начать двигать.

[12d3]

Немного мыслей по аналитической стороне задачи.
Судя по всему, оптимальная фигура - в форме этакой буквы С, симметричная, и при проворачивании внешней стороной касается двух сторон квадрата, а внутренней касается двери. Если не вдоль всего пути, то хотя б около центральной части пути. Будем рассматривать все в системе координат, жестко связанной с фигурой, и чтоб ось ординат была осью симметрии. Тогда у нас квадрат каким-то образом проворачивается вокруг фигуры, и основание двери (там, где петли) движется по какой-то траектории, определяемой только внешней частью фигуры. Будем считать, что форма внешней части зафиксирована, а форма внутренней части варьируется. Из-за симметрии моржно рассматривать только половинку траектории.
Пусть у нас в системе координат фигуры основание двери движется по траектории $x = x(t),\, y = y(t)$, где $t$ - просто какой-то параметр. Например, в частном случае, когда внешняя сторона представляет собой дугу окружности, то основание двери будет двигаться по окружности $x = -b \sin(t), \, y = a + b \cos(t)$, но в общем случае траектория основания может оказаться какой угодно, хоть с самопересечениями (но надеюсь, без них обойдется). А угол наклона двери мы тоже запараметризуем $\varphi = \varphi(t)$, так что координаты подвижный конец двери будут двигаться по траектории $X(t) = x(t) + \sin(\varphi(t)),\,Y(t) = y(t) - \cos(\varphi(t))$. В первом приближении можно считать, что эта траектория не слишком дикая, и таким образом она же и будет задавать внутреннюю часть фигуры.
А теперь внимание вопрос. Мы хотим при заданных $x(t),\,y(t)$ найти функцию $\varphi(t)$, максимизирующую функционал $\displaystyle \int_0^{t_0} Y(t) dX(t)$, она же площадь под графиком. Краевые условия придумаем какие-нибудь, скажем, что $\varphi(0) = 0, \,\varphi(t_0) = \varphi_0$. Или вместо второго краевого условия задать $X(t_0) = x_0$. Не знаю пока что нужно, надо думать.
Так вот, я бросился в бой с шашкой наголо и пошел писать уравнения Эйлера-Лагранжа, но тут меня поджидал провал. У нас подынтегральная функция получается линейной по $\varphi'$, и никакого диффура не выходит, и никакой экстремальной траектории не выходит, и все определяется краевыми условиями (подсказал мне чатгпт, каюсь, давно учился, все позабыл). Что это может значить? Что нужно сразу поворачивать дверь до максимального угла, а потом двигать основание, или наоборот сначала подвигать основание до конца, а потом только повернуть дверь? Непонятно, нужна помощь.

[Утундрий]

Предлагаю заинтересовавшимся потренироваться на кошках. Пусть тело — отрезок. Какова его максимально допустимая длина при условии закрывания дверцы опосля впихивания означенного отрезка?

[Geen]

Утундрий в сообщении #1669975 писал(а):

Какова его максимально допустимая длина

Корень из двух.

[Утундрий]

Geen в сообщении #1669977 писал(а):

Корень из двух.

Нет, так как не закроется дверца.

[Padawan]

12d3
Если траектория основания двери $(x(t),y(t))$ известна, то, по-моему, внутренняя кривая должна быть огибающей окружностей $(x-x(t)) ^2+(y-y(t)) ^2=1$

[sergey zhukov]

Утундрий
Для отрезка максимальная длина 1. Поскольку 1 - очевидное решение, а все, что больше, нужно будет "втыкать по диагонали" и дверца точно не закроется.

[Padawan]

12d3 в сообщении #1669972 писал(а):

Мы хотим при заданных $x(t),\,y(t)$ найти функцию $\varphi(t)$, максимизирующую функционал $\displaystyle \int_0^{t_0} Y(t) dX(t)$

Вектор $(Y(t) -y(t), X(t) -x(t) ) $ должен быть перпендикулярен траектории $(x(t), y(t))$ (и направлен вверх, если $x'(t) >0$ и вниз, если $x'(t) <0$).

[Утундрий]

sergey zhukov
"Очевидное решение" здесь $2(\sqrt 2 -1)$. Потому что проходит при любом положении дверцы.

[sergey zhukov]

12d3
Как тут уже было сказано:

mihaild в сообщении #1669705 писал(а):

Напоминает задачу о перемещении дивана
(её мы тут точно не решим)

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

[A_I]

Кстати,

Цитата:

Учёные из института Вейцмана провели необычный эксперимент.

Они задумались, — кто быстрее справится с задачей: протащить Т-образную фигуру через пространство, разделённое на три камеры, соединённые узкими проходами — люди или муравьи?

Интересная деталь:
ни люди, ни муравьи заранее не знали строения лабиринта.

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

Результаты оказались неожиданными:
в ходе неоднократных групповых испытаний муравьи с разгромным преимуществом оставляли команды людей далеко позади, опережая их на порядок.

https://drive.google.com/file/d/115bmg-gYfyvynqROIk5UhXLMawiP10dI/view?usp=drivesdk

[sergey zhukov]

A_I
Смотря, как сравнивать по времени. Если сделать все это в наноразмере, то эта штучка даже за счет одного броуновского движения может за секунду проскочить.