close

Вход

Забыли?

вход по аккаунту

?

Алгоритм построения оптимальных покрытий равными кругами невыпуклых многоугольников с неевклидовой метрикой.

код для вставкиСкачать
Информатика, вычислительная техника и управление
УДК 514.174.3
DOI: 10.21285/1814-3520-2016-5-45-55
АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНЫХ ПОКРЫТИЙ РАВНЫМИ КРУГАМИ
НЕВЫПУКЛЫХ МНОГОУГОЛЬНИКОВ С НЕЕВКЛИДОВОЙ МЕТРИКОЙ
© А.Л. Казаков1, А.А. Лемперт2, Нгуен Гуй Лием3
1,2
Институт динамики систем и теории управления им. В.М. Матросова СО РАН,
664033, Россия, г. Иркутск, ул. Лермонтова, 134.
3
Иркутский национальный исследовательский технический университет,
664074, Россия, г. Иркутск, ул. Лермонтова, 83.
Рассматривается задача о покрытии ограниченного множества на плоскости заданным количеством кругов равного радиуса. Разработан новый численный алгоритм, основанный на фундаментальных физических принципах
Ферма и Гюйгенса, который позволяет решать рассмотренную задачу в случаях, когда покрываемое множество
является невыпуклым и/или метрика, задающая расстояние между точками, не является евклидовой. Выполнена
программная реализация алгоритма и проведен вычислительный эксперимент, который показал работоспособность предложенного подхода в общем случае и его высокую эффективность для решения задачи о покрытии
выпуклого множества в евклидовой метрике при большом количестве (и малом радиусе) покрывающих кругов.
Ключевые слова: покрытие равными кругами, неевклидова метрика, оптико-геометрический подход, оптимизация, численный метод, вычислительный эксперимент.
ALGORITHM FOR THE EQUAL CIRCLES OPTIMAL COVERING PROBLEM FOR NON-CONVEX POLIGONS
WITH NON-EUCLIDEAN METRIC
A.L. Kazakov,A.A. Lempert, Nguyen Huy Liem
Matrosov Institute for System Dynamics and Control Theory SB RAS,
134 Lermontov St., Irkutsk, 664033, Russia.
Irkutsk National Research Technical University,
83 Lermontov St., Irkutsk, 664074, Russia.
The article deals with the coverage problem of a bounded set on a plane by a specified amount of equal radius circles.
The numerical algorithm based on fundamental physical principles of Fermat and Huygens is suggested and implemented. It allows to solve the considered problem for the cases where the covered set is non-convex and/or the metric that
specifies the distance between two points is non-Euclidean. The software implementation and computational experiment
have shown the applicability of the proposed approach in a general case and its high efficiency in solving the problem of
covering the convex sets in Euclidean metric with a large number (and a small radius) of covering circles.
Keywords: coverage with equal circles, non-Euclidean metric, optical geometric approach, optimization, numerical method, computational experiment
Введение
Задача о покрытии состоит в том, что в ограниченной области размещаются различные
геометрические объекты так, чтобы покрываемая область полностью лежала внутри объединения последних. Данная постановка находит широкое применение при решении прикладных
проблем в различных отраслях деятельности человека: в технике, экономике, логистике и др.
К типичным их представителям можно отнести задачи размещения станций различного назначения: сотовой связи, беспроводного Интернета, скорой помощи, банковских терминалов и
т.д. [4, 7, 24, 25]; построения сетей искусственных спутников Земли [15, 19]; выбора оптимальной мощности универсальных двигательных установок малой тяги [5, 6]; проектирования энергоэффективной системы мониторинга протяженных объектов беспроводными сенсорными сетями [1–2, 20] и т.д.
___________________________
1
Казаков Александр Леонидович, доктор физико-математических наук, заведующий лабораторией
математических методов исследования свойств динамических систем, е-mail: kazakov@icc.ru
Kazakov Alexander, Doctor of Physical and Mathematical Sciences, Head of the Laboratory of Mathematical Methods
of Dynamic Systems Features Study, e-mail: kazakov@icc.ru
2
Лемперт Анна Ананьевна, кандидат физико-математических наук, ведущий научный сотрудник,
е-mail: lempert@icc.ru
Lempert Anna, Candidate of Physical and Mathematical Sciences, Leading Researcher, e-mail: lempert@icc.ru
3
Нгуен Гуй Лием, аспирант, e-mail: nguyenhuyliem225@gmail.com
Nguyen Huy Liem, Postgraduate, e-mail: nguyenhuyliem225@gmail.com
ISSN 1814-3520
ВЕСТНИК ИрГТУ № 5 (112) 2016
45
Информатика, вычислительная техника и управление
С точки зрения теории оптимизации можно выделить две основные постановки задачи
о покрытии: минимизировать площадью перекрытий при заданном числе покрывающих объектов, либо минимизировать количество объектов при заданных их параметрах. При этом, пожалуй, наибольший интерес исследователей вызывает специальный класс задач, в которых в
качестве покрывающих фигур в двухмерном пространстве выступают круги, а в трехмерном –
шары равного радиуса. Так, в работах [4, 12] предложены алгоритмы нахождения оптимальных покрытий конгруэнтными кругами и указаны решения для покрытия квадрата n кругами
при n  15 , а в [26] представлены оптимальные конфигурации покрытий единичных круга,
квадрата и правильного треугольника для n  10 . В [13, 14] исследовались задачи покрытия
окружностями равного радиуса квадрата и круга с помощью метода построения наилучших
чебышёвских n -сетей, причем для малых n доказано, что представленные результаты являются оптимальными.
Для покрытия некоторых классов плоских односвязных множеств равными кругами
предложены алгоритмы, основанные на использовании квазидифференцируемости целевой
функции [26], эвристических [17] и метаэвристических методов [21–23], методов целочисленной [28] и непрерывной [29,30] оптимизации, представлены результаты для небольшого количества кругов ( n  36 ). Для большего количества равных кругов разработана модификация
метода возможных направлений для нахождения локального минимума и представлены оптимальные покрытия для n  72, n  81, n  100 [31].
Отметим, что большинство известных результатов получено для случая, когда покрываемая область является подмножеством евклидовой плоскости (пространства). В случае же
неевклидовой метрики данная задача остается малоизученной.
В настоящей статье предлагается алгоритм построения оптимальных покрытий замкнутых множеств равными кругами в специальной неевклидовой метрике, который основан на
использовании физических аналогий и развивает ранее проведенные исследования авторов
[8–11, 18]. Представлены результаты вычислительного эксперимента, включающие сравнение
решения задачи о покрытии единичного квадрата в евклидовой метрике с известными результатами; решение задач в метрике с установленными ранее [16] свойствами; решение задач с
неевклидовой метрикой специального вида.
Постановка задачи
Пусть в некоторой ограниченной области D  R 2 заданы непрерывная функция
0 <   f ( x, y)   , определяющая мгновенную скорость движения в точке ( x, y) , и односвязное множество M  D с непрерывной границей M .
Расстояние между точками a  (ax , a y ) и b  (bx , by ) определим следующим образом:
 (a, b) = min
