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

[Утундрий]

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

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

Да, уж... Изрядно я затупил, когда вопрошал сие.

Оказывается (внезапно), что если немного подумать (а я немного подумал), то можно догадаться (я смог и догадался), что эта самая максимальная длина тупо равна ширине квадрата.

[miflin]

(Оффтоп)

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

эта самая максимальная длина тупо равна ширине квадрата.

На всякий случай -- за вычетом толщины отрезка. А может и двух толщин, чтобы дверь уж точно не заклинило.

[sergey zhukov]

Вот решение, в котором пропихиваемая фигура имеет площадь $0,313$ от исходного квадрата:

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

[manul91]

sergey zhukov
Как именно работает "алгоритм поиска"?

[sergey zhukov]

manul91
Да весьма примитивно, если честно. Заданы три кусочно линейные функции, описывающие движение. А алогоритм просто случайно меняет их параметры ( по 40 параметров на каждую) и движется в сторону улучшения, когда случайно находит что-то получше. Это даже не градиентный спуск.

[A_I]

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

Да весьма примитивно, если честно. Заданы три кусочно линейные функции, описывающие движение. А алогоритм просто случайно меняет их параметры ( по 40 параметров на каждую) и движется в сторону улучшения, когда случайно находит что-то получше. Это даже не градиентный спуск.

(Оффтоп)

Что-то мне кажется, что это "примитивно" работающее прошло бы "на ура" за успешно выполненное задание ..

[12d3]

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

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

Кстати, поизучал я эту задачку о перемещении дивана, и там оказалась довольно простая математика. Можно почитать здесь: https://arxiv.org/pdf/1606.08111. Там решаются линейные ОДУ второго порядка, и решения все замечательные, синусы, косинусы да квадратные трехчлены. Так что у меня есть надежда, что можно найти оптимальную фигуру для нашей задачи в явном виде.

[Sender]

Если говорить о диване, утверждается, что эту задачу таки решили, доказав оптимальность фигуры Гервера.
https://arxiv.org/abs/2411.19826