Подходы к решению задачи раскраски графа
Предложены два подхода к решению задачи раскраски графа. Проведено сравнительное исследование эффективности известных для данной задачи и разработанных алгоритмов, подтвердившее преимущества предложенных подходов....
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schriftenreihe: | Компьютерная математика |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84559 |
| 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: | Подходы к решению задачи раскраски графа / В.П. Шило // Компьютерная математика. — 2009. — № 2. — С. 159-168. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84559 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-845592025-02-10T00:49:10Z Подходы к решению задачи раскраски графа Підходи до розв’язання задачі розфарбування графа Approaches to the graph painting problem solving Шило, В.П. Теория и методы оптимизации Предложены два подхода к решению задачи раскраски графа. Проведено сравнительное исследование эффективности известных для данной задачи и разработанных алгоритмов, подтвердившее преимущества предложенных подходов. Запропоновано два підходи до розв’язання задачі розфарбування графа. Проведено порівняльне дослідження ефективності відомих для даної задачі і розроблених алгоритмів, яке підтвердило переваги запропонованих підходів. Two approaches to the Vertex Coloring Problem solving are proposed. The comparative investigation of the efficiency of the proposed one and other methods known for this problem are provided, which confirmes the advantages of the approach proposed. 2009 Article Подходы к решению задачи раскраски графа / В.П. Шило // Компьютерная математика. — 2009. — № 2. — С. 159-168. — Бібліогр.: 7 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84559 519.854 ru Компьютерная математика application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Теория и методы оптимизации Теория и методы оптимизации |
| spellingShingle |
Теория и методы оптимизации Теория и методы оптимизации Шило, В.П. Подходы к решению задачи раскраски графа Компьютерная математика |
| description |
Предложены два подхода к решению задачи раскраски графа. Проведено сравнительное исследование эффективности известных для данной задачи и разработанных алгоритмов, подтвердившее преимущества предложенных подходов. |
| format |
Article |
| author |
Шило, В.П. |
| author_facet |
Шило, В.П. |
| author_sort |
Шило, В.П. |
| title |
Подходы к решению задачи раскраски графа |
| title_short |
Подходы к решению задачи раскраски графа |
| title_full |
Подходы к решению задачи раскраски графа |
| title_fullStr |
Подходы к решению задачи раскраски графа |
| title_full_unstemmed |
Подходы к решению задачи раскраски графа |
| title_sort |
подходы к решению задачи раскраски графа |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2009 |
| topic_facet |
Теория и методы оптимизации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84559 |
| citation_txt |
Подходы к решению задачи раскраски графа / В.П. Шило // Компьютерная математика. — 2009. — № 2. — С. 159-168. — Бібліогр.: 7 назв. — рос. |
| series |
Компьютерная математика |
| work_keys_str_mv |
AT šilovp podhodykrešeniûzadačiraskraskigrafa AT šilovp pídhodidorozvâzannâzadačírozfarbuvannâgrafa AT šilovp approachestothegraphpaintingproblemsolving |
| first_indexed |
2025-12-02T07:26:34Z |
| last_indexed |
2025-12-02T07:26:34Z |
| _version_ |
1850380538313965568 |
| fulltext |
Предложены два подхода к ре-
шению задачи раскраски графа.
Проведено сравнительное иссле-
дование эффективности извест-
ных для данной задачи и раз-
работанных алгоритмов, под-
твердившее преимущества пред-
ложенных подходов.
© В.П. Шило, 2009
ÓÄÊ 519.854
Â.Ï. ØÈËÎ
ÏÎÄÕÎÄÛ Ê ÐÅØÅÍÈÞ ÇÀÄÀ×È
ÐÀÑÊÐÀÑÊÈ ÃÐÀÔÀ*
Введение. В данной работе предложены два
подхода к решению задачи раскраски графа.
Первый из них состоит в сведении двух ти-
пов таких задач к модели булевого квадра-
тичного программирования без ограничений,
для решения которой в [1] предложен эффек-
тивный подход, базирующийся на использо-
вании метода глобального равновесного по-
иска (ГРП) [2]. Второй подход к решению
рассматриваемых задач связан с известным
утверждением – k-раскраске графа соответ-
ствует разбиение множества его вершин на k
независимых множеств. Вершины, входящие
в независимые множества, окрашиваются в
один цвет. Для решения задачи разбиения
множества вершин графа в работе предложен
приближённый алгоритм. Проведено сравни-
тельное исследование эффективности из-
вестного из литературы [3] и данного алго-
ритмов, которое подтвердило преимущества
последнего.
Содержательная постановка. Задача рас-
краски графа состоит в раскраске его вершин
различными цветами таким образом, чтобы
никакие две смежные вершины не были ок-
рашены одинаково. Она возникает во многих
важных реальных приложениях.
Математические модели. Выделяют две
постановки задачи раскраски графа.
Задача 1. Пусть задан граф G = G(V, E),
где V и E – соответственно множества его
вершин и ребер. Имеется K цветов, в которые
можно окрасить каждую вершину.
* Работа выполнена при частичной финансовой
поддержке Украинского научно-технологического
центра (грант № 4138).
Компьютерная математика. 2009, № 2 159
В.П. ШИЛО
Введем переменные ikx , i=1 ,…, |V |, k=1 ,..., K, такие, что
1, если -я вершина окрашена -м цветом,
0 в противном случае,ik
i k
x ⎧
= ⎨ −⎩
где |V | – мощность множества . V
Необходимо установить, можно ли раскрасить вершины графа, используя
все К цветов и соблюдая вышеперечисленные условия.
Математическая модель этой задачи состоит в нахождении таких значений
переменных ikx , которые удовлетворяют системе ограничений
1
1
K
ik
k
x
=
=∑ , i=1,..,|V |, (1)
, 1ik jkx x+ ≤ ( , )i j E∈ , k=1 ,..., K, (2)
ikx =0 , i=1 ,..., |V |, k=1 ,..., K, (3) 1∨
или в установлении факта, что таких значений не существует.
Ограничение (1) означает, что каждая вершина графа может быть окрашена
только одним цветом. Условие (2) указывает на то, что смежные вершины долж-
ны быть окрашены различными цветами.
Задача 2. Пусть задан граф G = G(V, E), где V и E – соответственно множест-
ва его вершин и ребер. Имеется максимальное число цветов, в которые мож-
но окрасить вершины графа (можно положить, например, =|V |).
K
K
Введем переменные ikx и , i=1 ,..., | |, k=1 ,..., K, такие, что ky V
1, если -я вершина окрашена -м цветом,
0 в противном случае,ik
i k
x ⎧
= ⎨ −⎩
1, если -й цвет используется в раскраске,
0 в противном случае.k
k
y
⎧
= ⎨ −⎩
Необходимо найти минимальное число цветов, которыми можно раскрасить
вершины графа при выполнении вышеназванных ограничений.
Математическая постановка этой задачи формулируется таким образом:
найти
, 1
min
K
k
x y k
y
=
∑ (4)
при условиях
1
1
K
ik
k
x
=
=∑ , i = 1 ,..., |V |, (5)
, 1ik jkx x+ ≤ ( , )i j E∈ , k = 1 ,..., K, (6)
Компьютерная математика. 2009, № 2 160
ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ РАСКРАСКИ ГРАФА
ik kx y≤ , i=1 ,..., | |, k=1 ,..., K, (7) V
ikx = 0 , i=1 ,..., | |, k=1 ,..., K. (8) 1∨ V
Отметим, что задачи 1 и 2 – NP-сложные.
Сведение рассматриваемых задач к известной модели. В работе [4] пред-
ложен способ сведения задач (1)–(3) и (4)–(8) к задаче булевого квадратичного
программирования без ограничений. Следуя [4], это можно сделать такими пре-
образованиями. Рассмотрим следующую задачу:
минимизировать
( )f x xQx= (9)
при ограничениях
Ax b= , (10)
0 1jx = ∨ , j=1 ,…, n. (11)
где Q – квадратная матрица порядка n, A – матрица размерностью m×n, x и b –
соответственно n-мерный и m-мерный векторы.
Эта модель объединяет как линейный, так и квадратичный случаи. Действи-
тельно, поскольку в силу булевости переменных справедливо равенство
2
j jx x= , j=1,…, n, то диагональная матрица позволяет представить линейную
функцию цели в виде (9). Для произвольной положительной штрафной кон-
станты P имеем
Q
~ ~
( ) ( ) ( )tf x xQx P Ax b Ax b xQx xDx c xQ x c= + − − = + + = + .
Таким образом, выбрав соответствующее значение P (что всегда возможно),
сведем задачу булевого квадратичного программирования с линейными ограни-
чениями вида (9)–(11) к следующей задаче:
минимизировать
~ ~
( )f x xQ x= (12)
при условиях
0 1jx = ∨ , j=1 ,…, n. (13)
Преобразование задачи (9)–(11) в задачу (12), (13) назовём первым преобра-
зованием.
Пусть E – некоторое множество пар индексов. Рассмотрим теперь такую
задачу:
минимизировать
( )f x xQx= (14)
при ограничениях
1, ( , )i kx x i k E+ ≤ ∈ , (15)
0 1jx = ∨ , j=1 ,…, n. (16)
Компьютерная математика. 2009, № 2 161
В.П. ШИЛО
Выбрав некоторую штрафную константу P, получим
~ ~
( , )
( ) i k
i k E
f x xQx P x x xQ x
∈
= + =∑ .
Назовем это преобразование вторым преобразованием. С его помощью
задача (14)–(16) также сводится к задаче (12), (13).
Подходы к решению поставленных задач. Как видим, постановки (1)–(3)
и (4)–(8) задачи раскраски графа с помощью первого и второго преобразований
сводятся к задаче безусловной минимизации – квадратичного программирова-
ния с булевыми переменными вида (12), (13). Для решения последней задачи
в работе [1] разработана модификация метода глобального равновесного поиска
[2], использующая в качестве поискового алгоритма метод табу.
Следует отметить, что для решения задач вида (12), (13) до появления рабо-
ты [1] лучшей считалась реализация алгоритма табу [5]. Результаты многочис-
ленных экспериментальных расчётов показали, что для задач большой размер-
ности алгоритм глобального равновесного поиска [1] лучше алгоритма табу [5]
как по качеству решений, так и по времени их нахождения.
В работе [4] приводятся результаты вычислительных экспериментов, кото-
рые свидетельствуют о том, что задача раскраски графа успешно решается бу-
дучи сформулированной в виде (12), (13). Постановка (12), (13) заключается во
введении штрафов за нарушение условий (1), (2) или (5), (6). В силу простоты
структуры ограничений (1) или (5) можно поддерживать их выполнение с по-
мощью специально выбранной системы ходов локальных процедур оптимиза-
ции, используемых алгоритмом глобального равновесного поиска, стартуя при
этом с начальной точки, которая удовлетворяет этим ограничениям. За наруше-
ние ограничений (2) или (6) можно вводить штрафы, аналогичные тем, которые
появляются в квадратичной модели (12), (13).
Таким образом, задачу (1)–(3) можно переформулировать в виде
минимизировать
{
1( , )
1
K
ik jk
k i j E
P x x
= ∈
}χ + >∑ ∑ (17)
при условиях
0 1, 1,..., , 1,..., ,ikx i V k= ∨ = = K (18)
1
1, 1,...,
K
ik
k
x i
=
V= = ∑ , (19)
где { } 1, если 1,
1
0 в противном случае;
ik jk
ik jk
x x
x x
+ >⎧⎪χ + > = ⎨
⎯⎪⎩
P – штрафная константа.
Компьютерная математика. 2009, № 2 162
ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ РАСКРАСКИ ГРАФА
Для задач построения помехозащищенных кодов максимального объема
представляет интерес следующая постановка:
минимизировать
{
2
1 1 1( , )
1
VK K
ik ik jk
k i k i j E
x P x
= = = ∈
⎛ ⎞
⎜ ⎟ }x+ χ + >
⎜ ⎟
⎝ ⎠
∑ ∑ ∑ ∑ (20)
при условиях
ikx =0 , i=1 ,..., |V |, k=1 ,..., K, (21) 1∨
1
1, 1,...,
K
ik
k
x i
=
V= = ∑ , (22)
где { } 1, если 1,
1
0 в противном случае;
ik jk
ik jk
x x
x x
+ >⎧⎪χ + > = ⎨
⎯⎪⎩
P – штрафная константа.
Для решения задач (17)–(19) и (20)–(22) на базе общей схемы метода ГРП
[6] разработаны оптимизационные алгоритмы.
Легко видеть, что множество вершин графа, окрашенных одним цветом, яв-
ляется независимым множеством. Поэтому задача раскраски графа может быть
сведена к задаче разбиения множества вершин графа на независимые множест-
ва. Следовательно, подход к решению последней задачи можно использовать
для решения задачи раскраски графа. Рассмотрим его.
Пусть задан граф G = (V, E), где V = { ,.., } и E ={ ,.., }– соответст-
венно множества его вершин и ребер, n =
1v nv 1e me
V , m = E . Подмножество вершин
I⊂V графа G называется независимым, если никакие две его вершины не связа-
ны ребром. Если для любого независимого множества I выполняется соотноше-
ние maxI ≥ I , то независимое множество называется максимальным не-
зависимым. Задача нахождения максимального независимого множества состоит
в отыскании независимого множества с максимальным количеством вершин.
Обозначим α(G) число элементов в максимальном независимом множестве
maxI
( )max max( )I G Iα = .
Задача поиска максимального независимого множества вершин графа
возникает также при нахождении кодов, корректирующих ошибки. Пусть nB –
множество n-мерных векторов, координаты которых принимают значения 0
или 1. Рассмотрим алфавит , состоящий из всех двоич-
ных векторов длиной k. Каждому вектору поставим в соответствие вершину
графа G (V, E). Предположим, что из-за ошибок при передаче информации
вектор может переходить в один из элементов множества
{ }, , 1,...,2k
i iA l l B i= ∈ = k
il
il
iR , 1,...,2 .ki =
Компьютерная математика. 2009, № 2 163
В.П. ШИЛО
Определим, что в графе G(V, E) ребро ( , )∈E тогда и только тогда, когда iv jv
i jR R∩ ≠ ∅. Очевидно, что если найдено независимое множество в G(V, E),
то тем самым найден код, корректирующий ошибки.
Разбиением множества вершин графа на независимые множества является
множество ( ) таких независимых множеств графа G (V, E), что каждая
вершина графа принадлежит только одному независимому множеству.
1,..., kIS IS
Особый интерес представляют следующие задачи разбиения:
• с минимальным числом k разбиений,
• с максимальным значением 2
1
k
i
i
IS
=
∑ нормы.
В первом случае задача разбиения множества вершин графа эквивалентна
задаче раскраски графа. Второй случай важен [3] при построении помехозащи-
щенных ассиметрических кодов (Z-канал). Поскольку эти задачи являются
NP-сложными, важной проблемой является разработка эффективных прибли-
женных алгоритмов их решения.
Рассмотрим один из возможных подходов к получению приемлемого раз-
биения множества вершин графа G (V, E) на независимые множества. Вначале
находится максимальное независимое множество исходного графа G (V, E).
Затем из графа G (V, E) исключаются вершины максимального независимого
множества с принадлежащими им ребрами, т.е. новый граф имеет вид
. Далее находится максимальное независимое множество
нового графа. Процесс продолжается до тех пор, пока не будет получено
разбиение.
1IS
1IS
1\ 1 \( \ , )V IS V ISG V IS E
1
2IS
С нашей точки зрения этот подход можно улучшить следующим образом.
Изменение состоит в нахождении (если это возможно) на каждом этапе задан-
ного числа максимальных независимых множеств соответствующего графа. Да-
лее строится специальный граф N, вершины которого соответствуют найденным
максимальным независимым множествам. Между двумя вершинами этого графа
имеется ребро тогда и только тогда, когда соответствующие максимальные не-
зависимые множества имеют общие вершины. Затем находится несколько мак-
симальных независимых множеств графа N и по некоторому правилу среди них
выбирается лучшее (например, по количеству ребер, исходящих из соответст-
вующих максимальных независимых множеств).
Схему предлагаемого алгоритма можно представить в виде следующих
процедур:
while(|V| > 0 )
{ for j = 1 to m
{ нахождение jIS
Компьютерная математика. 2009, № 2 164
ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ РАСКРАСКИ ГРАФА
if | |<| | break } jIS 1jIS −
формирование графа N
нахождение максимального независимого множества MIS графа N
G = } \ \( \ , )V MIS V MISG V MIS E
Заметим, что только при j = 1 число итераций будет максимальным, так как
для j > 1 уже известна мощность максимального независимого множества.
Результаты экспериментальных расчетов. С целью проверки эффектив-
ности предложенного алгоритма был проведен вычислительный эксперимент по
решению задачи разбиения множества вершин графа на независимые множества
для графов, возникающих при построении помехозащищенных кодов. Исполь-
зовались графы из семейств, которые возникают при построении кодов, коррек-
тирующих
• удаление одного бита – ldc,
• удаление двух битов – 2dc,
• единичную ошибку в Z-канале – lzc.
Подробнее с этими графами можно ознакомиться на сайте
http://www.research.att.com/~njas/doc/graphs.html. Для поиска максимального не-
зависимого множества вершин графа использовался алгоритм, описанный в [6].
В столбце α(
_
G ) приведены наибольшие известные числа α(
_
G ).
В табл. 1 содержатся результаты решения задачи разбиения множества вер-
шин для графов, являющихся дополнениями графов семейств 1dc, 2dc.
Получение разбиений множества вершин на независимые множества для
графа lzc имеет важное значение, так как эти данные могут быть использованы
для нахождения нижних оценок объема помехозащищенных кодов для Z-канала.
В табл. 2 приведены данные, полученные в [3]. (В табл. 2 и 3 для графов
lzc512 значение α(G) = 62, для графов lzc1024 – α(G) = 112).
ТАБЛИЦА 1. Полученные разбиения
Количество
Граф
_
G узлов ребер α(
_
G ) Разбиение
1dc512 512 121089 10 23(10),4(9),6(8),10(7),5(6),
6(5),10(4),7(3),2(2),3(1)
1dc1024 1024 499713 11
37(11),8(10),11(9),13(8),
12(7),13(6),10(5),18(4),
9(3),7(2),9(1)
2dc512 512 75221 58 58,51,3(46),38,37,36,28,
26,2(22),16,14,11,6,5,4
2dc1024 1024 354614 72
72,64,5(56),53,2(49),44,42,
39,2(37),32,29,28,26,22,21,
17,2(15),14,11,9,7,5, 2(3),1
Компьютерная математика. 2009, № 2 165
http://www.research.att.com/%7Enjas/doc/graphs.html
В.П. ШИЛО
ТАБЛИЦА 2. Разбиения, полученные в [3]
Количество
Граф узлов ребер Разбиение Норма k
4(62),58,54,51,44,34,
19,4 27726 11
lzc512 512 123904
4(62),2(56),52,44,30,
20,6 27624 11
lzc1024 1024 507135 112,2(110),109,104,9
8,95,87,75,61,46,14,3 97306 13
Табл. 3 содержит данные, полученные при решении задач предложенным
алгоритмом. Звёздочка в колонке “Норма” этой таблицы указывает на то, что
разбиения найдены при решении задачи (20)–(22).
ТАБЛИЦА 3. Разбиения, найденные предложенными алгоритмами
Количество Граф узлов ребер Разбиение Норма K
1 2 3 4 5 6
4(62),58,56,53,46,
31,16,4
28034 11
3(62),61,58,56,53,
46,29,18,5
27868 11 lzc512 512 123904
4(62),58,56,53,43,
32,16,6
27850 11
3(62),61,58,56,52,
46,31,17,5
27848 11
4(62),59,56,49,41,
38,18,3
27852* 11
4(62),58,56,52,43,
33,17,5
27832
4(62),58,56,54,42,
31,15,8
27806 11
lzc1024 1024 507135
112,2(110),108,105,
101,98,88,77,60,
40,13,2
98284* 13
112,2(110),109,108,
100,95,87,75,60,
44,13,1
98214* 13
Компьютерная математика. 2009, № 2 166
ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ РАСКРАСКИ ГРАФА
Окончание табл. 3
1 2 3 4 5 6
112,110,2(109),104,
103,95,89,75,61,
41,14,2
98004 13
112,2(110),108,105,
101,96,90,76,57,
41,17,1
97946 13
112,2(110),109,105,
100,99,88,75,59,
37,16,4
97942 13
112,2(110),109,105,
101,96,87,77,60,
38,15,4
97850 13
112,2(110),108,106,
99,95,89,76,60,
43,15,1
97842 13
112,2(110),108,105,
100,96,88,74,65,
38,17,1
97828 13
112,2(110),108,106,
103,95,85,76,60,
40,15,4
97720 13
112,2(110),108,106,
101,95,87,75,61,
40,17,2
97678 13
112,110,109,108,105,
101,96,86,78,63,
36,17,3
97674 13
Табл. 4 содержит результаты решения предложенными алгоритмами задачи
le450_5a, взятой из сайта http://mat.gsia.cmu.edu/COLOR/instances.html. Звёздочкой
в колонке “Время” отмечено среднее время решения задачи по 10 просчётам.
ТАБЛИЦА 4. Время решения задачи le450_5a
Количество
узлов ребер Алгоритм Время, с
K
Данные взяты из [4] 1027 5
ГРП для задачи (17)–(19) 337* 5 450 5714
ГРП для задачи (20)–(22) 171* 5
Компьютерная математика. 2009, № 2 167
http://mat.gsia.cmu.edu/COLOR/instances.html
В.П. ШИЛО
Заключение. Найдены новые окраски графов lzc512, lzc1024, возникающих
при построении помехозащищенных кодов, с нормой, большей чем в [3, 7].
Это позволило, в свою очередь, улучшить нижние оценки для кодов длиной
m = 19, 21, 22, 24.
В.П. Шило
ПІДХОДИ ДО РОЗВ’ЯЗАННЯ ЗАДАЧІ РОЗФАРБУВАННЯ ГРАФА
Запропоновано два підходи до розв’язання задачі розфарбування графа. Проведено
порівняльне дослідження ефективності відомих для даної задачі і розроблених алгоритмів,
яке підтвердило переваги запропонованих підходів.
V.P. Shylo
APPROACHES TO THE GRAPH PAINTING PROBLEM SOLVING
Two approaches to the Vertex Coloring Problem solving are proposed. The comparative investiga-
tion of the efficiency of the proposed one and other methods known for this problem are provided,
which confirmes the advantages of the approach proposed.
1. Pardalos P.M., Prokopyev O.A., Shylo O.V., Shylo V.P. Global equilibrium search applied to
the unconstrained binary quadratic optimization problem // Optimization Methods and Soft-
ware. –2008. – 23. – P. 129 – 140.
2. Шило В.П. Метод глобального равновесного поиска // Кибернетика и системный ана-
лиз. – 1999. – № 1. – С. 74–81.
3. Etzion T., Ostergard P. R. J. Greedy and heuristic algorithms for codes and colorings // IEEE
Trans. Inform. Theory. – 1998. – 44, N 1. – P. 382–388.
4. Kochenberger G. A. , Glover Fred., Alidaee B., Rego C. An Unconstrained Quadratic Binary
Programming Approach to the Vertex Coloring Problem // Ann. Oper. Res. – 2005. – 139,
N 1. – P. 229 – 241.
5. Palubeckis G. Multistart tabu search strategies for the unconstrained binary quadratic
optimization problem // Annals of Oper. Res. – 2004. – 131. – P. 259–282.
6. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы реше-
ния, исследования. – Киев: Наук. думка, 2003. – 264 с.
7. Шило В.П. Новые нижние оценки объема помехозащищенных кодов для Z-канала //
Кибернетика и систем. анализ. – 2002. – № 1. – С. 19 – 23.
Получено 14.04.2009
Îá àâòîðå:
Шило Владимир Петрович,
доктор физико-математических наук, ведущий научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
e-mail: v.shylo@gmail.com
Компьютерная математика. 2009, № 2 168
|