2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 18:29 
Заслуженный участник


24/08/12
1153
sergey zhukov в сообщении #1669764 писал(а):
Получается фигура, ограниченная тремя окружностями диаметрами, равными 1 и 2
Если не ошибся, площадь выходит $0.221485...$ Вдвое больше чем $(+\frac{7\pi-16}{64})\approx0.0936$ (это последнее выражение расчета для прежнего случая - верно? Как-то кажется больше чем десятая часть квадрата)

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 18:52 


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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 19:19 


18/11/18
895

(Оффтоп)

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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 20:23 


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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 20:25 
Заслуженный участник


24/08/12
1153
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}$; если абстрагироваться от проблемой "упирания кончиков"); понятно что при этом фигура выйдет разной (и тратить бОльшую часть поворота на малом угле раскрытия зазора двери - невыгодно).

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 23:06 


17/10/16
5315
manul91
Вариант с поворотом в середине не слишком оптимален. Если принять его за единицу, то вот этот вариант, подобранный руками, дает 1,14:
Изображение
Здесь пытаемся пропихнуть изначальный квадрат, причем все, что вылезает за границы или заметается дверью, отрезается.

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

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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 23:27 


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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 00:36 


05/09/16
12445
sergey zhukov
Слушайте вы прям мастер иллюстрирования и быстрого скетчинга. Браво!
У меня в голове примерно такая каринка была, но как реализовать...
Вот вас бы наверное взяли в эйрбас!
sergey zhukov в сообщении #1669834 писал(а):
вот этот вариант, подобранный руками, дает 1,14:

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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 01:22 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 02:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 03:39 
Заслуженный участник


24/08/12
1153
sergey zhukov в сообщении #1669834 писал(а):
Вариант с поворотом в середине не слишком оптимален. Если принять его за единицу, то вот этот вариант, подобранный руками, дает 1,14:
Это прям круто.
sergey zhukov в сообщении #1669834 писал(а):
Вообще, задача, конечно, не простая. Решение (если речь о конкретном способе пропихивания) дается координатами мгновенного центра вращения и угловой скоростью исходного квадрата, как функциями угла поворота двери. Т.е. это три скалярные функции. Слишком много вариантов, причем здесь вряд ли есть какой-то прием, который позволяет решить задачу "локально", типа "всегда вращай вокруг двери" или "пропихивай на максимальном зазоре" и т.д.
Нда. Что тут скажешь.
Не хочется верить что есть задача которая "решается" только методом тыка. Должна же быть хоть какая-то эмпирика.
Из каких соображений вы выбирали вручную центр вращения на каждом такте в последнем варианте?
sergey zhukov в сообщении #1669834 писал(а):
Я уже даже не уверен, что в оптимальном случае закрывание двери должно происходить монотонно.
Могу и ошибаться, но смотря на "обрубок" в последней анимации - есть вроде момент когда выгодно прикрыть дверь временно в обратном направлении. После того как дверь останавливается, через еще какое-то время плоская часть обрубка опирается в верхней стенки квадрата, вот этот момент.
Я думал про такую эвристику. Двигать дверь малыми фиксированными шажками. На каждом такте, "ощупать" что урезывает наименьшую часть из оставшегося обрубка, из трех возможных вариантов: придержать дверь как она есть (не двигать) а только завертеть фигуру, прикрыть дверь на один шаг и завертеть фигуру, открыть дверь на один шаг и завертеть фигуру. Сделать то что выгодней (как выбирать оптимальный центр вращения в каждом из случаев не знаю, можно "прощупать" по том же критерии). Хотя такой подход тоже локален (во времени), и даст только какой-то локальный минимум...

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 10:14 


17/10/16
5315
Вот вариант, который больше варианта "весь поворот в середине" на 1,25:
Изображение

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

Sender в сообщении #1669845 писал(а):
отрезать лишнее нижней стороной квадрата не нужно, ведь это открытый выход.

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

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

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

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

manul91 в сообщении #1669888 писал(а):
есть вроде момент когда выгодно прикрыть дверь временно в обратном направлении

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

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

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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 10:37 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 10:42 


17/10/16
5315
Padawan
$0.305$

 Профиль  
                  
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение14.01.2025, 12:42 
Заслуженный участник


13/12/05
4684
sergey zhukov в сообщении #1669834 писал(а):
Решение (если речь о конкретном способе пропихивания) дается координатами мгновенного центра вращения и угловой скоростью исходного квадрата, как функциями угла поворота двери.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: worm2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group