есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D.
Здравствуйте Bell, Вы писали:
B>есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D.
Одну, ту для которой d=D.
Другими словами, уточни, что ты понимаешь под
термином "вписать одну окружность в другую".
Здравствуйте yvb, Вы писали:
yvb>Здравствуйте Bell, Вы писали:
B>>есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D.
yvb>Одну, ту для которой d=D. yvb>Другими словами, уточни, что ты понимаешь под yvb>термином "вписать одну окружность в другую".
yvb>Юра.
если по-простому — пусть есть банка, в которую ложаться карандаши (например) . Так вот надо определить, сколько в эту банку можно напихать карандашей.
Здравствуйте Bell, Вы писали:
B>Здравствуйте yvb, Вы писали:
yvb>>Здравствуйте Bell, Вы писали:
B>>>есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D.
yvb>>Одну, ту для которой d=D. yvb>>Другими словами, уточни, что ты понимаешь под yvb>>термином "вписать одну окружность в другую".
yvb>>Юра.
B>если по-простому — пусть есть банка, в которую ложаться карандаши (например) . Так вот надо определить, сколько в эту банку можно напихать карандашей.
Вариант, не аналитический (а тебе какой нужен):
примерная модель самоупорядочевания:
— Берем большую окружность, размещаем и фиксируем ее на плоскости.
— Помещаем на самый верх, маленькую окружность c "весом m" и моделируем ее падение
под действием силы тяжести внутри большой окружности, пока она не примет устойчивое положениее.
— Берем вторую окружность и тоже самоне, учитывая все окружности находящиея внизу.
Если не лень можно поэксперентировать с моделью, например помещать окружности в центр большой,
и затем моделировать раскручивание большой окружности.
Здравствуйте Bell, Вы писали:
B>привет всем!
B>есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D.
Ну, готового решения я не знаю. Однако вот несколько мыслей:
1. Можно решить обратную задачу — найти минимальное D/d для N окружностей, такое, что круг диаметра D покрывает все окружности.
2. Как ее решать? Точное аналитическое решение, скорее всего, отсутствует.
3. Для случая большого N можно получить оценку следующим способом:
— берем коэффициент плотной упаковки (окружности заполняют плоскость гексагонально-симметричной сеткой, дырок столько же, сколько окружностей, площадь каждой дырки Sh=(r*r*Srqt(3))-3*1/6PI*r^2=Sqrt(3)*r^2-1/2Pi*r^2=So*(sqrt(3)-PI/2)/PI=So*k, где So — площадь кажной окружности.
— Поскольку каждая окружность занимает (k+1)So, то N окружностей займут N*(Sqrt(3)+PI/2)/PI*So;
— Таперича берем и строим окружность такого диаметра, площади которой будет достаточно:
R^2 = (r^2)*N(k+1);
— итого, R = r * Sqrt(N(k+1)).
— ясен пень, мы оптимисты. Это нижняя оценка диаметра. Насколько мы могли промахнуться? Верхняя оценка требуемой площади получится из следующих соображений: Вдоль большой окружности уместятся примерно R/r окружностей маленьких. Каждая из них может торчать максимум на половину своего диаметра, т.е. "не влезшая площадь" будет равна Sqrt(N(k+1))*PI*r^2/2. Погрешность площади растет как корень из N, а сама площадь — как N. То есть, относительная ошибка ~ N^(-0.5). Уже неплохо.
— Финальное уравнение принимает вид:
R^2=(r^2)(N(k+1))+Rr/2.
решаем его относительно N:
N = ((R/r)^2 — (R/2r))/(k+1)
для отношения R/r равного 10, N получится примерно 90. Погрешность у нас равна одной десятой... нда... То есть в 80 карандашей мы точно запихаем. Для R/r=100, получим примерно 8619 с погрешностью в один, примерно, процент.
Есть еще пара идей, как считать для случая малых отношений.
Ессно, мы тут программеры, так что надо написать программу, которая оптимально размещает окружности и строит диаметр. Уверен, что можно выполнить ее за время N*log(N). В хорошем случае за N.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте Sinclair, Вы писали:
S>Ессно, мы тут программеры, так что надо написать программу, которая оптимально размещает окружности и строит диаметр. Уверен, что можно выполнить ее за время N*log(N). В хорошем случае за N.
Боюсь, что дело куда сложнее. Можно упростить задачу, рассматривая ее как нахождение минимальной описывающей окружности для данного количества (N) непересекающихся окружностей меньшего радиуса. Тогда мы имеем классическую задачу на оптимизацию в 2N пространстве с N*(N-1)/2 связями. Минимизируемая фугкция неаналитическая. Найти нужно все локальные минимумы. Минимумы будут находиться у ограничений. Похоже, сама оценка вычислительной сложности нетривиальна. В любом случае — существенно многомерные задачи оптимизации имеют экспоненциальную сложность по числу степеней свободы.
Если кто найдет простой способ убить эту задачу, я бы с удовольствием посмотрел.
Здравствуйте Sinclair, Вы писали:
S>Здравствуйте Bell, Вы писали:
B>>привет всем!
B>>есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D. S>Ну, готового решения я не знаю. Однако вот несколько мыслей: S>1. Можно решить обратную задачу — найти минимальное D/d для N окружностей, такое, что круг диаметра D покрывает все окружности. S>2. Как ее решать? Точное аналитическое решение, скорее всего, отсутствует.
Вот, что мне удалось получить на эту тему
1. Есть решение задачи при D/d <= 3, а именно
N = 1 при 1/2 < D/d <= 1 — это очевидно
N= 2...5 если f(N+1) < D/d <= f(N), где f(n) = 1/(1+1/cos(pi(1/2-1/n)))
— тут простейшие геометрические расчёты.
2. Удивительно, но нет такого D/d при котором N равнялось бы шести!
Дело в том, что как только появляется возможность вставить
шестой "карандаш", то тут же оказывается, что можно вставить
ещё и седьмой!
т.е. вблизи D/d = 3 при D/d < 3 число карандашей равно N=5,
вот при пересечении D/d = 3 добавляется сразу два карандаша — N=7 !
3. Дальше опять всё потечёт спокойно, без катаклизмов
N= 7... если f(N) < D/d <= f(N-1), где f(n) таже.
4. Гдето приблизительно при D/d = 4 опять произойдёт
вставка карандаша в центр. Когда точно не могу сосчитать.
5. При бОльших D/d совсем сложно с перестроением порядка,
там происходит что-то типа фазовых переходов.
Достроение слоёв и щелчки в упорядочении.
(прошу прощения за вольную терминологию)
Здравствуйте George_Seryakov, Вы писали:
GS>Здравствуйте Sinclair, Вы писали:
S>>Ессно, мы тут программеры, так что надо написать программу, которая оптимально размещает окружности и строит диаметр. Уверен, что можно выполнить ее за время N*log(N). В хорошем случае за N.
GS>Боюсь, что дело куда сложнее. Можно упростить задачу, рассматривая ее как нахождение минимальной описывающей окружности для данного количества (N) непересекающихся окружностей меньшего радиуса. Тогда мы имеем классическую задачу на оптимизацию в 2N пространстве с N*(N-1)/2 связями. Минимизируемая фугкция неаналитическая. Найти нужно все локальные минимумы. Минимумы будут находиться у ограничений. Похоже, сама оценка вычислительной сложности нетривиальна. В любом случае — существенно многомерные задачи оптимизации имеют экспоненциальную сложность по числу степеней свободы.
GS>Если кто найдет простой способ убить эту задачу, я бы с удовольствием посмотрел.
Окружность, внутри которой находятся диски:
X, Y, R – параметры, задающие описанную окружность.
Xi, Yi, Ri – параметры, задающие отдельный диск, i = 1..N.
Требуется найти
min R
по X, Y и всем Xi, Yi, таким, что
{диски должны не пересекаться}
1. sqr(Xi-Xj)+sqr(Yi-Yj) >= sqr(Ri+Rj) для всех i<>j, i, j = 1..N
{диски должны находиться внутри описанной окружности}
2. sqr(Xi-X) + sqr(Yi-Y)<= sqr(R) — sqr(Ri), i = 1..N.
Получена задача минимизации с ограничениями типа неравенств. Можно построить точную строго выпуклую штрафную функцию (с использованием функции Лагранжа) для этой задачи, которая в окрестности одного из возможных решений будет строго выпуклой (скорее всего при одинаковом радиусе вписываемых дисков решение будет единственным). Численная минимизация ее (лучше всего с помощью метода Ньютона – достаточно всего 7-10 итераций) и даст «наиболее близкое» к исходному приближению решение.
Здравствуйте klovetski, Вы писали:
GS>>Боюсь, что дело куда сложнее. Можно упростить задачу, рассматривая ее как нахождение минимальной описывающей
... GS>>нетривиальна. В любом случае — существенно многомерные задачи оптимизации имеют экспоненциальную сложность по числу степеней свободы.
K>min R
K>по X, Y и всем Xi, Yi, таким, что K>{диски должны не пересекаться} K>1. sqr(Xi-Xj)+sqr(Yi-Yj) >= sqr(Ri+Rj) для всех i<>j, i, j = 1..N K>{диски должны находиться внутри описанной окружности} K>2. sqr(Xi-X) + sqr(Yi-Y)<= sqr(R) — sqr(Ri), i = 1..N.
K>Получена задача минимизации с ограничениями типа неравенств. Можно построить точную строго выпуклую штрафную функцию (с использованием функции Лагранжа)
Расскажи, как ты будешь использовать ф.Л. для чиленной оптимизации. Напиши функцию и расскажи, как ты численно будешь находить оптимум.
Как будешь обрабатывать ситуацию, когда решение находтся вблизи (части) ограничений.
K>Численная минимизация ее (лучше всего с помощью метода Ньютона – достаточно всего 7-10 итераций) и даст «наиболее близкое» к исходному приближению решение.
Расскажи мне про метод Ньютона в многомерных задачах. Оцени заодно собственные числа матрицы квадратичных коэффициентов (овражистость) и вычислительную сложность.
Здравствуйте George_Seryakov, Вы писали:
GS> Расскажи, как ты будешь использовать ф.Л. для чиленной оптимизации. Напиши функцию и расскажи, как ты численно будешь находить оптимум.
например, см. Д. Бертсекас. Условная оптимизация и методы множителей Лагранжа. Москва. "Радио и связь", 1987г., главы 3, 4. GS> Как будешь обрабатывать ситуацию, когда решение находтся вблизи (части) ограничений.
Никак особенно ее обрабатывать не буду, поскольку все учитывается в точной штрафной функции. Кроме того, решение обязательно будет таким, что часть ограничений будет равна нулю в точке решения (множители Лагранжа для них будут > 0).
GS> Расскажи мне про метод Ньютона в многомерных задачах. Оцени заодно собственные числа матрицы квадратичных коэффициентов (овражистость) и вычислительную сложность.
Метод Ньютона можно посмотреть в любой книжке по численным методам. Например, Ф.П.Васильев, Численные методы решения экстремальных задач. М., Наука, 1980г.
Там же есть и описание метода Лагранжа.
Поскольку используется точная штрафная функция, то овражистость практически исчезает. В крайнем случае можно воспользоваться методом регуляризации (акад. Тихонов А.Н).
Вычислительная сложность: на каждой итерации метода Ньютона надо решать систему линейных алгебраических уравнений с положительно определенной матрицей (задается верхняя треугольная часть), где число неизвестных равно количеству ограничений, но > 2. Плюс к этому надо на каждой итерации вычислять сами элементы матрицы, которые определяются на основе вычисления первых, вторых и третьих производных от функций-ограничений.
Можно посмотреть и
web.mit.edu/6.291/www/Allerton_Paper.pdf
Enhanced Optimality Conditions and Exact Penalty Functions
Proceedings of Allerton Conference, September 2000 Enhanced Optimality Conditions
and Exact Penalty Functions 1 by Dimitri P. Bertsekas and Asuman E. Koksal
Здравствуйте klovetski, Вы писали:
GS>> Расскажи, как ты будешь использовать ф.Л. для численной оптимизации. Напиши функцию и расскажи, как ты численно будешь находить оптимум.
K>например, см. Д. Бертсекас. Условная оптимизация и методы множителей Лагранжа. Москва. "Радио и связь", 1987г., главы 3, 4.
Не, мне даже любопытно стало. Всегда думал, что множители Лагранжа — чисто аналитический прием.
К сожалению, у меня тут под боком нет русскоязычной научно-технической библиотеки. Библиотека Конгресса, может, но до нее ехать несколько часов. Будь добр, перескажи своими словами. Кратенько, сжато. Я, типа, профессионал.
GS>> Расскажи мне про метод Ньютона в многомерных задачах. Оцени заодно собственные числа матрицы квадратичных коэффициентов (овражистость) и вычислительную сложность. K>Метод Ньютона можно посмотреть в любой книжке по численным методам. Например, Ф.П.Васильев, Численные методы решения экстремальных задач. М., Наука, 1980г.
Та же самая просьба. Особенно интересует применимость м.Н. в многомерных ситуациях.
K>Поскольку используется точная штрафная функция, то овражистость практически исчезает. В крайнем случае можно воспользоваться методом регуляризации (акад. Тихонов А.Н).
Про это поподробнее, пожалуйста. Всегда думал, что овражистость — свойство, не связанное с использованием точной штрафной функции. И для регуляризации нужна априорная информация.
Здравствуй Георгий, Вы писали:
GS> Будь добр, перескажи своими словами. Кратенько, сжато. Я, типа, профессионал.
Профессионал в чем?
Пересказать можно, но не очень кратенько. Формулы все-таки писать придется.
А в форуме это не очень удобно.
GS>Особенно интересует применимость м.Н. в многомерных ситуациях.
Применяется еще чаще, чем в одномерном случае.
GS>Всегда думал, что овражистость — свойство, не связанное с использованием точной штрафной функции. И для регуляризации нужна априорная информация.
Овражистость — свойство минимизируемой функции. Поскольку начальная функция заменяется на точную штрафную, то функция — другая, с очень хорошими свойствами. Она то как раз и ликвидирует овражистость исходной функции и дает строго выпуклую в окрестности минимума функцию, имеющую единственную точку минимума.
Априорная информация в данном случае состоит в том, что нам нужно произвольное (хотя все-таки одно) решение системы линейных уравнений для метода Ньютона. Поскольку матрица вторых производных может иметь кратные значения (хотя по теории не должна), то величина параметра регуляризации зависит лишь от максимального собственного значения этой матрицы (~ 1.e-7*LambdaMax). Этого вполне достаточно для сходимости.
Вообще говоря, сие может быть не очень интересно всему оcтальному сообществу, поэтому может быть перейдем на общение по e-mail? , Константин
Здравствуйте klovetski, Вы писали:
GS>> Будь добр, перескажи своими словами. Кратенько, сжато. Я, типа, профессионал.
K>Профессионал в чем?
В вычислительной математике. Занимался в ИПМ им Келдыша конструированием разностных схем с произвольным количеством законов сохранения. K>Вообще говоря, сие может быть не очень интересно всему оcтальному сообществу, поэтому может быть перейдем на общение по e-mail? , Константин
Забавно. Обнаруживаю зияющие пробелы в своих знаниях по теории оптимизации. Убедил, что теоремой двойственности убивается геморрой с ограничениями. Пока неясно про точные штрафные функции и почему минимизировать придется ыункцию без овражистости.
K>По тихоновской регуляризации обратных задач астрофизики http://www.issep.rssi.ru/pdf/9712_084.pdf
С астрофизикой тут все честно — внесение дополнительной информации, с "регуляризацией" оптимизации систем с вырожденными минимумами — это скорее технический прием.
Попробуй посмотреть: Numerical methods for constrained optimization.
Ed. by P.E. Gill and W. Murrey, National Physical Laboratory, Teddington, Middlesex, Academic Press, London – New York – San Francisco, 1974.
глава 8, часть III, 8.6. Метод Флетчера.
Оригинал статьи: Fletcher R. An exact penalty function for nonlinear programming with inequalities. Math. Progr., 5, 1973, p. 129- 150.
Там достаточно аккуратно и правдиво выписаны формулы для замены множителей Лагранжа (Lam) хорошей функцией от неизвестных, что позволяет перейти (от поиска минимума по X и максимума по Lam) к поиску минимума только по X. При этом в конце параграфа что-то говорится о том, что Lam – вектор оптимальных множителей задачи …. Не надо обращать на это внимания, а просто решать имеющуюся (чуть выше формула 8.6.8 русского издания) систему линейных алгебраических уравнений (СЛАУ) относительно Lam методом регуляризации.
(Неравенства при этом можно заменить на равенства введением некоторого количества дополнительных переменных. )
Их выводы по поводу плохой применимости метода для решения задач с ограничениями типа неравенств исходят, видимо, из их тогдашнего неумения решать вырожденные СЛАУ. Я же считал достаточно много различных задач с числом переменных до 300 – и все работало нормально. Мог бы лишь порекомендовать еще использовать не чистый метод Ньютона, а с регулируемым шагом. Что-нибудь типа квадратичной аппроксимации по направлению спуска, которое задается матрицей вторых производных. Действительно здорово помогает.
А по поводу «овражистости»… Это бич методов градиентного типа. В методе Ньютона это гораздо менее заметно в силу того, что выбор направления спуска задается матрицей вторых производных, которая в основном и убирает эту овражистость.
Здесь главная проблема — вырожденность матрицы вторых производных. Потому лучше нигде не считать обратных матриц, а решать соответствующие СЛАУ – тогда все сойдется (если их вовремя и аккуратно регуляризовать – то есть брать все время минимальное по норме решение, независимо от имеющейся априорной информации ): ).
Здравствуйте George_Seryakov,
намедни искал разные подпрограммки, нашел интересный сайт: НИВЦ МГУ http://www.srcc.msu.su/num_anal/lib_na/cat/cat1223.htm
Там как раз имеются программы решения задач минимизации функций многих переменных с ограничениями. С текстами на Си и фортране. Может быть подойдет для Вашей задачи? Пусть оно будет вычислять не очень быстро, но если "дольше" писать самому, то почему бы и не воспользоваться?
Здравствуйте klovetski, Вы писали:
K>Там как раз имеются программы решения задач минимизации функций многих переменных с ограничениями. С текстами на Си и фортране. Может быть подойдет для Вашей задачи? Пусть оно будет вычислять не очень быстро, но если "дольше" писать самому, то почему бы и не воспользоваться?
У меня сейчас в основном другие задачи — посредством телефонных разговоров с неопределенным количеством людей определить — почему программа (написанная когда-то кем-то, в меру следуя моим советам) в Миннесоте и Джорджии работает не так, как в Нью-Джерси. Пожалуй, с легкостью променял бы эту задачу на многомерную оптимизацию.
. Так вот надо определить, сколько в эту банку можно напихать карандашей.
