На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
Внимание!
В связи с запланированным апгрейдом системы форум и большинство других наших сервисов (*.sources.ru, drkb.ru, codersclub.*)
временно будут недоступны с 01 мая по 07 мая 2021г.
Приносим наши искренние извинения за причинённые неудобства!
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Вписание многогранника в многогранник, Поиск максимального объёма
Имеются два выпуклых многогранника. Нужно найти такое аффинное преобразование, применяя которое к первому многограннику, он будет вписан во второй и иметь максимальный объём.
Разобьём многогранник на пирамидки. Объём каждой пирамидки поменяется в одно и то же число раз при линейном преобразовании, которое легко найти.
Вписанность как система линейных неравенств - сравнением точек нашего многогранника с плоскостями граней другого многогранника.
Линейное программирование?
Цитата scrambrella @
Линейное программирование?

Нелинейное. Объём - это функция третьего порядка. Можно рассмотреть задачу немного проще.
Передвинем многогранники так, чтобы их центры масс находились в начале координат, и теперь будем искать линейное преобразование, применяя которое к первому многограннику, он будет вписан во второй и иметь максимальный объём. Здесь мы, убирая смещение, снижаем размерность задачи с 12 ( аффинное преобразование ) до 9 ( линейное преобразование ).
А если привлечь физику? Задать внутреннему многограннику характеристику давления и в точках соприкосновения вершин считать вектора сил, считая скелет многогранника абсолютно упругим. Есть нюанс: метод считает преобразование непрерывным, тогда как задача этого не требует, главное, чтоб результат показал пересечение тел, совпадающее с внутренним телом. Т.е. этот метод не даст вершинам внутреннего многогранника пересечь грани внешнего в процессе расчёта действия сил, поэтому если существует лучшее решение, проходящее через промежуточное худшее, оно не будет найдено.
Цитата Qraizer @
А если привлечь физику? Задать внутреннему многограннику характеристику давления и в точках соприкосновения вершин считать вектора сил, считая скелет многогранника абсолютно упругим.

Уткнётся в стенку в плохой позиции и дальше расширяться не будет.
Можно, конечно, решать градиентными методами, но это долго и будут локальные максимумы.
scrambrella, именно это я и написал. Если хочется что-то сказать, давай по существу.
prografix, никто не запрещает поставить множество экспериментов.
Вообще, в общем случае тут нет решения. Иначе давно б не существовало бы нерешённых задач типа этой Т.е. лучшее, что можно, пробовать по-разному и оценивать результат. ИМХО физический движок наиболее просто это реализует.

Добавлено
P.S. Самому страшно: требуется максимизировать тройной интеграл в поле кватернионов на компактном многообразии, заданном ещё одним тройным интегралом. Буду признателен, если кто предложит формулировку задачи попроще.
Сообщение отредактировано: Qraizer -
Qraizer
Формулировка такая: множество допустимых значений образует выпуклый многогранник в 9-мерном пространстве ( для второй задачи ). Нужно найти оптимальную точку. Беда в том, что она может лежать не на вершине и не на ребре многогранника, а где-то на поверхности.
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:


Рейтинг@Mail.ru
[ Script execution time: 0,0325 ]   [ 19 queries used ]   [ Generated: 5.05.21, 21:55 GMT ]