Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними
A polynomial two-level algorithm for the linear contraction of criteria for the problem of covering an interval-weighted graph with stars is offered when the objective function tends to a maximum. The sufficient conditions for the asymptotic accuracy of the algorithm is substantiated.
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/154693 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866302297400672256 |
|---|---|
| author | Perepelitsa, V. A. Tereshchenko, Ye. V. |
| author_facet | Perepelitsa, V. A. Tereshchenko, Ye. V. |
| author_sort | Perepelitsa, V. A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-01-18T15:10:28Z |
| description | A polynomial two-level algorithm for the linear contraction of criteria for the problem of covering an interval-weighted graph with stars is offered when the objective function tends to a maximum. The sufficient conditions for the asymptotic accuracy of the algorithm is substantiated. |
| first_indexed | 2025-07-17T10:24:24Z |
| format | Article |
| fulltext |
© В.А. Перепелица, Э.В. Терещенко, 2006
94 ISSN 1681–6048 System Research & Information Technologies, 2006, № 4
УДК 519.8
АСИМПТОТИЧЕСКИЙ ПОДХОД К РЕШЕНИЮ
ДИСКРЕТНЫХ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ С
ИНТЕРВАЛЬНЫМИ ДАННЫМИ
В.А. ПЕРЕПЕЛИЦА, Э.В. ТЕРЕЩЕНКО
Предложен полиномиальный двухуровневый алгоритм линейной свертки кри-
териев для задачи покрытия интервально взвешенного графа звездами с мак-
симизируемой целевой функцией весового вида. Проведено обоснование дос-
таточных условий асимптотической точности предложенного алгоритма.
ВВЕДЕНИЕ
Исследуются задачи дискретного программирования, в которых числовые
параметры слабо структурированы, так как их значения определяются вре-
менными рядами исходных данных основного показателя моделируемого
эволюционного процесса или системы. Например, задача землепользования
[1] формализуется как экстремальная задача покрытия звездами двудольно-
го графа, в котором веса ребер определяются путем прогнозирования вре-
менных рядов урожайности сельскохозяйственных культур. Аналогично, в
теоретико-графовой постановке задачи сегментации рынка [2] веса ребер
представляют собой прогнозное значение временных рядов спроса на опре-
деленный вид продукции. Как показано в работе [3], в процессе прогнозиро-
вания временного ряда основного показателя получаемая оценка его значе-
ний представляется в виде нечетких множеств или интервальных величин.
В результате приходим к решению дискретных экстремальных задач с ин-
тервальными или нечеткими данными.
Настоящая работа посвящена проблемам поиска «субоптимальных»
решений экстремальной задачи о покрытии графа звездами для случая ин-
тервального задания весов ребер. Эта задача относится к NP-трудным [4],
для которых, как известно, отсутствуют полиномиальные алгоритмы. Один
из подходов, развиваемых в рамках «теории алгоритмов с оценками» [5],
при построении приближенных полиномиальных алгоритмов позволяет
осуществлять оценку поведения алгоритма в типичном случае, т.е. «почти
всегда», что практически более ценно. Теория алгоритмов с оценками ис-
пользует понятия асимптотической точности, когда алгоритм находит асим-
птотически оптимальное решение [6], значение целевой функции которого
при увеличении размерности задачи стремится (в смысле относительной
погрешности) к идеальной точке. Ниже предложен и обоснован полиноми-
альный (относительно размерности задачи) асимптотически точный алго-
ритм покрытия звездами полного графа, ребра которого взвешены интер-
вальными весами.
Асимптотический подход к решению дискретных экстремальных задач …
Системні дослідження та інформаційні технології, 2006, № 4 95
Теория алгоритмов с оценками предложена в работах Э.Х. Гимади,
И.И. Глебова, В.А. Перепелицы в начале 1970-х гг. [5]. Для случая миними-
зируемых критериев приближенные алгоритмы для экстремальных задач на
графах (об остовных деревьях и цепях [7], о совершенных паросочетаниях
[8], о покрытии графа цепями и звездами [9, 10], о максимальном незави-
симом множестве вершин [11]), а также для задач ЦЛП [11, 12] в опти-
мизационной и многокритериальной постановках описаны в работах
И.В. Сергиенко, В.А. Емеличева, Н.К. Максишко, М.К. Кравцова [13].
В данной статье проведено обоснование асимптотической точности алго-
ритма покрытия звездами графа с весами ребер, заданными интервально
[14], для случая, когда интервальное значение целевой функции максимизи-
руется. Доказанные в работе [9] теоремы не распространяются на рассмат-
риваемую ниже постановку задачи.
ПОСТАНОВКА ЗАДАЧИ
),( RnG обозначим множество всех полных n-вершинных графов ),( EVG = ,
у которых каждому ребру Ee ∈ приписан вес )(ew , представляющий собой
интервал из множества интервалов ],[},{ 21
rrrr wwww ==Ω , Rr ,1= , т.е. для
ребра Ee ∈ его вес
221121 )(,)()],(),([)( rrrrrrr wewwewewewew === . (1)
При заданном параметре 3≥h допустимым решением рассматривае-
мой задачи покрытия графа G звездами является всякий такой его остовной
подграф EEEVx xx ⊆= ),,( , в котором каждая компонента связности пред-
ставляет собой h -вершинную звезду; }{xX = — множество всех допусти-
мых решений (МДР).
На МДР X определена максимизируемая интервальная целевая
функция (ИЦФ)
max)()( →= ∑
∈ xEe
ewxW , (2)
где при вычислении интервально-значной функции ])(,)([)( 21 xWxWxW =
осуществляется классическое суммирование [14] интервалов =)(ew
Ω∈= )](),([ 21 xwxw :
))(),(()](),([)( 2121 xWxWxwxwxW
xEe
== ∑
∈
, (3)
где
2,1,)()( == ∑
∈
kewxW
x
kk
Ee
.
В работе [15] обосновывается утверждение о том, что всякая интер-
вальная задача на графах с ИЦФ (2) эквивалентна соответствующей произ-
водной от нее двухкритериальной задаче с векторной целевой функцией
(ВЦФ)
В.А. Перепелица, Э.В. Терещенко
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 96
))(),(()( 21 xFxFxF = , (4)
состоящей из двух критериев весового вида MAXSUM
2,1,max)()()( =→== ∑
∈
υυ
υ
υ
xEe
ewxWxF , (5)
где )(
1
ew и )(2 ew , )()( 21 ewew ≤ — пара весов, которой взвешены ребра
xEe ∈ полного графа G , при условии )()(),()( 2
2
1
1 ewewewew == , т.е.
значения критериев (3) и (5) совпадают.
ВЦФ (4), (5) в МДР X определяет паретовское множество (ПМ) X~
[16]. Искомым решением рассматриваемой двухкритериальной задачи по-
крытия графа G h -вершинными звездами является полное множество аль-
тернатив (ПМА) 0X .
Примечание 1. Среди методов отыскания паретовских оптимумов
(ПО) Xx ~~ ∈ многокритериальных задач наиболее распространены алгорит-
мы линейной свертки критериев (АЛСК) [16]. АЛСК базируются на том, что
при положительно определенной N-критериальной ВЦФ элемент Xx ∈ ,
максимизирующий (минимизирующий) линейную свертку критериев (ЛСК),
)()(
1
xFxF
N
υ
υ
υ
λ λ∑
=
= , (6)
является ПО [16]. Здесь вектор NΛ∈λ , где ),...,({ 1 NN λλλ ==Λ ;
},1,0,1
1
N
N
=>=∑
=
υλλ υ
υ
υ .
Примечание 2. В однокритериальной классической постановке задача
покрытия графа звездами является NP-трудной [4], т.е. к настоящему време-
ни отсутствуют полиномиальные алгоритмы ее решения. В многокритери-
альной [7] или интервальной постановке [14] она является труднорешаемой,
т. е. нижняя оценка вычислительной сложности нахождения ее ПМА растет
экспоненциально от размерности Vn = .
Для интервальной задачи покрытия графа звездами предлагается поли-
номиальный двухуровневый АЛСК нахождения допустимого решения, в
определенном смысле близкого к оптимуму. На нижнем уровне каждому
ребру присваивается значение линейной свертки значений границ его весо-
вого интервала, а на верхнем — находится допустимое решение с помощью
предлагаемого градиентного алгоритма 1α . Для построения ЛСК вида (6)
вначале выбирается конечное подмножество 2
0
2 Λ⊂Λ множества =Λ2
),({ 21 λλλ == ; ∑
=
=
2
1
,1
υ
υλ }2,1,0 => υλυ . Далее для каждого вектора
0
221 ),( Λ∈= λλλ строится ЛСК
)()()( 21
21 xWxWxF λλλ += . (7)
Асимптотический подход к решению дискретных экстремальных задач …
Системні дослідження та інформаційні технології, 2006, № 4 97
В силу аддитивной природы критериев (5) ЛСК (7) представляем как
целевую функцию (ЦФ) оптимизационной задачи, рещаемой на верхнем
уровне
∑∑
∈=
→=
xEe
ewxF max)()(
2
1
υ
υ
υ
λ λ . (8)
Из примечания 1 следует, что решение, оптимальное по ЦФ (8), являет-
ся парето-оптимальным по ИЦФ (2), (3) или ВЦФ (4), (5). В результате
объединения найденных решений по всевозможным вариантам 0
2Λ∈λ ,
2
0
2 Λ⊂Λ получаем некоторое подмножество паретовского множества
)(~~ GXX = . Из этого подмножества выделяется некоторое подмножество
искомого ПМА )(00 GXX = . Последнее подмножество можно рассматри-
вать как аппроксимацию искомого ПМА 0X .
ОСНОВНЫЕ РЕЗУЛЬТАТЫ
Описание алгоритма верхнего уровня α1 для фиксированного вектора
0
221 ),( Λ∈= λλλ . Алгоритм 1α использует процедуру координатного подъ-
ема, на вход которого поступают линейные свертки (ЛС) концов интерваль-
ных весов Ω∈= )](),([)( 21 ewewew ребер полного графа ),( EVG =
1),()(),( 21
2
2
1
1 =++= λλλλλ ewewew . (9)
λG обозначим данный граф G , в котором интервальные веса заменены на
их свертки вида (9).
Работа алгоритма 1α состоит из двух этапов 1
1α и 2
1α . Пусть
µ=⎥⎦
⎤
⎢⎣
⎡=
h
n
h
n . На этапе 1
1α 1-взвешенный граф ),( EVG =λ разбивается про-
извольным образом на подграфы ),( iii EVG = с равномощными множества-
ми вершин hiVi ,1, == µ . Множество },...,,{
21
hhh
h vvvV
µ
= рассматривается
как множество центров звезд.
Этап 2
1α состоит из 1−h подэтапов 1,1,,2
1 −= hiiα . Входом подэтапа
i,2
1α является двудольный граф ),,( iihi EVVG = , определяемый подмножес-
твом ребер EEi ⊆ , состоящим из всех таких ребер Evve ih ∈= ),( , что
h
h Vv ∈ , а i
i Vv ∈ . Каждый из подэтапов i,2
1α , 1,1 −= hi состоит из шагов
µ,1=s . Через ),( i
k
h
ss s
vve = , h
h
s Vv ∈ , i
i
k Vv
s
∈ обозначим ребро, выделенное
на шаге s ; s
iE — множество ребер, выделенное на первых s шагах; s
iV —
подмножество вершин i
i
k Vv ∈ , каждая из которых инцидентна некоторо-
му ребру s
iEe ∈ . Если µ<s , то на шаге 1+s выделяется такое ребро
В.А. Перепелица, Э.В. Терещенко
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 98
i
i
ki
i
k
h
ss VvEvve
ss
∈∈=
++++ 11
,),( 11 , которое инцидентно вершине h
h
s Vv ∈+1 , и
при этом его ЛС ),( 1+sew λ имеет максимальное значение среди таких ре-
бер i
i
k
h
s Evve ∈= + ),( 1 , каждое из которых не пересекается с каким-либо
ребром s
iEe ∈ .
)),(,(max)),(,( 11 1
i
k
h
s
Vv
i
k
h
s vvwvvw
s
i
i
k
s +
∈
+ =
+
λλ , (10)
где },...,,{\
21
i
k
i
k
i
ki
s
i s
vvvVV = .
Далее ребро ),(
111
i
k
h
ss s
vve
+++ = окрашивается, после чего осуществляет-
ся реализация следующего шага. После шага µ=s подэтап i,2
1α завершает
свою работу, и следует переход к подэтапу 1,2
1
+iα , 1−≤ hi . После подэтапа
1,2
1
−hα , а вместе с ним и этапа 2
1α , в каждом из двудольных графов
1,1),,,( −== hiEVVG iihi выделяем множество µ
iE всех окрашенных ребер
iEe ∈ , составляющих совершенное паросочетание в iG . Далее в данном
графе E)(V,G =λ выделяем h -дольный остовной подграф =λ
α1
G
),,,...,,( 121
λEVVVV hh−= , где ∪
1
1
−
=
=
h
i
iEE µλ . Так как алгоритм 1α применен к
полному графу, то окрашенные ребра, инцидентные вершине h
h
s Vv ∈ ,
µ≤≤ s1 , образуют h -вершинную звезду, т.е. подграф λ
α1
G представляет
собой допустимое решение XEVx
x
∈= ),( λ
λ , λ
λ EE
x
= рассматриваемой
задачи на полном 1-взвешенном графе ),( EVG = , λ
λ EE
x
= .
Обоснование асимптотической точности алгоритма 1α . Через RG
обозначим полный вероятностный [17] n-вершинный граф, в котором для
какой-либо пары вершин Vvv ∈",' ребру ),( vve ′′′= с условной вероятно-
стью rp присваивается определенный согласно (1) интервальный вес
Ω∈= )](),([)( 21 ewewew
rrr },...,2,1{,1
1
Rrp
R
r
r ∈=∑
=
. Применив к RG алго-
ритм нижнего уровня, каждому его ребру e согласно (9) присвоим значе-
ние ЛС. Взвешенный таким образом граф RG обозначим λ
RG .
),,( ΩRnM λ обозначим множество всех n -вершинных графов =λG
),( EV= , у которых при фиксированном ),( 21 λλλ = каждому ребру Ee∈
приписано значение ЛС (9). Последовательности …,2,1=n поставим во
взаимооднозначное соответствие последовательность множеств ),,( ΩRnM λ
Асимптотический подход к решению дискретных экстремальных задач …
Системні дослідження та інформаційні технології, 2006, № 4 99
и последовательность чисел 0lim,0 =≥
∞→
n
n
n εε , а также последовательность
вероятностных графов λ
RG .
( )xEVx ,= обозначим допустимое решение, полученное путем при-
менения алгоритма 1α к графу ),,( Ω∈ RnMG λλ . Значение ЦФ (8) для это-
го решения ( ) ( )∑
∈
==
xEe
x ewxF ,λσ λ . Через 0σ обозначим вес оптимально-
го по ЦФ )(xF λ решения ( )xEVx ,= .
Определение 1. Пусть существует последовательность nε , =n
,...,2,1= 0lim =
∞→
n
n
ε , для которой свойство ( ) 01 σεσ nx −≥ выполняется для
почти всех графов ),,( Ω∈ RnMG λλ или выполняется с вероятностью
nxP δ−≥ 1)( , 0lim =
∞→n
nδ для графа λ
RG . Тогда будем говорить, что 1α поч-
ти всегда приводит к асимптотически точному решению. При этом удовле-
творяющее этому определению допустимое решение назовем асимптотиче-
ски точным [5, 6].
При фиксированном ),( 21 λλλ = по аналогии с (9) применим к элемен-
там Ω∈= ),()( 21
rrr www λ операцию преобразования их в ЛС.
Rrwww rrr ,1,)( 2
2
1
1 =+= λλλ . (11)
Обозначим },,,,,{ 21 Rr wwwwQ ……=λ упорядоченное по возрастанию
множество Rrwr ,1)},({ =λ .
Всякий полный n -вершинный 1-взвешенный граф, ребрам е которого
приписаны веса )(ew из множества λQ , по определению принадлежит мно-
жеству ),,( ΩRnM λ , в дальнейшем обозначаемое ),,( λQRnM .
)( λΩRG обозначим вероятностный n -вершинный полный граф. Вся-
кому его ребру e приписывается вес ЛС λΩ∈= rwew )( с вероятностью rp
согласно распределению вероятностей
∑∑
==
===>
r
t
tr
R
r
rrRr pfpRrppppp
11
21 ,1,,1,0},,...,,...,,{ , (12)
где rf — интегральная функция распределения; 00 =f .
Необходимо обосновать накладываемые на множество λQ вероятно-
стные условия, при выполнении которых алгоритм 1α почти всегда приво-
дит к асимптотически точному решению.
Пусть к некоторой реализации вероятностного n-вершинного графа
)( λΩRG применен алгоритм 1α , в результате чего получено допустимое
решение ),(
11 xEVx = , на котором ЦФ (8) принимает значение == )(1 xF λσ
В.А. Перепелица, Э.В. Терещенко
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 100
∑
∈
=
1
)(
xEe
ew . Через 0σ обозначим нижнюю оценку значения некоторой ЦФ на
оптимальном покрытии 0x рассматриваемой реализации графа )( λΩRG .
Пусть для величин Ω∈ rw выполняется указанное выше распределение ве-
роятностей (12). Определим условия, при выполнении которых вероятность
получения асимптотически точного решения стремится к 1.
nnP δσεσ −≥−≥ 1))1(( 01 , (13)
где 0→nε и 0→nδ при ∞→n .
Согласно равенству
h
n
=µ число ребер, составляющих остовные под-
графы 0x и 1x , определяется соотношением
0)1(
10
nhEE xx =−== µ . (14)
Далее с учетом определения величин 0σ и r
Rr
R ww
≤≤
=
1
max согласно (14)
получаем неравенство Rwn00 ≤σ , откуда для выполнения неравенства (13)
достаточно, чтобы выполнялось соотношение
nRn wnP δεσ −≥−≥ 1))1(( 01 . (15)
Пусть 1σ — математическое ожидание величины 1σ ; )( 1σD — дис-
персия величины 1σ . Допустим, что мы получили нижнюю оценку 0σ для
1σ : 01 σσ ≥ . Выберем новую величину *σ так, что выполняется строгое нера-
венство 0* σσ < и оценим вероятность того, что величина 1σ не превосходит
*σ . При этом установлено )|(|)( *
1
*
1 σσσσσσ −≥−≤≤ PP . Используя
неравенство Чебышева, получаем
2
0
1
1
)*(
)(
*)(
σσ
σ
σσ
−
≤≤
D
P . (16)
Величину *σ определим следующим образом:
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−=
)(ln
11* 0
nϕ
σσ , (17)
где )(nϕ — произвольная, сколь угодно медленно растущая функция
∞→)(nϕ с ростом n . Тогда
2
0
2
1
1
)(
))((ln)(
*)(
σ
ϕσ
σσ
nD
P ≤≤ . (18)
Вычислим нижнюю оценку 1σ . На каждом шаге первого подэтапа
1,2
1α , состоящего из шагов µ,,2,1 …=s , выбирается ребро максимального
Асимптотический подход к решению дискретных экстремальных задач …
Системні дослідження та інформаційні технології, 2006, № 4 101
веса ml из множества мощностью slsmm −+== µ)( , µ≤≤ s1 ; ml — ма-
тематическое ожидание величины выделяемого максимума ml .
i,2
1σ обозначим суммарный вес ребер, выделенных и окрашенных
в двудольном подграфе ),,( iihi EVVG = на подэтапе 1,2
1α , 11 −≤≤ hi ;
i,2
1σ — математическое ожидание величины i,2
1σ .
В принятых обозначениях результатом работы шага s подэтапа 1,2
1α яв-
ляется выделенное на этом шаге ребро ),( i
k
h
ss s
vve = , вес которого равен
Ω∈) λew( .
Математическое ожидание
( ) )()()()(
2
1
1
1
11 rm
R
r
rrR
R
r
rmrmrm wlPwwwwlPwlPwl ≤−−=≤−≤= ∑∑
−
=
+
=
++ , (19)
где
m
rrm fwlP =≤ )( . (20)
По определению графа )( λΩRG вычисляемые согласно (5) элементы
ml независимы. Отсюда с учетом соотношения slsmm −+== µ)( и равенств
(19), (20) вычисляем математическое ожидание
=≤−== ∑ ∑∑
=
−
==
))((
1
2
11
1,2
1
µµ
σ
m
R
r
rmR
m
m wlPwl
∑∑ ∑
−
+
−
= =
+ −
−
−≥−−=
2
1
2
1 1
1 1
)()(
R
r r
rr
R
R
r m
m
rrrR f
ww
wfwww µµ
µ
.
Математическое ожидание веса покрытия 1x представляет собой сумму
математических ожиданий результатов работы подэтапов i,2
1α , 1,1 −= hi .
∑
−
=
=
1
1
,2
11
h
i
iσσ . (21)
Тогда оценка для представленной выше величины 0σ будет иметь вид
∑
−
+
−
−
−−−=
2
1
0 1
)1()1(
R
r r
rr
R f
ww
hwh µσ . (22)
На основании (17) и (22) вычислим значение
)
ln
11)(
1
)1()1((*
2
1
ϕ
µσ −
−
−
−−−= ∑
−
+
R
r r
rr
R f
ww
hwh .
Последнее выражение для расчета *σ можем преобразовать в терми-
нах ЛС (9)
В.А. Перепелица, Э.В. Терещенко
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 102
=⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−
−−−= ∑
−
+
ϕ
µσ
ln
11
1
)1()1(*
2
1
R
r r
rr
R f
ww
hwh
*)1()1()( 2
2
1
1 ελλµ −−+= hww RR , (23)
где
∑
−
+ +
−
−
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−=
2
1
ln
1
1ln
111*
R
r r
rr
R f
ww
w ϕϕµ
ε .
С учетом (13) и упорядочения элементов λΩ∈ rw для оптимального
значения 0σ справедлива верхняя оценка )1(0 −≤ hwRµσ . Тогда можем
сформулировать следующее
Утверждение 1. Для того чтобы имело место стремление →
− )1(
*
hwRµ
σ
1→ при ∞→n , достаточно выполнить неравенство
∑
−
=
++ +
≤
−
−+−2
1
2
2
1
1
22
12
11
11 )(
1
)()(R
r
RR
r
rrrr ww
f
wwww
ϕ
λλµλλ
.
Аналогично вычислим верхнюю оценку для дисперсии
∑
−
=
+
−
−
−−≤
2
1
1
11 1
)1)((2)(
R
r r
rr
R f
wwhwwD σ . (24)
С учетом (22), (24), (18)
h
n
=µ получим при ∞→n .
≤
−
−
−
−−
≤≤
∑
−
=
+
222
2
1
12
1
1
)1(
1
ln)1)((2
*)(
hw
f
ww
hww
P
R
R
r r
rr
R
µ
ϕ
σσ
0ln3
)1(
ln)(2 2
22
2
1
→≤
−
−
≤
ϕ
ϕ
µ
ϕ
µ
ϕ
nhw
w
ww
R
R
R
.
Теорема 1. Если распределение вероятностей (12) для весов ребер графа
)( λΩRG удовлетворяет неравенству ∑
−
=
++ ≤
−
−+−2
1
22
12
11
11
1
)()(R
r r
rrrr
f
wwww λλ
ϕ
λλµ )( 2
2
1
1 RR ww +
≤ , то с вероятностью nP δ−≥1 , 0→nδ при ∞→n ре-
шение 1x , полученное с помощью алгоритма 1α , является асимптотически
точным. Вычислительная сложность этого алгоритма )()( 2
1 nO≤ατ .
Последнее утверждение теоремы 1 очевидно, так как, согласно опре-
делению, каждое ребро данного графа алгоритм 1α просматривает не более
одного раза, в силу чего )()( 1 EO≤ατ , где )( 2nOE ≤ .
Асимптотический подход к решению дискретных экстремальных задач …
Системні дослідження та інформаційні технології, 2006, № 4 103
СРАВНЕНИЕ С ИЗВЕСТНЫМИ РЕЗУЛЬТАТАМИ
В целях сравнения полученных в настоящей работе результатов с известны-
ми ранее [5, 6, 10] рассмотрим частный случай расположения интервалов
Ω∈)(ewr на числовой оси. Пусть интервалы Rrwww
rrr ,1],,[ 21 == имеют
длину, равную 2. Центры интервалов — это возрастающая последователь-
ность целых чисел с шагом 1. Границы интервалов — целые числа. Распре-
деление вероятностей — равновероятное, т.е.
R
pr
1
= , Rr ,1= . Значит,
справедливо следующее
Утверждение 2. Для почти всех графов ),,( Ω∈ RnMG решение 1x
является асимптотически точным, если выполняется неравенство ≤RR ln
ϕ
λλ
h
wwn RR )( 2
2
1
1 +
≤ .
Доказательство. Действительно, пусть ),,(0 λΩRnM — множество
всех графов ),,( Ω∈ RnMG , для каждого из которых в контексте опреде-
ления 1 справедливо неравенство ( ) 0lim,1 0
1 =−≥
∞→
nnn εσεσ . Таким об-
разм, в случае равномерного распределения вероятность P получения
асимптотически точного решения 1x равна
),,(
),,(0
Ω
Ω
=
RnM
RnM
P
λ
. Поэтому до-
статочно показать, что при выполнении условий этого утверждения для
равномерного распределения имеют место равенства 0*lim =
∞→
ε
n
,
( ) 0*lim 1 =≤
∞→
σσP
n
, где величины )(** nεε = , )(** nσσ = определяются
выражениями (18), (23). Из них вытекает следующее обоснование асимп-
тотической точности решения х1, получаемого на выходе алгоритма 1α :
=+
−
−
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−= ∑
−
+
2
1
ln
1
1ln
111*
R
r r
rr
R f
ww
w ϕϕµ
ε
≤+
−⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−= ∑
−
=
2
1 ln
1
ln
11
R
rR rR
R
wn
h
ϕϕ
≤+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−+⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−≤ ∫
−
=
ϕλλϕ ln
11
)(ln
11
2
1
2
2
1
1
R
rRR rRwwn
hR
0
ln
1
)(
ln
ln
11 2
2
1
1
→+
+⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−≤
ϕλλϕ RR wwn
RRh ,
≤
−
−
−
−−
≤≤
∑
−
=
+
222
2
1
12
1
1
)1(
1
ln)1()(2
*)(
hw
f
ww
hww
P
R
R
r r
rr
R
µ
ϕ
σσ
В.А. Перепелица, Э.В. Терещенко
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 104
≤
−
−
−
≤
∑
−
=
)1(
ln)(2
22
2
1
2
1
hw
rR
Rww
R
R
r
R
µ
ϕ
0ln3 2 →≤ ϕ
ϕn
при ∞→n и
ϕϕ
λλ
h
wn
h
wwn
RR RRR =
+
≤
)(
ln
2
2
1
1 ,
ϕh
nR ≤ln . (25)
Утверждение 2 доказано.
Среди известных результатов о достаточных условиях асмптотической
точности градиентных алгоритмов можно привести следующий [5, 6].
Если множество
n
hRR
ln
и},...,2,1{
+
≤=Ω
ϕ
, то для почти всех графов
),,( Ω∈ RnMG алгоритм градиентного типа находит асимптотически точное
решение задачи коммивояжера с минимизируемой ЦФ. Отметим, что при
таком определении Ω достаточное условие утверждения 2 принимает вид
(25). Таким образом, область достаточных условий асимтотической точно-
сти в случае максимизируемой ЦФ экспоненциально превосходит область
достаточных условий асимптотической точности минимизируемых
критериев.
В работе [10] для максимизируемой ЦФ получены достаточные условия
асимптотической точности алгоритма координатного подъема для задачи о
цепях в виде 1ln −≤
ϕ
nR . Отсюда следует, что представленные в утвержде-
нии 2 достаточные условия асимптотической точности градиентного алгорит-
ма для задачи с интервальными данными фактически совпадают с достаточ-
ными условиями асимптотической точности алгоритма для задачи с
детерминированными данными в случае, когда параметр h является констан-
той или ограниченной растущей функцией от n .
ВЫВОДЫ
Полученные результаты относятся к классу задач дискретного программи-
рования в условиях неопределенности данных. Исследуемая авторами про-
блема оценки эффективности градиентных алгоритмов для экстремальных
задач на интервально взвешенном графе, по-видимому, ранее не рассматри-
валась. Теорема 1 устанавливает принципиальную возможность обоснова-
ния асимптотической точности алгоритмов градиентного подъема (спуска)
для дискретных задач с интервальными данными. Представляет интерес
исследование других задач дискретной оптимизации с интервальными
данными.
Асимптотический подход к решению дискретных экстремальных задач …
Системні дослідження та інформаційні технології, 2006, № 4 105
ЛИТЕРАТУРА
1. Максишко Н.К., Перепелица В.А., Заховалко Т.В. Теоретико-графовая эколого-
экономическая модель задачи землепользования // Вісн. Східноукр. нац. ун-
ту ім. В. Даля. — 2002. — № 2 (48), — С. 92–100.
2. Перепелица В.А., Терещенко Э.В. Теоретико-графовая модель сегментации
рынка // Питання прикладної математики і математичного моделювання.
Зб. наук. пр. — Дніпропетровськ: Вид-во Дніпропетр. ун-ту, 2004. —
С. 153–159.
3. Максишко Н.К., Перепелица В.А. Моделирование управления риском на базе
прогнозной модели // Экономическая кибернетика. — 2004. — № 1–2 (25–
26). — С. 85–89.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. —
М.: Мир, 1982. — 416 с.
5. Гимади Э.Х., Глебов И.И., Перепелица В.А. Алгоритмы с оценками для задач
дискретной оптимизации // Проблемы кибернетики. — М.: Наука, 1975. —
Вып. 31. — С. 35–42.
6. Перепелица В.А. Асимптотический подход к решению некоторых экстремаль-
ных задач на графах//Проблемы кибернетики. — М.: Наука, 1973. —
Вып. 26. — С. 291–314.
7. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных
задач // Дискретная математика. — 1994. — Вып. 1,6. — С. 3–33.
8. Сергиенко И.В., Перепелица В.А. К проблеме нахождения множеств альтерна-
тив в дискретных многокритериальных задачах // Кибернетика. — 1987. —
№ 5. — С. 85–93.
9. Емеличев В.А., Перепелица В.А., Шунгаров Х.Д. Асимптотический подход к
многокритериальной задаче покрытия графа звездами// ДАН БССР. —
1986. — ХХХI, № 5. — С. 430–433.
10. Максишко Н.К. Анализ эффективности алгоритма координатного подъема для
задачи о цепях // Докл. АН УССР. Сер. А. Физ.-мат. и техн.науки. — 1990.
— № 7. — С. 77–80.
11. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации. Проблемы, мето-
ды решения, исследования. – Киев: Наук. думка, 2003. — 260 с.
12. Сергиенко И.В. Математические модели и методы решения задач дискретной
оптимизации. – Киев: Наук. думка, 1988. — 472 с.
13. Кравцов М.К., Дичковская С.А. Асимптотический подход к решению много-
критериальной трехиндексной планарной проблемы выбора // Кибернетика
и системный анализ. — 2004. — № 3. — С. 24–29.
14. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. — М.: Мир,
1987. — 356 с.
15. Perepelitsa V.A., Kozina G.L. Interval Discrete Models and Multiobjectivity. Com-
plexity Estimates // Interval Computations. — 1993. — № 1. — Р. 51–59.
16. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериаль-
ных задач. — М.: Наука, 1982. — 256 с.
17. Коршунов А.Д. Основные свойства случайных графов с большим числом
вершин и ребер // Успехи матем. наук. — 1985. — 40, № 1(241). —
С. 123–164.
Поступила 12.07.2005
|
| id | journaliasakpiua-article-154693 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:24:24Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/c6/1ea782c8f82d44414ef9552e1b369dc6.pdf |
| spelling | journaliasakpiua-article-1546932019-01-18T15:10:28Z Asymptotic approach to solution of discrete extreme problems with interval data Асимптотический подход к решению дискретных экстремальных задач с интервальными данными Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними Perepelitsa, V. A. Tereshchenko, Ye. V. A polynomial two-level algorithm for the linear contraction of criteria for the problem of covering an interval-weighted graph with stars is offered when the objective function tends to a maximum. The sufficient conditions for the asymptotic accuracy of the algorithm is substantiated. Предложен полиномиальный двухуровневый алгоритм линейной свертки критериев для задачи покрытия интервально взвешенного графа звездами с максимизируемой целевой функцией весового вида. Проведено обоснование достаточных условий асимптотической точности предложенного алгоритма. Запропоновано поліноміальний двурівневий алгоритм лінійної згортки критеріїв для задачі покриття інтервально зваженого графа зірками з цільовою функцією ваги, яка прямує до максимуму. Проведено обґрунтування достатніх умов асимптотичної точності запропонованого алгоритму. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-01-18 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/154693 System research and information technologies; No. 4 (2006); 94-105 Системные исследования и информационные технологии; № 4 (2006); 94-105 Системні дослідження та інформаційні технології; № 4 (2006); 94-105 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/154693/154303 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Perepelitsa, V. A. Tereshchenko, Ye. V. Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| title | Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| title_alt | Asymptotic approach to solution of discrete extreme problems with interval data Асимптотический подход к решению дискретных экстремальных задач с интервальными данными |
| title_full | Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| title_fullStr | Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| title_full_unstemmed | Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| title_short | Асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| title_sort | асимптотичний підхід до вирішення дискретних екстремальних задач з інтервальними даними |
| url | https://journal.iasa.kpi.ua/article/view/154693 |
| work_keys_str_mv | AT perepelitsava asymptoticapproachtosolutionofdiscreteextremeproblemswithintervaldata AT tereshchenkoyev asymptoticapproachtosolutionofdiscreteextremeproblemswithintervaldata AT perepelitsava asimptotičeskijpodhodkrešeniûdiskretnyhékstremalʹnyhzadačsintervalʹnymidannymi AT tereshchenkoyev asimptotičeskijpodhodkrešeniûdiskretnyhékstremalʹnyhzadačsintervalʹnymidannymi AT perepelitsava asimptotičnijpídhíddoviríšennâdiskretnihekstremalʹnihzadačzíntervalʹnimidanimi AT tereshchenkoyev asimptotičnijpídhíddoviríšennâdiskretnihekstremalʹnihzadačzíntervalʹnimidanimi |