Метод построения оптимальных темных покрытий
Г. К. Каменев 119991 Москва, ул. Вавилова, 40, ВЦ ФИЦ ИУ РАН
Аннотация:
Рассматривается задача построения метрических
$\varepsilon$-сетей и соответствующих им покрытий шарами
для компактных множеств с вероятностной мерой. Для случая множеств, имеющих метрически значимые части малой меры (темные множества), предлагается использовать методы построения
$\varepsilon$-сетей,
которые можно объединить в рамках единого подхода метода глубоких ям. В этом подходе построенная метрическая сеть пополняется ее глубокой ямой (наиболее удаленным элементом множества) до
достижения требуемой точности. Существующая реализация метода для метрического множества с
заданной на нем вероятностной мерой основана на поиске глубоких ям с помощью чистого глобального поиска. Для построения темных покрытий предлагается реализация метода на основе случайного
мультистарта. Показана близость логарифма числа элементов получаемых сетей к
$\varepsilon$-энтропии, что
позволяет говорить об их оптимальности. Приводятся способы оценки надежности и полноты получаемых
$(\varepsilon, \delta)$-покрытий в смысле К. Э. Шеннона. Рассматриваемые методы могут использоваться в задачах построения покрытий неявно заданных множеств с мерой, определенной на прообразе, а также
в задачах восстановления компактных носителей многомерных случайных величин с неизвестным
законом распределения. Библ. 15. Фиг. 2. Табл. 1.
Ключевые слова:
$\varepsilon$-сети,
$(\varepsilon, \delta)$-сети Шеннона,
$\varepsilon$-энтропия,
$\varepsilon$-емкость, фрактальная размерность, покрытия, аппроксимация, метод глубоких ям, глобальная оптимизация, локальная оптимизация, чистый глобальный поиск, случайный мультистарт, математическое моделирование, носитель случайной величины.
УДК:
519.977
Поступила в редакцию: 11.05.2017
Исправленный вариант: 26.12.2017
DOI:
10.31857/S004446690000330-4