Определение и исследование комбинаторных пространств
Предлагается подход к формализации понятия комбинаторного пространства. Вводится определение направленного отрезка, которое обобщает понятие направленных отрезков в метрических и частично упорядоченных пространствах. Исследован практически важный случай – метрический направленный отрезок....
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46672 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Определение и исследование комбинаторных пространств / Л.Ф. Гуляницкий, С.И. Сиренко // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 17-24. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-46672 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-466722025-02-09T17:42:40Z Определение и исследование комбинаторных пространств Означення та дослідження комбiнаторних просторів Definition and study of combinatorial spaces Гуляницкий, Л.Ф. Сиренко, С.И. Предлагается подход к формализации понятия комбинаторного пространства. Вводится определение направленного отрезка, которое обобщает понятие направленных отрезков в метрических и частично упорядоченных пространствах. Исследован практически важный случай – метрический направленный отрезок. Пропонується підхід до формалізації понять комбінаторного простору та задач комбінаторної оптимізації. Введено означення направленого відрізка, яке узагальнює поняття направлених відрізків у метричних та частково упорядкованих просторах. Досліджено важливий для застосувань випадок – метричний направлений відрізок. The paper suggests an approach for formal defining notions of combinatorial space and combinatorial optimization problem. A notion of directed segment is introduced that generalizes directed segments in metric and partially ordered spaces. The metric directed segment, which is a practically relevant case, is studied in detail. 2010 Article Определение и исследование комбинаторных пространств / Л.Ф. Гуляницкий, С.И. Сиренко // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 17-24. — Бібліогр.: 13 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46672 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Предлагается подход к формализации понятия комбинаторного пространства. Вводится определение направленного отрезка, которое обобщает понятие направленных отрезков в метрических и частично упорядоченных пространствах. Исследован практически важный случай – метрический направленный отрезок. |
| format |
Article |
| author |
Гуляницкий, Л.Ф. Сиренко, С.И. |
| spellingShingle |
Гуляницкий, Л.Ф. Сиренко, С.И. Определение и исследование комбинаторных пространств Теорія оптимальних рішень |
| author_facet |
Гуляницкий, Л.Ф. Сиренко, С.И. |
| author_sort |
Гуляницкий, Л.Ф. |
| title |
Определение и исследование комбинаторных пространств |
| title_short |
Определение и исследование комбинаторных пространств |
| title_full |
Определение и исследование комбинаторных пространств |
| title_fullStr |
Определение и исследование комбинаторных пространств |
| title_full_unstemmed |
Определение и исследование комбинаторных пространств |
| title_sort |
определение и исследование комбинаторных пространств |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/46672 |
| citation_txt |
Определение и исследование комбинаторных пространств / Л.Ф. Гуляницкий, С.И. Сиренко // Теорія оптимальних рішень: Зб. наук. пр. — 2010. — № 9. — С. 17-24. — Бібліогр.: 13 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT gulânickijlf opredelenieiissledovaniekombinatornyhprostranstv AT sirenkosi opredelenieiissledovaniekombinatornyhprostranstv AT gulânickijlf označennâtadoslídžennâkombinatornihprostorív AT sirenkosi označennâtadoslídžennâkombinatornihprostorív AT gulânickijlf definitionandstudyofcombinatorialspaces AT sirenkosi definitionandstudyofcombinatorialspaces |
| first_indexed |
2025-11-28T23:06:34Z |
| last_indexed |
2025-11-28T23:06:34Z |
| _version_ |
1850077300422344704 |
| fulltext |
Теорія оптимальних рішень. 2010, № 9 17
ÒÅÎÐIß
ÎÏÒÈÌÀËÜÍÈÕ
ÐIØÅÍÜ
Предлагается подход к форма-
лизации понятия комбинаторного
пространства. Вводится опреде-
ление направленного отрезка, ко-
торое обобщает понятие напра-
вленных отрезков в метрических и
частично упорядоченных прост-
ранствах. Исследован практичес-
ки важный случай – метрический
направленный отрезок.
Л.Ф. Гуляницкий, С.И. Сиренко,
2010
ÓÄÊ 519.8
Ë.Ô. ÃÓËßÍÈÖÊÈÉ, Ñ.È. ÑÈÐÅÍÊÎ
ÎÏÐÅÄÅËÅÍÈÅ È ÈÑÑËÅÄÎÂÀÍÈÅ
ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÏÐÎÑÒÐÀÍÑÒÂ
Введение. Модели и методы комбинаторной
оптимизации находят применение в разных
областях – от бизнеса до современных нау-
коемких технологий. При этом, ключевые
термины и понятия в этой отрасли приклад-
ной математики часто используются без над-
лежащего формального определения. Это
касается, в первую очередь, таких понятий,
как задача комбинаторной оптимизации
(ЗКО), комбинаторное пространство, со-
седство в комбинаторном пространстве, опе-
раторы сдвига [1–4].
В работе предлагается определение этих и
других важных понятий, отталкиваясь от по-
нятия дискретного пространства. Особое
внимание уделяется конструктивному под-
ходу к определению понятия направленного
отрезка в комбинаторном пространстве.
Данное определение развивает как понятие
отрезка в теоретико-множественном смысле
[5], так и d-отрезка в метрическом и
р-отрезка в частично упорядоченном про-
странствах [6, 7].
1. Комбинаторные пространства
и понятия соседства
Пусть X – дискретное пространство, т. е.
пространство, состоящее из изолированных
точек. Опишем понятие окрестности в таких
пространствах формально.
Определение 1. Упорядоченная пара
(((( )))) { ( ), } 2X
x x s x
x X
X ,R , R R , R N x s S ,U
∈∈∈∈
= = ∈ ⊆= = ∈ ⊆= = ∈ ⊆= = ∈ ⊆
называется пространством с окрестностями,
если выполняется:
1) ;
2) ( ) ( )
x
x
x X R
x X ,N x R x N x .
∀ ∈∀ ∈∀ ∈∀ ∈ ⇒⇒⇒⇒ ≠ ∅≠ ∅≠ ∅≠ ∅
∀ ∈ ∈∀ ∈ ∈∀ ∈ ∈∀ ∈ ∈ ⇒⇒⇒⇒ ∈∈∈∈
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
18 Теорія оптимальних рішень. 2010, № 9
Элементы множества xR будем называть окрестностями точки x X∈ , а
множество xR – системой окрестностей точки x X∈ . Здесь xS – множество
индексов окрестностей точки x .
Понятие окрестности в таком понимании является более слабым, чем
понятие метрической или топологической окрестности, и включает их как
частные случаи.
Окрестности также могут задаваться описательно, с помощью функции
соседства [2].
Определение 2. Функция соседства, определенная на произвольном
множестве X , – это отображение : 2XN X → , т. е. такое отображение, которое
каждому элемента x X∈ ставит в соответствие некоторое множество ( )N x X⊆ .
Определение 3. Пространство с окрестностями в понимании определения 1
называется заданным функцией соседства, если x X∀ ∈∀ ∈∀ ∈∀ ∈ {{ }, ( )}xR x N x==== .
Другой способ задания окрестностей – использование оператора сдвига,
который формально опишем следующим образом. Рассмотрим отображение
:I X P X× → , где P – конечное множество с заданным строгим линейным
порядком. Зададим отображение g : 2PX → таким образом: ( )g x P⊆ – это
множество тех p P∈ , для которых значение ( , )I x p определено.
Определение 4. Отображение :I X P X× → называется оператором сдвига
для элементов множества X , если
1) ( ) : ( , ) ;
2) , ' ( ) : ' ( , ) ( , ').
x X p g x I x p x
x X p p g x p p I x p I x p
∀ ∈ ∃ ∈ =
∀ ∈ ∀ ∈ ≠ ⇒ ≠
Элементы множества P называются параметрами оператора сдвига I .
Определение 5. Пространство с окрестностями в понимании определения 1
называется заданным с помощью оператором сдвига, если x X∀ ∈∀ ∈∀ ∈∀ ∈
{{ },{ ( ), ( )}}xR x I x, p p g x= ∈= ∈= ∈= ∈ .
С помощью оператора сдвига можно формально описать циклический
просмотр (круговой просмотр) окрестностей в алгоритмах, который был
независимо предложен в [8, 9].
Определение 6. Базисными окрестностями произвольной точки простран-
ства x X∈ , будем называть множество
{ ( ), :| ( ) | 1, :1 | ( ) | | ( ) |}
x s x s x t s
B N x s S N x t S N x N x= ∈ > ∃ ∈ < < ,
где C – мощность множества C .
Другими словами, базисные окрестности – это такие окрестности из
системы окрестностей точки, которые имеют наименьшую мощность.
Нетрудно видеть, что все базисные окрестности одной точки имеют
одинаковую мощность и в общем случае для некоторых точек базисных
окрестностей может не существовать.
ОПРЕДЕЛЕНИЕ И ИССЛЕДОВАНИЕ КОМБИНАТОРНЫХ ПРОСТРАНСТВ
Теорія оптимальних рішень. 2010, № 9 19
Определение 7. Пространство X называется локально-конечным в ком-
бинаторном понимании, если все базисные окрестности всех его точек конечны.
Введенное понятие локально-конечности более слабое, чем аналогичное
понятие, которое определено для метрических пространств [10], и эквивалентно
понятию, используемому в топологических пространствах [11]. Укажем, что для
отдельных классов пространств (например, метрических пространств) из
локально-конечности в комбинаторном понимании следует дискретность
пространства.
Определение 8. Комбинаторным пространством называется дискретное
локально-конечное в комбинаторном понимании пространство, которое имеет
не больше, чем счетное количество элементов.
Введем понятие соседства в комбинаторных пространствах таким образом.
Определение 9. Точка комбинаторного пространства y X∈ называется
соседней к точке x X∈ , если существует такая базисная окрестность
x
N B∈
точки x , что y N∈ .
2. Формальное определение задач комбинаторной оптимизации
Объекты, которые обычно рассматриваются в ЗКО – это перестановки, раз-
мещения, графы, подмножества, целые числа и другие структуры, обобщением
которых является понятие комбинаторного объекта [12, 13]. Пусть заданы
множество {1,..., }Y m= и Z – не более чем счетное дискретное пространство с
заданным строгим линейным порядком, которое назовем образующим.
Комбинаторные объекты порождаются на основе заданного базового
пространства, структура которого будет обозначена далее.
Определение 10. Под комбинаторным объектом κ будем понимать триаду
( , , )Xκ = ϕ Ω% , где :Y Xϕ → % – гомоморфизм, который удовлетворяет
ограничениям заданными предикатом Ω , а X% – базовое пространство.
Варьированием вида базового пространства можно порождать комбина-
торные объекты разного типа, которые формально классифицируем таким
образом.
Определение 11. Назовем комбинаторными объектами 1-го порядка такие
комбинаторные объекты, в которых базовое пространство совпадает с
образующим:
(1)
( , , )Xκ = ϕ Ω , где
(1)
X Z≡ , т. е. :Y Zϕ → .
Определение 12. Комбинаторными объектами k-го порядка (k > 1) назовем
такие комбинаторные объекты ( )( , , )kXκ = ϕ Ω , в которых ( ) ( 1)
k
k kX X Z−= ∪ ,
( )
:
k
Y Xϕ → .
Конкретизацией Ω можно описывать целые классы объектов (таких как,
например, перестановки или размещения), каждый из которых представлен
отдельным гомоморфизмом ϕ .
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
20 Теорія оптимальних рішень. 2010, № 9
Определение 13. ЗКО называется проблема нахождения такого *x D X∈ ⊆ ,
что
min ( )
x D X
x* a rg f x
∈ ⊆∈ ⊆∈ ⊆∈ ⊆
==== , (1)
где X – комбинаторное пространство (вариантов) решений задачи, элементами
которого являются комбинаторные объекты, D X⊆ – подпространство
допустимых решений, которое определяется заданным предикатом Π
(формируется ограничительными условиями задачи), а 1
Rf : X →→→→ – заданная
целевая функция задачи.
Это определение конкретизирует понятие ЗКО, которое было введено ра-
ньше в [12, 13], поскольку отсутствие требования локально-конечности про-
странства решений могло приводить к отнесению к данному типу таких задач, к
которым неприменимы переборные алгоритмы комбинаторной оптимизации.
3. Направленные отрезки в комбинаторных пространствах
Пусть X – комбинаторное пространство.
Определение 14. Маршрутом ,x y
uuur
между двумя точками ,x y X∈
называется упорядоченное множество точек 1ix X ,i ,...,k∈∈∈∈ ==== , которое
удовлетворяет условиям:
1) 1 kx x,x y= == == == = ;
2) 1{1,..., 1} :
ix ii k N B x N+∀ ∈ − ∃ ∈ ∈ .
Будем называть длинной маршрута количество точек пространства, из
которых он состоит.
Определение 15. Направленным отрезком между двумя точками называется
маршрут минимальной длинны.
Укажем, что между двумя точками пространства может существовать
несколько разных отрезков.
Введенное понятие отрезка развивает, в частности, понятие d-отрезка,
которое было введено для метрических пространств в [6], и р-отрезка, которое
предложено в [7] для частично упорядоченных пространств. Следует отметить,
что оба упомянутых типа отрезков – как и введенный в этом определении
являются развитием аналогичных понятий, известных в математике [5].
Поскольку метрические направленные отрезки – один из важных частных
случаев направленных отрезков в комбинаторных пространствах, рассмотрим их
более детально. Введем и рассмотрим понятие направленного v-отрезка,
который во многих пространствах совпадает с d-отрезком [6].
Пусть ( , )X X d= – комбинаторное пространство с метрикой d .
Определение 16. Назовем направленным v-отрезком / x, y / , x, y X∈∈∈∈ ,
упорядоченное множество точек 1ix X ,i ,...,k∈∈∈∈ ==== , удовлетворяющее условиям:
ОПРЕДЕЛЕНИЕ И ИССЛЕДОВАНИЕ КОМБИНАТОРНЫХ ПРОСТРАНСТВ
Теорія оптимальних рішень. 2010, № 9 21
1) 1 kx x,x y= == == == = ;
2) 1( () )i id x,x d x,x ++++<<<< , 1 1i ,...,k= −= −= −= − ;
3) для всех трех точек i j sx ,x ,x таких, что ( () < )i j i sd x ,x d x ,x , выполняется
( ( () ) )i j j s i sd x ,x d x ,x d x ,x+ =+ =+ =+ = ;
4) :z X∃ ∈∃ ∈∃ ∈∃ ∈ 1:{1 1} { }i ii ,...,k z x ,x ++++∃ ∈ − ∉∃ ∈ − ∉∃ ∈ − ∉∃ ∈ − ∉ , 1 1( ) ( ) ( )i i i id x ,z d z,x d x ,x+ ++ ++ ++ ++ =+ =+ =+ = .
Определение 17. Назовем v-интервалом x, y< >< >< >< > множество / x, y / без
точек x, y , а v-полуинтервалами x, y /<<<< , / x, y >>>> – множество / x, y / без точки
x и без точки y соответственно.
Нетрудно показать, что в локально-конечном пространстве количество
разных направленных отрезков между двумя фиксированными точками
конечно. Будем обозначать количество разных v-отрезков, которые можно
построить между точками x, y X∈∈∈∈ , как / x,y /M , а j-ый v-отрезок – j
/ x, y / .
Опишем формально определение метрического (ненаправленного) отрезка и
покажем, что имеет место соотношение между понятиями метрического
ненаправленного отрезка и направленного v-отрезка.
Определение 18. Метрическим отрезком [ ]x,y , x, y X∈∈∈∈ , называется
множество [ ] = { : ( ( ( }) ) )x, y z X z z xd x, d ,y d ,y∈∈∈∈ + =+ =+ =+ = .
Лемма 1. Пусть ( , )X X d= – метрическое комбинаторное пространство, а
x, y X∈∈∈∈ произвольные точки, тогда [ ]x,y – конечное множество.
Доказательство. Предположим x, y X∃ ∈∃ ∈∃ ∈∃ ∈ такие, что [ ]x,y содержит
бесконечное количество элементов. Рассмотрим сферическую окрестность
радиуса с = ( , )d x y : с ( ) { : ( , ) }dO x u X d x u ρ= ∈ ≤ . Очевидно, что с[ , ] ( )dx y O x⊆ .
Откуда, с ( )
d
O x содержит бесконечное количество элементов, что противоречит
тому, что X – локально-конечное пространство.
Лемма доказана.
Теорема 1. Для произвольных точек x,y X∈∈∈∈ , если ( , )X X d= – некоторое
комбинаторное пространство с метрикой d , имеет место такое соотношение:
1
[ ] =
/ x ,y /
j
j ,...,M
x, y / x, y /
====
U .
Доказательство. Пусть, {1 }
j
/ x,y /z / x, y / , j ,...,M∈ ∈∈ ∈∈ ∈∈ ∈ . По определению
v-отрезка выполняется ( ( () ) )zd x,z d ,y d x,y+ =+ =+ =+ = , откуда [ ]z x, y∈∈∈∈ .
Следовательно, [ ], {1 }j
/ x,y // x, y / x, y j ,...,M⊂ ∈⊂ ∈⊂ ∈⊂ ∈ .
Пусть [ ]z x, y∈∈∈∈ . Имеем ( ( () ) )d x,z d z,y d x,y+ =+ =+ =+ = . Построим v-отрезок на
основе точек x,z, y . Очевидно, что свойства 1)–3) из определения v-отрезка
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
22 Теорія оптимальних рішень. 2010, № 9
выполняются. Предположим, что существует такая точка { }z' x,z∉∉∉∉ , которая
нарушает условие 4) для точек x,z , т. е.
( ( () ) )d x,z' d z',z d x,z+ =+ =+ =+ = . (2)
Покажем, что для точек x,z',z, y также выполняются свойства 2)–3). Рас-
смотрим ( () )d x,z' d z', y++++ . Из условия (2) и неравенства треугольника имеем:
( ( ( ( ( ( ( ( () ) = ) ) ) = ) ) ) ).d x,z' d z', y d x,z d z',z d z', y d x,y d z,y d z',z d z', y+ − + − − ++ − + − − ++ − + − − ++ − + − − +
Далее, из неравенства треугольника вытекает, что ( ( () ) ) 0d z',y d z,y d z',z− − ≤− − ≤− − ≤− − ≤ .
Отсюда ( ( () ) )d x,z' d z',y d x,y+ ≤+ ≤+ ≤+ ≤ , но из определения метрики следует, что
( ( () ) )d x,z' d z',y d x,y+ ≥+ ≥+ ≥+ ≥ . Итак, имеет место ( ( () ) )d x,z' d z',y d x,y+ =+ =+ =+ = и
свойство 3) выполняется. Выполнение свойства 2) следует из (2).
Аналогичным образом можно показать, что свойства 1)–3) выполняются и
для случая, когда точка z' находится между точками z, y , т.е. имеет место
( ( () ) )d z,z' d z', y d z,y+ =+ =+ =+ = . Поскольку количество точек отрезка [ ]x,y конечно,
то количество точек, удовлетворяющих свойствам 1)–3) и нарушающих условие
4), также конечно. Следовательно, описанный процесс построения v-отрезка
завершится, и будем иметь некоторый v-отрезок, соединяющий точки x, y и
содержащий z . Следовательно, 0
0 {1 }:
j
/ x ,y /j ,...,M z / x, y /∃ ∈ ∈∃ ∈ ∈∃ ∈ ∈∃ ∈ ∈ .
Теорема доказана.
Из теоремы 1 вытекает
Следствие. Пусть ( , )X X d= – метрическое комбинаторное пространство, а
x,y X∈∈∈∈ произвольные точки. Тогда / x, y / – конечное множество.
На практике, v-отрезки используются, в частности, в алгоритме
Н-метода [13]. Ключевым этапом алгоритма являются решения подзадач,
определяющихся на основе двух точек пространства x, y с использованием
v-отрезка особого типа / , / , / , /x x y x x
∞ ∞∈ . Здесь x∞ – это „тупиковая”
относительно x точка пространства (в частности, она может быть максимально
отдаленной от x точкой пространства).
Определение 19. Тупиковой точкой относительно точки x X∈∈∈∈ будем
называть точку x X∈∈∈∈
s
, для которой не существует другой точки x' X∈∈∈∈ такой,
что x' x≠≠≠≠
s
и / x,x / / x,x' /⊂⊂⊂⊂
s
.
Для этого типа v-отрезков имеет место такое соотношение с обычным
метрическим отрезком.
Теорема 2. Для произвольных точек x,y X∈∈∈∈ , если ( , )X X d= – некоторое
комбинаторное пространство с метрикой d , имеет место такое соотношение
1 ( ) ( ) ( ),
[ ] [ ]
i j i i
i x x
/ x ,x /
i j i
y / x,x / , j ,...,M ,i I d x,y d y,x d x,x i I
/ x,x / x, y y,x
s
s s s
s s
U U
∈ = ∈ + = ∈∈ = ∈ + = ∈∈ = ∈ + = ∈∈ = ∈ + = ∈
= ∪= ∪= ∪= ∪
,
ОПРЕДЕЛЕНИЕ И ИССЛЕДОВАНИЕ КОМБИНАТОРНЫХ ПРОСТРАНСТВ
Теорія оптимальних рішень. 2010, № 9 23
где / x,y /M – количество разных v-отрезков между точками x и y , i
xx ,i I
s
∈∈∈∈ –
тупиковые точки относительно точки x .
Доказательство. Пусть [ ],
i
z y,x∈∈∈∈
s
( ) ( ) ( ),
i i
d x, y d y,x d x,x+ =+ =+ =+ =
s s
xi I∈∈∈∈ . Тогда
( ) ( ) ( )
i i
d z, y d z,x d y,x+ =+ =+ =+ =
s s
. Рассмотрим ( ) ( ) ( ) + ( )
i i
d x,z d z,x d x,z d y,x+ = −+ = −+ = −+ = −
s s
( ) ( ) ( ) + ( ) ( )
i
d z, y d x,z d z , y d x,x d x, y− = − −− = − −− = − −− = − −
s
. Поскольку ( ) ( )d x,z d x, y− −− −− −− −
( ) 0d y,z− ≤− ≤− ≤− ≤ , то ( ) ( ) ( )
i i
d x,z d z,x d x,x+ ≤+ ≤+ ≤+ ≤
s s
. Несложно видеть, что имеет место
( ) ( ) ( )
i i
d x,z d z,x d x,x+ ≥+ ≥+ ≥+ ≥
s s
, тогда ( ) ( ) ( )
i i
d x,z d z,x d x,x+ =+ =+ =+ =
s s
и, аналогично доказа-
тельству теоремы 1, можно показать, что существует v-отрезок i/ x,x /
s
, такой
что i i
z / x,x /, y / x,x /∈ ∈∈ ∈∈ ∈∈ ∈
s s
. Если [ ]z x, y∈∈∈∈ , то по теореме 1 существует v-отрезок
между точками x,y содержащий точку z . Поскольку имеет место
( ) ( ) ( )
i i
d x, y d y,x d x,x+ =+ =+ =+ =
s s
, то аналогично предыдущему случаю отрезок можно
расширить до v-отрезка между точками ix,x
s
так, что он будет содержать точки
z и y .
Пусть ,
i j i j
z / x,x / , y / x,x /
s s
∈ ∈∈ ∈∈ ∈∈ ∈ 1 i x/ x,x /
j ,...,M ,i Is= ∈= ∈= ∈= ∈ . Из i j
y / x,x /∈∈∈∈
s
следует, что
( ) ( ) = ( )
i i
d x, y d y,x d x,x++++
s s
. (3)
Рассмотрим случаи:
а) если ( ) ( , )d x,z d x y≤≤≤≤ , то z / x,y /∈∈∈∈ и, по теореме 1, [ ]z x,y∈∈∈∈ ;
б) если ( ) ( , )d x,z d x y>>>> , то i j
xz / y,x / ,i I∈ ∈∈ ∈∈ ∈∈ ∈
s
и, учитывая теорему 1 и (3),
имеем [ ] ( ) ( ) = ( ),i i i
xz y,x ,d x, y d y,x d x,x i I∈ + ∈∈ + ∈∈ + ∈∈ + ∈
s s s
.
Теорема доказана.
Заключение. В работе предложен подход к формальному определению
важнейших в комбинаторной оптимизации понятий – комбинаторного
пространства, соседства, сдвига, маршрута и отрезка. На основе развития
понятия комбинаторных объектов дано строгое определение ЗКО, которое
может использоваться и для классификации таких задач. Разработанный
конструктивный подход к определению и построению специальных
направленных отрезков и интервалов позволяет использовать его в современных
методах решения ЗКО. Проведено исследование наиболее часто встречающихся
типов отрезков – метрических v-отрезков.
Полученные результаты могут служить основой для углубленного изучения свойств
комбинаторных пространств и ЗКО, что определяет направления возможных
дальнейших исследований.
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
24 Теорія оптимальних рішень. 2010, № 9
Л.Ф. Гуляницький, C.І. Сіренко
ОЗНАЧЕННЯ ТА ДОСЛІДЖЕННЯ КОМБIНАТОРНИХ ПРОСТОРІВ
Пропонується підхід до формалізації понять комбінаторного простору та задач комбінаторної
оптимізації. Введено означення направленого відрізка, яке узагальнює поняття направлених
відрізків у метричних та частково упорядкованих просторах. Досліджено важливий для
застосувань випадок – метричний направлений відрізок.
L.F. Hulianytskyi, S.I. Sirenko
DEFINITION AND STUDY OF COMBINATORIAL SPACES
The paper suggests an approach for formal defining notions of combinatorial space and
combinatorial optimization problem. A notion of directed segment is introduced that generalizes
directed segments in metric and partially ordered spaces. The metric directed segment, which is a
practically relevant case, is studied in detail.
1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных
задач оптимизации. – Киев: Наук. думка, 1981. – 288 с.
2. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. –
М.: Мир, 1985. – 512 с.
3. Hoos H.H., Stützle T. Stochastic Local Search: Foundations and Applications. – San Francisco:
Morgan Kaufmann Publ., 2005. – 658 p.
4. Talbi E.-G. Metaheuristics: from design to implementation. – Hoboken, New Jersey: John
Wiley & Sons, 2009. – 593 p.
5. Александров П.С. Введение в теорию множеств и общую топологию. – М.: Наука, 1977. –
368 с.
6. Гуляницкий Л.Ф. О некоторых функциональных понятиях в дискретных пространствах. –
Докл. АН УССР. Сер. А. – 1978. – № 10. – С. 870–873.
7. Гуляницкий Л.Ф. Оптимизация функций, определенных на частично упорядоченных
пространствах одного вида // Вопросы разработки территориальных автоматизированных
систем управления. – Кемерово: Кемеровский госуниверситет, 1984. – С. 93–97.
8. Krone M.J. Heuristic Programming Applied to Scheduling Problems (неопубликованная
диссертация). – Princeton University, 1970. – 142 p.
9. Гуляницкий Л.Ф., Ходзинский А.Н. Особенности реализации алгоритмов метода ветвей и
границ и метода вектора спада в пакете ВЕКТОР-1В // Вычислительные аспекты в
пакетах прикладных программ. – Киев: Ин-т кибернетики АН УССР, 1979. – С. 25–30.
10. Baudier F., Lancien G. Embeddings of locally finite metric spaces into Banach spaces // Proc.
Amer. Math. Soc. – 2008. – N 136. – P. 1029–1033.
11. Nakaoka F., Oda N. Some applications of minimal open sets // Int. J. of Mathematics and
Mathematical Sciences. – 2001. – N 27(8). – P. 471–476.
12. Гуляницкий Л.Ф. До формалізації та класифікації задач комбінаторної оптимізації //
Теорія оптимальних рішень. – 2008. – № 7. – С. 45–49.
13. Гуляницкий Л.Ф., Сергиенко И.В. Метаэвристический метод деформированного
многогранника в комбинаторной оптимизации // Кибернетика и системный анализ. –
2007. – № 6. – С. 70–79.
Получено 15.02.2010
|