Скажем, у нас есть многогранник в стандартной форме:
Существуют ли какие-либо известные способы нахождения гиперплоскости которая разбивает многогранник таким образом, чтобы число вершин на каждой стороне гиперплоскости было приблизительно одинаковым? (т.е. алгоритм, который минимизирует абсолютную разницу мощностей вершин по двум сторонам разбиения).
Кроме того, есть ли какие-либо известные результаты относительно сложности этой проблемы?
Приложение: Ограничение типов порезов:
Вот вариант исходной проблемы с надеждой, что ее легче решить, чем исходную:
Есть ли способ эффективно вычислить или оценить, для какой координаты гиперплоскость вида даст наименьшую абсолютную разницу вершин по обе стороны от разбиения? Под эффективными я подразумеваю что-нибудь более эффективное, чем исчерпывающее перечисление мощностей вершин для всех возможных таких разбиений.
Примечание: после нескольких дней небольшого прогресса я также разместил этот вопрос в MathOverflow .
источник
Ответы:
Я не могу вспомнить аналитический способ сделать это!
Но это классическая проблема для генетического программирования! Если вы знакомы с ним, вы можете использовать нормализованные векторы в центре многогранника, который описывает плоскость среза.
Таким образом, ваша совокупность представляет собой набор нормализованных векторов [x, y, z, ...], и в качестве функции подбора вы используете разницу между двумя разделенными объемами!
Так что, если разница стремится к нулю, то больше «подходит» ваш вектор / плоскость!
источник