|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/175.2 19 Nov 2002 19:54:53
To : Valentin Davydov
Subject : Выпуклая оболочка
--------------------------------------------------------------------------------
Tue Nov 19 2002 09:31, Valentin Davydov wrote to All:
VD> From: Valentin Davydov <val@sqdp.trc-net.co.jp>
VD> Задано множество точек внутри K-мерного куба. Требуется построить
VD> выпуклый многогранник минимального объёма, который, во-первых,
VD> содержал бы все эти точки, во-вторых, целиком лежал бы внутри куба,
VD> и в-третьих, число вершин которого не превосходило бы заранее
VD> заданного N. Как бы к решению подступиться?
VD> Для существования решения можно считать, что N >= 2^K. Годится также
VD> и субоптимальное решение (то есть объём, близкий к минимальному,
VD> если степень близости легко оценить).
Можно сделать так:
Для начала любым методом найдем многогранник без ограничения на кол-во вершин.
Далее выпуклый многогранник можно представить в виде системы неравенств(3мер.
случай):
A1x+B1y+C1z<=D1
A2x+B2y+C2z<=D2
...
После чего выкидываем неравенства из системы до тех пор, пока не достигнем
условия 3.
Причем выкидываем так, чтобы добывочный объем был как можно меньше.
также можно попробовать:
1.Выкидывать сразу парами, тройками, и т.д.
2.Выкидывать и одновременно поворачивать вокруг общих ребер смежные грани так,
чтобы минимизировать объем.
Можно также решать задачу минимизации функции V=f(Ai,Bi,Ci,Di)|n<N любым
методом поиска минимума (спуска, генетическим).
Send Email to vovanius2000<yxo>mail. ru
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Выпуклая оболочка 