Продолжение задачи про четыре четверти http://math.hashcode.ru/questions/21046

Круг радиуса 1 разделили двумя перпендикулярными диаметрами на четыре одинаковых "дольки".
В каком наименьшем квадрате можно расположить полученные фигуры без наложения?
Части можно поворачивать и они могут касаться друг друга и сторон квадрата.

задан 4 Сен '13 16:32

изменен 4 Сен '13 16:36

10|600 символов нужно символов осталось
0

Вот ссылка на известный мне ресурс, в котором разбирается целая серия таких задач. Берётся $%n$% секторов единичного круга, каждый из которых составляет $%1/m$% от площади круга, и далее приводятся известные на данный момент "рекордные" конфигурации. Предыдущая задача про "четыре четверти" -- это случай $%n=4$%, $%m=4$%. У меня при анализе конкретного расположения (оно там есть на рисунке) получалось некое значение, выражаемое через корень уравнения пятой степени. Является ли само такое расположение оптимальным, я не знаю. Очень часто в задачах комбинаторной геометрии бывают известны только оценки, хотя иногда удаётся доказать, что найденная конфигурация является "рекордной".

По идее, для всех задач такого типа есть алгоритм, но он при большом количестве параметров не является практически пригодным.

ссылка

отвечен 4 Сен '13 17:04

Алгоритм для чего? Решения перебором? Почкм у них тогда такое плохое решение для нашего случая? На глаз видно, что у нас лучше. Хотя... Ладно, это несложно посчитать.

(4 Сен '13 17:12) behemothus

С каждой четвертью круга можно связать координаты её центра, а также ещё один числовой параметр, описывающий угол её поворота (но без тригонометрии). Возникает 12 параметров. К ним добавляется ещё один: размер квадрата. Выписываются неравенства, выражающие тот факт, что части расположены как надо. Далее вопрос формулируется в терминах т.н. элементарной теории действительных чисел: существуют ли такие 13 чисел, что система неравенств имеет хотя бы одно решение. Эта теория алгоритмически разрешима по теореме Тарского, но алгоритм очень сложный и медленный. Какая конфигурация лучше, надо считать.

(4 Сен '13 17:25) falcao

так это система неравенств... Алгоритма как такового нет, кроме численного. Во всяком случае лет двадцать назад его не было. Я тогда занимался задачи "раскроя" листа на заготовки... Задача, конечно было посложнее, но суть та же. Ничего путного кроме простого перебора не предложили. Занимался этим, помнится, академик Рвачев из украинской АН.

(5 Сен '13 16:36) behemothus

Существование этого алгоритма доказано лет 50 назад. Называется это "разрешимость элементарной теории действительных чисел". Материал изложен в ряде учебников, его можно найти по словам "теорема Тарского - Зайденберга". Кстати говоря, я вчера проделал некоторые вычисления и сравнил две конструкции. Та, которая указана по ссылке, даёт квадрат со стороной $%1,9429...$% для круга единичного радиуса. Из решения @chameleon удалось извлечь величину $%(4\sqrt{3}+2\sqrt{2})/5$%, то есть около $%1,9513...$%.

(5 Сен '13 16:52) falcao

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

(5 Сен '13 20:03) behemothus

Маловато -- в каком смысле? Вы ожидали, что сторона уменьшенного квадрата будет ещё ближе к двум, или наоборот? Теорема Тарского показывает, как можно последовательно элиминировать кванторы в логических формулах. По типу того, как утверждение $$(\exists x)(x^2+px+q=0)$$ мы превращаем в неравенство $%p^2-4q\ge0$%, и квантор исчезает. Это алгоритм, применяя который к заданной формуле для квадрата со стороной $%a$%, мы в конце получим необходимые и достаточные алгебраические условия на $%a$%. При этом те значения переменных, описывающие конструкцию, получаются теми же способами.

(5 Сен '13 23:13) falcao

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

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

Маловато -- в каком смысле?

В смысле экономии. Я потом это посчитаю - сравню.

(6 Сен '13 12:33) behemothus
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Для продолжения обсуждения...

ссылка

отвечен 6 Сен '13 12:38

Алгоритм есть не у системы неравенств, а у соответствующей алгоритмической проблемы. На вход алгоритма подаётся система неравенств; на выходе выдаётся ответ о том, имеет ли она хотя бы одно решение. Это уже позволяет (на теоретическом уровне) решать какие-то достаточно сложные задачи. Например, узнать, каким числом единичных шаров можно окружить один такой же (известная историческая задача, где Ньютон и Грегори спорили об ответе: 12 или 13?). То, что при большом числе параметров описанный алгоритм малопригоден на практике, я упомянул сразу.

(6 Сен '13 14:12) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×2,325

задан
4 Сен '13 16:32

показан
796 раз

обновлен
6 Сен '13 14:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru