Управление большими системами
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УБС:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Управление большими системами, 2019, выпуск 81, страницы 6–25
DOI: https://doi.org/10.25728/ubs.2019.81.1
(Mi ubs1015)
 

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Системный анализ

О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве

А. Л. Казаковa, А. А. Лемпертa, К. М. Леb

a Институт динамики систем и теории управления им. В.М. Матросова СО РАН, Иркутск
b Иркутский национальный исследовательский технический университет, Иркутск
Список литературы:
Аннотация: Статья посвящена изучению двух содержательных задач вычислительной геометрии: задачи построения оптимальных многократных покрытий кругами замкнутого ограниченного множества в двумерном метрическом пространстве и аналогичной задачи упаковки кругов. В обоих случаях число кругов фиксировано. В первом случае целью является минимизация, а во втором — максимизация радиуса кругов. Рассматриваемая метрика, вообще говоря, неевклидова. Источником такой постановки является транспортная логистика, где встречаются задачи, в которых расстояние между объектами необходимо заменить минимальным временем перемещения между ними, при этом искомый оптимум в силу особенностей местности далеко не всегда достигается при движении по прямой линии. Для решения задач предложены вычислительные алгоритмы, которые основаны на применении оптико-геометрического подхода, базирующегося на принципах геометрической оптики Ферма и Гюйгенса, и методе $K$-средних. Ключевым этапом работы в обоих случаях является построение обобщенной диаграммы Вороного порядка $k$, каждая ячейка которой при фиксированном наборе из $n$ центроидов включает в себя точки, расположенные ближе к некоторым $k$ центроидам, чем к оставшимся $n-k$. При этом, в отличие от классической диаграммы Вороного, здесь ячейки могут пересекаться. Проведены вычислительные эксперименты, выполнены обсуждение и интерпретация их результатов.
Ключевые слова: многократное покрытие множества, многократная упаковка кругов, неевклидова метрика, вычислительный алгоритм, оптико-геометрический подход, диаграмма Вороного, численный эксперимент.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-07-00604
Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 18-07-00604).
Поступила в редакцию: 19 июля 2019 г.
Опубликована: 30 сентября 2019 г.
Тип публикации: Статья
УДК: 514.174.2
ББК: 22.19
Образец цитирования: А. Л. Казаков, А. А. Лемперт, К. М. Ле, “О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве”, УБС, 81 (2019), 6–25
Цитирование в формате AMSBIB
\RBibitem{KazLemLe19}
\by А.~Л.~Казаков, А.~А.~Лемперт, К.~М.~Ле
\paper О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве
\jour УБС
\yr 2019
\vol 81
\pages 6--25
\mathnet{http://mi.mathnet.ru/ubs1015}
\crossref{https://doi.org/10.25728/ubs.2019.81.1}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ubs1015
  • https://www.mathnet.ru/rus/ubs/v81/p6
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Управление большими системами
    Статистика просмотров:
    Страница аннотации:236
    PDF полного текста:83
    Список литературы:34
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024