GG ( a ,b )
dG
 f ( x, y).
(1)
G
Здесь G(a, b) – множество всех возможных непрерывных кривых, лежащих в области
D и соединяющих a и b . Иными словами, кратчайшим путем между точками будет кривая,
на преодоление которой затрачивается наименьшее время. Нетрудно увидеть, что все аксиомы метрики для  (a, b) выполнены. В случае, когда f ( x, y)  1 , получаем стандартную евклидову метрику
 (a, b)  (ax  bx )2  (a y  by )2 .
Рассматривается задача об оптимальном покрытии множества M заданным числом
кругов равного радиуса Ck (Ok , r ) , где Ok – центр k -го круга, r – радиус, k  1, n .
Определение 1. Покрытием Pn (r ) множества M из n кругов радиуса r называется
объединение C1 (O1, r )  C2 (O2 , r ) 
46
 Cn (On , r ) такое, что
ВЕСТНИК ИрГТУ № 5 (112) 2016
ISSN 1814-3520
Информатика, вычислительная техника и управление
k = 1, n : Ck (Ok , r )  D, Ok  M , Pn  M = M .
(2)
Иначе говоря, набор кругов Pn является покрытием множества M в том случае, когда
их объединение содержит множество M .
Определение 2. Оптимальным покрытием Pn* множества M будем называть покрытие,
состоящее из кругов минимального радиуса.
Следовательно, при нахождении оптимального покрытия Pn* множества M требуется
найти такое разбиение M на n сегментов M k , k  1, n и расположение центров покрывающих
их кругов Ok , k  1, n , чтобы радиус последних был минимально возможным, т.е. требуется
решить следующую задачу на экстремум:
Rmin = max   Ok , M k   min,
k 1,n
(3)
где  (Ok , M k ) – расстояние от центра Ok круга Ck до замкнутой границы соответствующего
сегмента M k .
О вычислительном алгоритме
В этом разделе авторами предлагается метод решения задачи (1)–(3), базирующийся
на аналогии между распространением световой волны и отысканием минимума интегрального
функционала (1), которая в свою очередь является следствием физических законов Ферма и
Гюйгенса.
Закон Ферма гласит, что свет в своем движении выбирает тот путь, который он проходит за минимальное время, а принцип Гюйгенса утверждает, что, если световая волна достигла некоторой точки, то последняя сама становится источником света. Таким образом, если
выпустить световую волну из одной точки и зафиксировать фотон, который придет первым в
другую точку, то его траектория и будет кратчайшим путем в смысле минимума по времени.
Суть алгоритма заключается в последовательном разбиении покрываемого множества
на сегменты относительно начального набора центров покрывающих кругов на основе диаграммы Вороного; нахождении наилучшего центра покрывающего круга для каждого сегмента;
пересегментации относительно новых центров.
Алгоритм:
Шаг № 1. Определяются начальные координаты центров Ok кругов Ck , k  1, n в заданной области M методом случайной генерации положений, покоординатные совпадения не
допускаются.
Шаг № 2. Из точек Ok , k  1, n , выпускаются световые волны по алгоритму, предложенному в [9], производится разбиение области M на n сегментов M k и определяются границы
сегментов M k , k  1, n .
Шаг № 3. Граница M k сегмента M k аппроксимируется ломаной с узлами в точках
Ai , i = 1, m .
Шаг № 4. Из каждой вершины границы Ai ,i = 1, m , выпускаются световые волны по алгоритму из [9].
Шаг № 5. Каждая точка ( x, y)  M k , впервые достигнутая одной из световых волн, маркируется,
фиксируется
время
ее
достижения
Определяется
точка
T ( x, y) .
ISSN 1814-3520
ВЕСТНИК ИрГТУ № 5 (112) 2016
47
Информатика, вычислительная техника и управление
Ok  arg max T ( x, y). Тогда минимальный радиус круга с центром Ok , покрывающего область
( x , y )M k
M k , определяется как Rk min  max  (Ok , Ai ) .
i 1,m
Шаги № 3–5 выполняются независимо для каждого сегмента M k , k  1, n .
Шаг № 6. Определяется Rmin  max Rk min , после чего осуществляется переход к шагу
k 1,..n
№ 2, при этом в качестве начальных координат выступает найденный набор Ok  Ok , k  1, n .
Шаги № 2–6 повторяются до тех пор, пока уменьшается радиус Rmin , после чего текущее покрытие Pn 
n
Ck (Ok , Rmin ) сохраняется в качестве приближения к глобальному решеk 1
нию задачи.
Шаг № 7. Значение счетчика количества генерации начальных положений Iter увеличивается на единицу. Если значение Iter достигло наперед заданной величины, то работа алгоритма завершается, в противном случае осуществляется переход к шагу № 1.
В следующем разделе представлены результаты вычислительного эксперимента, проведенного с использованием предложенного алгоритма.
Вычислительный эксперимент
Тестирование предложенного в предыдущем разделе алгоритма проведено с использованием ПК следующей конфигурации: Intel(R) Core(TM) i5-3570K (частота 3,4 ГГц, 8 Гб ОЗУ)
и операционной системой Windows 7. Алгоритм реализован на языке программирования С# с
помощью пакета Visual Studio 2008.
Пример 1. В этом примере приведено сравнение полученных авторами результатов с
результатами из [29] для задачи покрытия единичного квадрата равными кругами в евклидовой метрике f ( x, y)  1 (табл. 1). Здесь n – количество покрывающих кругов;
RKnown – наилучший радиус покрытия из [29] для соответствующего числа кругов;
Rmin – наилучший радиус покрытия, найденный с помощью предложенного авторами алгоритма, R  RKnown  Rmin ; t – время работы алгоритма. Число случайных генераций начальных
положений Iter  25 .
Прочерки в пустых строках табл. 1 означают отсутствие известных результатов для соответствующих n . Нетрудно увидеть, что по сравнению с известными (оптимальными) результаты, полученные авторами, несколько хуже, однако отклонение радиуса покрывающих
кругов от оптимального не превосходит 0,1% (для n  10 – 0,0001% ). При этом общее время
решения задачи относительно невелико даже для n  500 . Отсюда можно сделать вывод, что
предложенный алгоритм, несмотря на то что он, строго говоря, напрямую не предназначен
для решения задач о покрытии в евклидовой метрике, и здесь показывает достаточно хорошие результаты.
Пример 2. Введем следующую («линейную») метрику: f ( x, y)  0 (1  kx) , где 0 , k постоянны, т.е. скорость движения растет линейно с ростом координаты x ; покрываемое множество является выпуклым многоугольником. Результаты расчетов для 0  1/ 2; k  1/10 показаны на рис. 1 и в табл. 2.
В работе [16] установлено, что круги в «линейной» метрике для евклидовой метрики
также являются кругами, но со смещенным центром. На рис. 1 можно видеть, что результаты
численного решения хорошо соотносятся с теоретическими. Также отметим, что в «линейной»
метрике радиусы покрывающих кругов одинаковы (см. табл. 2), а при переходе к евклидовой
метрике они зависят от расположения центров: чем ближе к оси Oy , тем меньше радиус.
Пример 3. Введем следующую метрику:
48
ВЕСТНИК ИрГТУ № 5 (112) 2016
ISSN 1814-3520
Информатика, вычислительная техника и управление
a1 ( x, y ) 
0, a1 ( x, y )  0.8,
( x  2.5) 2  ( y  2.5) 2
, f1 ( x, y )  
1  ( x  2.5) 2  ( y  2.5) 2
a1 ( x, y ),
a2 ( x, y ) 
0, a ( x, y )  0.8,
( x  2.5) 2  ( y  7.5) 2
, f 2 ( x, y )   2
1  ( x  2.5) 2  ( y  7.5) 2
a2 ( x, y ),
a2 ( x, y ) 
0, a3 ( x, y )  0.8,
( x  7.5) 2  ( y  2.5) 2
, f 3 ( x, y )  
2
2
1  ( x  7.5)  ( y  2.5)
a3 ( x, y ),
a3 ( x, y ) 
0, a ( x, y )  0.8,
( x  7.5) 2  ( y  7.5) 2
, f 4 ( x, y )   4
1  ( x  7.5) 2  ( y  7.5) 2
a4 ( x, y ),
F ( x, y)  f1 ( x, y)  f 2 ( x, y)  f3 ( x, y)  f 4 ( x, y),
0.4,0  F ( x, y )  0.4,

