При анализе алгоритмов несколько авторов изучали вычисление объема выпуклых тел большой размерности - задачу, которую также можно использовать для моделирования многих других задач комбинаторного перечисления . Часто в этих работах используется модель вычислений «черный ящик», в которой входные данные предоставляются подпрограммой для проверки, находится ли точка внутри или вне выпуклого тела, а не путем явного перечисления вершин или граней выпуклого многогранника . Известно, что в этой модели никакой детерминированный алгоритм не может достичь точного приближения [1] [2], и даже для явного перечисления граней или вершин проблема заключается в# П-хард . [3] Тем не менее, совместная работа Мартина Дайера , Алана М. Фриза и Равиндрана Каннана предоставила схему рандомизированной полиномиальной аппроксимации по времени для проблемы, обеспечивая резкий контраст между возможностями рандомизированных и детерминированных алгоритмов. [4]
Основным результатом статьи является рандомизированный алгоритм поиска приближение к объему выпуклого тела в -мерное евклидово пространство, предполагая существование оракула членства . Алгоритм требует времени, ограниченного полиномом от, размер а также . Алгоритм объединяет две идеи:
- Используя метод Монте-Карло с цепью Маркова (MCMC), можно генерировать точки, которые почти равномерно случайным образом распределены в пределах данного выпуклого тела. Базовая схема алгоритма - это почти равномерная выборка изнутри. путем размещения сетки, состоящей из -мерные кубы и случайное блуждание по этим кубам. Используя теорию быстрого перемешивания цепей Маркова , они показывают, что случайному блужданию требуется полиномиальное время, чтобы оно стало почти однородным распределением. [4]
- Используя выборку отбраковки , можно сравнивать объемы двух выпуклых тел, одно вложенных в другое, когда их объемы находятся в пределах небольшого коэффициента друг от друга. Основная идея состоит в том, чтобы генерировать случайные точки внутри внешнего из двух тел и подсчитывать, как часто эти точки также находятся внутри внутреннего тела.
Данное выпуклое тело может быть аппроксимировано последовательностью вложенных тел, в конечном итоге достигающих одного известного объема (гиперсферы), при этом этот подход используется для оценки фактора, на который изменяется объем на каждом шаге этой последовательности. Умножение этих факторов дает приблизительный объем исходного тела.
Эта работа принесла своим авторам премию Фулкерсона 1991 года . [5]
Улучшения
Хотя время для этого алгоритма полиномиально, он имеет высокий показатель степени. Последующие авторы улучшили время работы этого метода, предоставив более быстрое перемешивание цепей Маркова для той же проблемы. [6] [7] [8] [9]
Обобщения
Результат полиномиальной аппроксимации был обобщен на более сложные структуры, такие как объединение и пересечение объектов. [10] Это относится к проблеме меры Кли .
Рекомендации
- ^ Elekes, Г. (1986), "Геометрическое неравенство и сложность вычисления объема", Дискретная и Вычислительная геометрия , 1 (4): 289-292, DOI : 10.1007 / BF02187701 , МР 0866364
- ^ Барани, Имре ; Фуредите, Золтан (1987), "Вычисление объема трудно", Дискретная и Вычислительная геометрия , 2 (4): 319-326, DOI : 10.1007 / BF02187886 , МР 0911186
- ^ Дайер, Мартин ; Фриз, Алан (1988), "О сложности вычисления объема многогранника", SIAM журнал по вычислениям , 17 (5): 967-974, DOI : 10,1137 / 0217060 , МР 0961051
- ^ а б Дайер, Мартин ; Frieze, Алан ; Kannan, Рави (1991), "Случайный алгоритм полиномиальное время для аппроксимации объем выпуклых тел", Журнал ACM , 38 (1): 1-17, DOI : 10,1145 / 102782,102783 , MR 1095916 , S2CID 13268711
- ^ Лауреаты премии Фулкерсона , Американское математическое общество , получено 3 августа 2017 г.
- ^ Эпплгейт, Дэвид ; Каннан, Рави (1991), "Выборка и интеграция функций, близких к логарифмически вогнутой", Труды Двадцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '91) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 156 -163, DOI : 10,1145 / 103418,103439 , ISBN 978-0-89791-397-3, S2CID 15432190
- ^ Каннан, Рави ; Ловас, Ласло ; Симоновиц, Миклош (1997), "Случайные блуждания иобъемный алгоритм для выпуклых тел », Случайные структуры и алгоритмы , 11 (1): 1–50, DOI : 10.1002 / (SICI) 1098-2418 (199708) 11: 1 <1 :: AID-RSA1> 3.0.CO; 2 -X , Руководство по ремонту 1608200
- ^ Ловас, Л .; Simonovits, M. (1993), "Случайные блуждания в выпуклое тело и улучшенный алгоритм объемного", случайных структур и алгоритмов , 4 (4): 359-412, DOI : 10.1002 / rsa.3240040402 , MR 1238906
- ^ Ловас, Л .; Вемпала, Сантош (2006), «Моделирование отжига в выпуклых телах иобъем алгоритм», журнал компьютерных и системных наук , 72 (2): 392-417, DOI : 10.1016 / j.jcss.2005.08.004 , MR 2205290
- ^ Брингманн, Карл; Фридрих, Тобиас (01.08.2010). «Аппроксимация объёма стыков и пересечений геометрических объектов большой размерности» . Вычислительная геометрия . 43 (6): 601–610. arXiv : 0809.0835 . DOI : 10.1016 / j.comgeo.2010.03.004 . ISSN 0925-7721 . S2CID 5930593 .