2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение12.01.2025, 21:45 
A_I
Вариант с наибольшей площадью будет тоже скорее всего ограничен дугами окружностей. Мой вариант можно чуть увеличить, скруглив угол в точке $G$, а вот насколько -- считать надо. И нет никакой уверенности, что это будет фигура наибольшей площади.

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение12.01.2025, 22:03 
Padawan в сообщении #1669697 писал(а):
Вот такую фигуру можно запихать: $BJHKLMFGIB$. Даже вырезал из бумаги и провращал внутри квадрата.

А точка B там точно не лишняя? Т.е. не $JHKLMFGIJ$?

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение12.01.2025, 22:03 
Аватара пользователя
Padawan, я так понимаю, Ваш вариант - это открыть дверь наполовину и пропихнуть с поворотом что получится?
Напоминает задачу о перемещении дивана.
(её мы тут точно не решим)

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение12.01.2025, 22:14 
mihaild
Более того, во время поворота дверцу тоже будем вращать

-- Пн янв 13, 2025 00:15:50 --

wrest
Этот кусочек ($BJI$) не мешает, поэтому пусть будет.

-- Пн янв 13, 2025 01:03:14 --

Padawan в сообщении #1669702 писал(а):
Мой вариант можно чуть увеличить, скруглив угол в точке $G$

Можно добавить дугу окружности радиуса $1-\frac{\sqrt 2}2$ с центром в точке $E$.

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

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 00:14 
Мне кажется, оптимальная фигура должна быть асимметричной, что-то в духе жирной запятой. И внешний обвод имеет не постоянную кривизну, а уменьшающуюся к хвостику, чтобы по мере пропихивания и закрытия дверцы лучше заполнять центральную часть квадрата... Хм, наверное, для начала можно задаться вопросом, какую самую длинную кривую можно так пропихнуть.

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 09:27 
Довольно очевидная оптимизация исходной фигуры (которая заметается закрывающейся дверцей) - это "поворот" одной ее половины вот так:
Изображение
Теряется желтая площадь ($\frac{4-\pi}{16}$), но приобретается красная ($\pi\frac{3}{64}$).
Изображение

Можно еще немного пожертвовать острыми кончиками (которые и так немного подрезаются в этом варианте, совсем чуть-чуть), чтобы увеличить степень поворота (в этом варианте угол красного сектора равен $67,5^\circ$). Это должно еще больше увеличить площадь.

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 09:40 
sergey zhukov
Сколько в итоге получается?

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 09:47 
Padawan
$(+\frac{7\pi-16}{64})$ (для единичного квадрата) минус из этого чуть-чуть по кончикам.

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 09:48 
Возможно, "протаскивать-и-поворачивать-вокруг-конца двери" фигуру нужно по чуть-чуть, по мере (и одновременно с) открыванием двери - это наверно даст еще лучший результат (чем просто поворот двери на полоборота, потом поворот фигуры, и наконец поворот двери до конца - как на картинке).
Правда "ограниченной дугами окружностей" такая фигура вряд ли будет....

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 10:01 
manul91
Да, я тоже так думаю. Я хотел рассмотреть общий вариант, но сначала решил попробовать этот частный.
Более общий вариант - неперерывный поворот фигуры в процессе "пропихивания". Проблема в том, что неизвестна траектория центра вращения фигуры.

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

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 10:10 
sergey zhukov в сообщении #1669739 писал(а):
Проблема в том, что неизвестна траектория центра вращения фигуры.
Как бы фигура вроде всегда должна поворачиваться вокруг конца двери (чтобы максимально утилизировать мгновенно-доступный зазор) - значит траектория "мгновенного центра вращения" совпадает с траекторию конца двери.
sergey zhukov в сообщении #1669739 писал(а):
Есть два простых варианта: центр вращения движется по стенкам будки ( фигура катается по стенкам без проскальзывания) и центр вращения находится на конце двери (вот эта картинка выше - частный случай второго варианта).
Первый "вариант" непонятно о чем. Разумеется фигура при "поворачивании" должна не выходить за стенок. "Без проскальзывания" - такого требования в условии вроде нет.

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 10:13 
manul91
Почему она должна поворачиваться вокруг конца двери? "Без проскальзывания" по двери - такого же условия тоже нет. В мгновенном зазоре есть две граничные точки, можно поворачивать фигуру вокруг каждой из них при " пропихивании".
Без проскальзывания по стенкам - это просто чтобы траектория центра вращения была известна. Поиск под фонарем. Понятно, что условия этого не оговаривают.

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 10:18 
sergey zhukov в сообщении #1669741 писал(а):
Почему она должна поворачиваться вокруг конца двери?
Интуитивно: ) чтобы максимально использовать мгновенно-доступный зазор. Центр вращения должен же быть где-нибудь, если фигура поворачивает не вокруг самой-внутренней точки зазора - меньше площади пролезет. Вроде.
Насчет "не проскальзывания" - я думаю проскальзывание по чему угодно не только допустимо но и желательно.

-- 13.01.2025, 11:32 --

sergey zhukov в сообщении #1669741 писал(а):
В мгновенном зазоре есть две граничные точки, можно поворачивать фигуру вокруг каждой из них при " пропихивании".
Какова будет "вторая граничная точка в мгновенном зазоре" при фиксированном раскрытии двери, конкретно?
Так по моему "зазор" - это с одной стороны точка - конец дверцы, с другой стороны - две противоположные стенки квадрата.
Как бы оно не было, поворот вокруг точки в которой фигура упирается в стенки исключает "проскальзывание" - но "проскальзывание" выглядит выигрышной стратегией, непонятно зачем его не использовать (вот в вашем примере на картинке проскальзывание есть как по конце двери так и по стенок). Имхо алгоритмически наверно чередовать открывание двери чуть-чуть еще (с проскальзыванием по контура фигуры), потом поворот фигуры вокруг конца двери (с проскальзыванием по стенкам), и потом повторить - както-так.
Да и чисто интуитивно по-бытовому, когда протискиваемся в таких условий, то поворот происходит вокруг внутренней части препятствия а "зад" скользит по стенках (проскальзывание - залог успеха). Лол : )))

 
 
 
 Re: Интересная алгоритмическая задачка от Airbus
Сообщение13.01.2025, 13:19 
Вот построение одного из вариантов решения, когда фигура вращается вокруг точки касания двери (без проскальзывания по двери). В данном случае скорость вращения выбрана постоянной, угол поворота равен углу открытия двери:
Изображение

Получается фигура, ограниченная тремя окружностями диаметрами, равными 1 и 2. Если выбрать другую зависимость скорости вращения фигуры от угла поворота двери, то можно получить другие решения (не круглые) . Какая из них максимизирует площадь - это вопрос. Вероятно, нужно вращать тем быстрее, чем шире зазор между дверью и стенками.

 
 
 [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group