f ( x, y )   F ( x, y ),
0.8, F ( x, y )  0.

Таблица 1
Покрытие единичного квадрата в евклидовой метрике
Table 1
n
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
35
40
45
50
75
100
150
500
Unit square covering in the Euclidean metric
Rmin
R
RKnown
0,218233512793
0,212516016493
0,202275889208
0,194312371432
0,185510547260
0,179661759933
0,169427051598
0,165680929571
0,160639663597
0,157841981747
0,152246811233
0,148953789551
0,143693177122
0,141244822388
0,138302883283
0,133548706561
0,131764875615
0,128633534503
0,127317553466
0,125553507964
0,122036868819
–
–
–
–
–
–
–
–
ISSN 1814-3520
0,218233693441
0,213107846578
0,202747599284
0,194342244670
0,185635185242
0,180281054179
0,169711748759
0,166406071981
0,160864969889
0,158309478760
0,152426892598
0,149133934021
0,144275792440
0,142205886841
0,139246317546
0,134470667521
0,132809473674
0,129617869059
0,128024566650
0,126029658000
0,123001449585
0,115444819132
0,108376286825
0,102320378621
0,095904051463
0,078877824148
0,068332659403
0,05554107666
0,03082452774
0,000000180648
0,000591830085
0,000471710076
0,000029873238
0,000124637981
0,000619294246
0,000284697161
0,000725142410
0,000225306292
0,000467497013
0,000180081365
0,000180144470
0,000582615318
0,000961064453
0,000943434263
0,000921960960
0,001044598059
0,000984334556
0,000707013185
0,000476150036
0,000964580766
–
–
–
–
–
–
–
–
ВЕСТНИК ИрГТУ № 5 (112) 2016
t
43,477
44,175
45,132
46,687
47,143
47,611
48,516
49,593
50,463
50,81
51,683
52,853
53,165
53,914
54,522
54,835
56,441
57,05
57,892
58,469
58,984
62,884
67,221
71,605
73,508
88,141
128,342
144,831
408,707
49
Информатика, вычислительная техника и управление
Рис. 1. Оптимальные покрытия равными кругами для многоугольника
Fig. 1. Polygon optimal covering with equal circles
Таблица 2
Покрытие выпуклого многоугольника в неевклидовой метрике
Table 2
n
50
Convex polygon covering in the Euclidean metric
Rmin
t
1
10,514174027378
1,014
2
8,229119718281
5,226
3
6,549338964147
12,797
4
5,774430168742
20,561
5
4,826911112031
27,566
6
4,431735800433
30,499
7
4,167997532613
36,146
8
3,888225133265
41,418
9
3,579772457365
45,287
ВЕСТНИК ИрГТУ № 5 (112) 2016
ISSN 1814-3520
Информатика, вычислительная техника и управление
Данная метрика может применяться, к примеру, при описании движения по «холмистой» местности, когда скорость зависит от угла подъема или спуска, либо по «городу», когда
средняя скорость в пригороде постоянна, затем уменьшается при движении от окраин к центру и снова становится постоянной (но меньшей по сравнению с пригородом) в районе центра,
и т.п.
Покрываемое множество в данном случае является невыпуклым многоугольником.
На рис. 2 представлены результаты численного решения. Можно убедиться, что площадь построенных покрытий во всех представленных случаях не намного превосходит площадь покрываемого множества. Кроме того, с ростом количества кругов в покрытии уменьшается площадь перекрытий. Отметим также, что, как и в предыдущем примере, в заданной метрике радиусы покрывающих кругов одинаковы (табл. 3). Из табл. 3 можно видеть, что время
выполнения относительно невелико.
Рис. 2. Покрытие невыпуклого многоугольника в неевклидовой метрике
Fig. 2. Non-convex polygon covering in the Euclidean metric
ISSN 1814-3520
ВЕСТНИК ИрГТУ № 5 (112) 2016
51
Информатика, вычислительная техника и управление
Таблица 1
Покрытие невыпуклого многоугольника в неевклидовой метрике
Table 3
n
1
2
3
4
5
6
7
8
9
Non-convex polygon covering in the Euclidean metric
Rmin
48,3509591310017
39,6535062156294
30,9690548988679
25,3337283136898
22,3412999182734
21,479024599642
19,4344397313216
18,2625236493321
17,6052158181218
t
3,375
25,093
48,109
71,562
88,641
108,734
126,078
142,922
168,688
Вышесказанное позволяет сделать вывод о применимости предложенного авторами
подхода к решению задач о покрытии невыпуклых односвязных множеств со сложной неевклидовой метрикой.
Заключение
В ходе проведенного исследования авторами получены следующие научные результаты:
1. Предложен новый универсальный алгоритм решения известной задачи о построении
оптимального покрытия, представляющий интерес как с точки зрения абстрактной математики, так и в связи с многочисленными приложениями в различных сферах человеческой деятельности, который позволяет минимизировать требования к покрываемому множеству и применим как для евклидовой, так и для достаточно широкого класса неевклидовых метрик.
2. Выполнена программная реализация разработанного алгоритма и проведен численный эксперимент, который показал, что предложенный подход:
а) работоспособен в случаях, когда покрываемое множество имеет сложную конфигурацию и/или рассматривается сложная неевклидова метрика;
б) показывает высокую эффективность при решении классической задачи о покрытии
единичного квадрата кругами равного радиуса в евклидовой метрике, при этом эффективность особенно высока, если число кругов значительно (от нескольких десятков и более).
В дальнейшем предложенный подход авторы планируют распространить на задачу покрытия многосвязных областей [22].
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты № 14-07-00222, № 16-31-00356.
Статья поступила 01.04.2016 г.
Библиографический список
1. Алдыноол Т.А., Ерзин А.И., Залюбовский В.В. Покрытие плоской области случайно распределенными сенсорами // Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика.
2010. Т. 10. № 4. C. 7–25.
2. Астраков С.Н., Ерзин А.И. Сенсорные сети и покрытие полосы эллипсами // Вычислительные технологии. 2013.
Т. 18. № 2. C. 3–11.
3. Астраков С.Н., Ерзин А.И., Залюбовский В.В. Сенсорные сети и покрытие плоскости кругами // Дискретный
анализ и исследование операций. 2009. Т. 16. № 3. C. 3–19.
4. Брусов В.С., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журнал
вычислительной математики и математической физики. 1971. Т. 11. № 2. С. 304–313.
5. Брусов В.С., Пиявский С.А. Двигательная установка малой тяги, универсальная для двумерного диапазона //
Известия Академии наук СССР. Космические исследования. 1970. № 4. С. 542–546.
52
ВЕСТНИК ИрГТУ № 5 (112) 2016
ISSN 1814-3520
Информатика, вычислительная техника и управление
6. Брусов В.С., Пиявский С.А. Применение теории оптимальных покрытий к задачам выбора мощности двигателя
малой тяги // Известия Академии наук СССР. Механика твердого тела. 1969. № 2. С. 10–14.
7. Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал
вычислительной математики и математической физики. 2010. Т. 50. № 4. С. 757–769.
8. Казаков А.Л., Журавская М.А., Лемперт А.А. Вопросы сегментации логистических платформ в условиях становления региональной логистики // Транспорт Урала. 2010. № 4. С. 17–20.
9. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной
логистике // Автоматика и телемеханика. 2011. № 7. С. 50–57.
10. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания
непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. С. 87–100.
11. Казаков А.Л., Лемперт А.А., Нгуен Г.Л. Оптимизация системы коммуникаций с учетом региональных особенностей: математическая модель и численный метод // Вестник ИрГТУ. 2014. № 12 (95). С. 17–22.
12. Кротов В.Ф., Пиявский С.А. Достаточные условия оптимальности в задачах об оптимальных покрытиях // Известия Академии наук СССР. Техническая кибернетика. 1968. № 2. С. 10–17.
13. Лебедев П.Д., Бухаров Д.С. Аппроксимация многоугольников наилучшими наборами кругов // Известия Иркутского государственного университета. Серия: Математика. 2013. № 3. С. 72–87.
14. Лебедев П.Д., Успенский А.А., Ушаков В.Н. Алгоритмы наилучшей аппроксимации плоских множеств объединениями кругов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 4.
С. 88–99.
15. Можаев Г.В. Задача о непрерывном обзоре поверхности Земли и кинематически правильные спутниковые
системы // Известия Академии наук СССР. Космические исследования. 1972. Т.10. № 6. С. 833–840.
16. Москаленский Е.Д. О нахождении точных решений двумерного уравнения эйконала для случая, когда фронт
волны, распространяющейся в среде, является окружностью // Сибирский журнал вычислительной математики.
2014. Т. 17. № 4. С. 363–372.
17. Мухачева А.С. Простые эвристики для решения двумерной задачи максимального покрытия // Принятие решений в условиях неопределенности: межвузовский научный сборник. Вып. 2. Ч. 1. Уфа: Изд-во УГАТУ, 2005.
С. 24–32.
18. О методе решения задачи оптимальной прокладки высокоскоростных железнодорожных магистралей с учетом региональных особенностей /А.Л. Казаков [и др.] // Транспорт: наука, техника, управление. 2012. № 2.
С. 41–44.
19. Пиявский С.А. Об оптимизации сетей // Известия Академии наук СССР. Техническая кибернетика. 1968. № 1.
С. 68–80.
20. Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 2014. Т. 21. № 1. C. 84–102.
21. Телицкий С.В., Филиппова А.С. Комплексный подход к решению задачи покрытия области заготовками
неопределенных размеров // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации.
Управление. 2012. № 2 (145). С. 61–67.
22. Филиппова А.С., Кузнецов В.Ю. Задачи о минимальном покрытии ортогональных многоугольников с
запретными участками // Информационные технологии. 2008. № 9 (145). С. 60–65.
23. Фроловский В.Д. Оптимизация раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы).
Saarbrücken: LAP LAMBERT Academic Publishing, 2011. 124 с.
24. Balazs B., Endre P., Balazs L.L. Optimal circle covering problems and their applications // CEJOR. 2015. Vol. 23.
C. 815–832.
25. Drezner Z. Facility location: A survey of applications and methods. NY: Springer-Verl. 1995. 571 p.
26. Heppes A. Covering a planar domain with sets of small diameter // Periodica Mathematica Hungarica. 2006. Vol. 53.
P. 157–168.
27. Jandl H., Wieder К. A continuous set covering problem as a quasidifferentiale optimization problem // Optimization:
A Journal of Mathematical Programming and Operations Research. 1988. Vol. 19. No. 6. P. 781–802.
28. Melissen J.B.M., Schuur P.C. Covering a rectangle with six and seven circles // Discrete Applied Mathematics. 2000.
Vol. 99. P. 149–156.
29. Nurmela K.J. Ostergard P.R.J. Covering a square with up to 30 equal circles. Res. rept A62. Lab. Technol. Helsinki
Univ. 2000. Р. 20.
30. Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles // Experimental
Mathematics. 2000. Vol. 9. Issue. 2. P. 241–250.
31. Stoyan Y.G., Patsuk V.M. Covering a compact polygonal set by identical circles // Computational Optimization and
Applications. 2010. Vol. 46. C. 75–92.
References
1. Aldynool T.A., Erzin A.I., Zaliubovskii V.V. Pokrytie ploskoi oblasti sluchaino raspredelennymi sensorami [The coverage of a planar region by randomly deployed sensors]. Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriia:
ISSN 1814-3520
ВЕСТНИК ИрГТУ № 5 (112) 2016
53
Информатика, вычислительная техника и управление
Matematika, mekhanika, informatika – Bulletin of Novosibirsk state university. Series: Mathematics, Mechanics, Information Science, 2010, vol. 10, no. 4, pp. 7–25.
2. Astrakov S.N., Erzin A.I. Sensornye seti i pokrytie polosy ellipsami [Sensor networks and stripe covering with ellipse s].
Vychislitel'nye tekhnologii – Computational Technologies, 2013, vol. 18, no. 2, pp. 3–11.
3. Astrakov S.N., Erzin A.I., Zaliubovskii V.V. Sensornye seti i pokrytie ploskosti krugami [Sensor networks and planar
region coverage with circles]. Diskretnyi analiz i issledovanie operatsii – Discrete analysis and operation study, 2009,
vol. 16, no. 3, pp. 3–19.
4. Brusov V.S., Piiavskii S.A. Vychislitel'nyi algoritm optimal'nogo pokrytiia oblastei ploskosti [Computational algorithm for
plane area optimal coverage]. Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki – Journal of computational
mathematics and mathematical physics, 1971, vol. 11, no. 2, pp. 304–313.
5. Brusov V.S., Piiavskii S.A. Dvigatel'naia ustanovka maloi tiagi, universal'naia dlia dvumernogo diapazona [Low thrust
propulsion installation universal for two-dimensional band]. Izvestiia Akademii nauk SSSR. Kosmicheskie issledovaniia –
Proceedings of the USSR Academy of Sciences. Space Exploration, 1970, no. 4, pp. 542–546.
6. Brusov V.S., Piiavskii S.A. Primenenie teorii optimal'nykh pokrytii k zadacham vybora moshchnosti dvigatelia maloi
tiagi [Application of the theory of optimal coverage to the tasks of low thruster power selection]. Izvestiia Akademii nauk
SSSR. Mekhanika tverdogo tela – Proceedings of the USSR Academy of Sciences. Mechanics of solids, 1969, no. 2,
pp. 10–14.
7. Galiev Sh.I., Karpova M.A. Optimizatsiia mnogokratnogo pokrytiia ogranichennogo mnozhestva krugami [Optimization
of limited set multiple coverage with circles]. Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki – Journal of computational mathematics and mathematical physics, 2010, vol. 50, no. 4, pp. 757–769.
8. Kazakov A.L., Zhuravskaia M.A., Lempert A.A. Voprosy segmentatsii logisticheskikh platform v usloviiakh stanovleniia
regional'noi logistiki [The problems of logistic platforms segmentations in the conditions of regional logistics develo pment]. Transport Urala – Transport Urala, 2010, no. 4, pp. 17–20.
9. Kazakov A.L., Lempert A.A. Ob odnom podkhode k resheniiu zadach optimizatsii, vozni-kaiushchikh v transportnoi
logistike [On approach to solving optimization problems arising in transport logistics]. Avtomatika i telemekhanika – Automation and Remote Control, 2011, no. 7, pp. 50–57.
10. Kazakov A.L., Lempert A.A., Bukharov D.S. K voprosu o segmentatsii logisticheskikh zon dlia obsluzhivaniia nepreryvno raspredelennykh potrebitelei [On the issue of logistic zone segmentation to serve continuously distributed consu mers]. Avtomatika i telemekhanika – Automation and Remote Control, 2013, no. 6, pp. 87–100.
11. Kazakov A.L., Lempert A.A., Nguen G.L. Optimizatsiia sistemy kommunikatsii s uche-tom regional'nykh osobennostei: matematicheskaia model' i chislennyi metod [Communication system optimization considering regional features: a
mathematical model and a numerical method]. Vestnik IrGTU – Proceedings of Irkutsk State Technical University, 2014,
no. 12 (95), pp. 17–22.
12. Krotov V.F., Piiavskii S.A. Dostatochnye usloviia optimal'nosti v zadachakh ob opti-mal'nykh pokrytiiakh [Sufficient
optimality conditions in the problems of optimal coverage]. Izvestiia Akademii nauk SSSR. Tekhnicheskaia kibernetika –
Proceedings of the USSR Academy of Sciences. Engineering Cybernetics, 1968, no. 2, pp. 10–17.
13. Lebedev P.D., Bukharov D.S. Approksimatsiia mnogougol'nikov nailuchshimi naborami krugov [Approximation of
polygons with the best set of circles]. Izvestiia Irkutskogo gosudarstvennogo universiteta. Matematika – The Bulletin of
Irkutsk State University. Mathematics, 2013, no. 3, pp. 72–87.
14. Lebedev P.D., Uspenskii A.A., Ushakov V.N. Algoritmy nailuchshei approksimatsii ploskikh mnozhestv
ob"edineniiami krugov [Algorithms of the best approximations of the flat sets by the union of circles]. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Komp'iuternye nauki – The Bulletin of Udmurt University. Mathematics.
Mechanics. Computer Science, 2013, issue 4, pp. 88–99.
15. Mozhaev G.V. Zadacha o nepreryvnom obzore poverkhnosti Zemli i kinematicheski pra-vil'nye sputnikovye sistemy
[The problem of continuous observation of the Earth's surface and cinematically correct satellite systems]. Izvestiia
Akademii nauk SSSR. Kosmicheskie issledovaniia – Proceedings of the USSR Academy of Sciences. Space Exploration, 1972, vol.10, no. 6, pp. 833–840.
16. Moskalenskii E.D. O nakhozhdenii tochnykh reshenii dvumernogo uravneniia eikonala dlia sluchaia, kogda front vo lny, rasprostraniaiushcheisia v srede, iavliaetsia okruzhnost'iu [On finding exact solutions of the two-dimensional eikonal
equation when the front of the wave propagating in a medium is a circle]. Sibirskii zhurnal vychislitel'noi matematiki –
Siberian Journal of Numerical Mathematics, 2014, vol. 17, no. 4, pp. 363–372.
17. Mukhacheva A.S. Prostye evristiki dlia resheniia dvumernoi zadachi maksimal'nogo pokrytiia [Simple heuristics for
solving the two-dimensional problems of maximum coverage]. Priniatie reshenii v usloviiakh neopredelennosti: mezhvuzovskii nauchnyi sbornik, issue 2, part 1 [Decision Making Under Uncertainty Conditions]. Ufa, UGATU Publ., 2005,
pp. 24–32.
18. Kazakov A.L., Zhuravskaia M.A., Lempert A.A., Bukharov D.S. O metode resheniia zadachi optimal'noi prokladki
vysokoskorostnykh zheleznodorozh-nykh magistralei s uchetom regional'nykh osobennostei [On the method of solving
the problem of optimal high-speed rail line laying taking into account regional features]. Transport: nauka, tekhnika, upravlenie – Transport: Science, Engineering, Control, 2012, no. 2, pp. 41–44.
19. Piiavskii S.A. Ob optimizatsii setei [On network optimization]. Izvestiia Akademii nauk SSSR. Tekhnicheskaia kiber-
54
ВЕСТНИК ИрГТУ № 5 (112) 2016
ISSN 1814-3520
Информатика, вычислительная техника и управление
netika – Proceedings of the USSR Academy of Sciences, 1968, no. 1, pp. 68–80.
20. Takhonov I.I. O nekotorykh zadachakh pokrytiia ploskosti krugami [On some problems of covering the plane with
circles]. Diskretnyi analiz i issledovanie operatsii – Discrete analysis and operation study, 2014, vol. 21, no. 1,
pp. 84–102.
21. Telitskii S.V., Filippova A.S. Kompleksnyi podkhod k resheniiu zadachi pokrytiia oblasti zagotovkami neopredelennykh razmerov [An integrated approach to solving the problem of covering the area with blanks of uncertain sizes].
Nauchno-tekhnicheskie vedomosti SPbGPU. Informatika. Telekommunikatsii. Upravlenie – St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2012, no. 2 (145), pp. 61–67.
22. Filippova A.S., Kuznetsov V.Iu. Zadachi o minimal'nom pokrytii ortogonal'nykh mnogougol'nikov s zapretnymi uchastkami [Problems on minimal covering of orthogonal polygons with forbidden areas]. Informatsionnye tekhnologii – Information technologies, 2008, no. 9 (145), pp. 60–65.
23. Frolovskii V.D. Optimizatsiia raskroia materialov na oborudovanii s ChPU (modeli, metody, algoritmy) [Optimization of
material cutting on CNC equipment (models, methods, algorithms)]. Saarbrücken: LAP LAMBERT Academic Publishing,
2011. 124 p.
24. Balazs B., Endre P., Balazs L.L. Optimal circle covering problems and their applications, CEJOR, 2015, vol. 23,
pp. 815–832.
25. Drezner Z. Facility location: A survey of applications and methods, NY: Springer-Verl, 1995. 571 p.
26. Heppes A. Covering a planar domain with sets of small diameter, Periodica Mathematica Hungarica, 2006, vol. 53,
pp. 157–168.
27. Jandl H., Wieder K. A continuous set covering problem as a quasidifferentiale optimization problem, Optimization:
A Journal of Mathematical Programming and Operations Research, 1988, vol. 19, no. 6, pp. 781–802.
28. Melissen J.B.M., Schuur P.C. Covering a rectangle with six and seven circles, Discrete Applied Mathematics, 2000,
vol. 99, pp. 149–156.
29. Nurmela K.J. Ostergard P.R.J. Covering a square with up to 30 equal circles. Res. rept A62. Lab. Technol. Helsinki
Univ, 2000, p. 20.
30. Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Experimental
Mathematics, 2000, vol. 9, issue 2, pp. 241–250.
31. Stoyan Y.G., Patsuk V.M. Covering a compact polygonal set by identical circles, Computational Optimization and
Applications, 2010, vol. 46, pp. 75–92.
ISSN 1814-3520
ВЕСТНИК ИрГТУ № 5 (112) 2016
55
1/--страниц
Пожаловаться на содержимое документа