|
Продолжение задачи про четыре четверти http://math.hashcode.ru/questions/21046 Круг радиуса 1 разделили двумя перпендикулярными диаметрами на четыре одинаковых "дольки". задан 4 Сен '13 16:32 
behemothus |
|
Вот ссылка на известный мне ресурс, в котором разбирается целая серия таких задач. Берётся $%n$% секторов единичного круга, каждый из которых составляет $%1/m$% от площади круга, и далее приводятся известные на данный момент "рекордные" конфигурации. Предыдущая задача про "четыре четверти" -- это случай $%n=4$%, $%m=4$%. У меня при анализе конкретного расположения (оно там есть на рисунке) получалось некое значение, выражаемое через корень уравнения пятой степени. Является ли само такое расположение оптимальным, я не знаю. Очень часто в задачах комбинаторной геометрии бывают известны только оценки, хотя иногда удаётся доказать, что найденная конфигурация является "рекордной". По идее, для всех задач такого типа есть алгоритм, но он при большом количестве параметров не является практически пригодным. отвечен 4 Сен '13 17:04 
falcao Алгоритм для чего? Решения перебором? Почкм у них тогда такое плохое решение для нашего случая? На глаз видно, что у нас лучше. Хотя... Ладно, это несложно посчитать.
(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
|
|
Для продолжения обсуждения... отвечен 6 Сен '13 12:38
behemothus Алгоритм есть не у системы неравенств, а у соответствующей алгоритмической проблемы. На вход алгоритма подаётся система неравенств; на выходе выдаётся ответ о том, имеет ли она хотя бы одно решение. Это уже позволяет (на теоретическом уровне) решать какие-то достаточно сложные задачи. Например, узнать, каким числом единичных шаров можно окружить один такой же (известная историческая задача, где Ньютон и Грегори спорили об ответе: 12 или 13?). То, что при большом числе параметров описанный алгоритм малопригоден на практике, я упомянул сразу.
(6 Сен '13 14:12)
falcao
|