На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
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,0212 ]   [ 14 queries used ]   [ Generated: 20.06.21, 21:12 GMT ]