Дискретные задачи размещения ballred.gif (861 bytes) Библиотека тестовых задач
line.jpg (1129 bytes)

ballred.gif (861 bytes) Библиотека тестовых задач ballred.gif (861 bytes) Задача о p-медиане ballred.gif (861 bytes)

Примеры на совершенных кодах

Пусть Bk множество слов (векторов) длины k из алфавита {0, 1}. Бинарным кодом длины k  назовем произвольное непустое подмножество из Bk. Совершенный бинарный код с расстоянием 3 есть подмножество C Ì Bk, | C | = 2k/(k+1) такой, что расстояние Хэмминга d(c1, c2) 3 для всехl c1, c2Î C, c1¹ c2. Такие коды существуют для k = 2r – 1, где  r > 1 целое. Положим n = 2k, n/(k + 1), I J = {1,…,  n}. Каждый элемент iÎI соответствует вершине x(i) булева гиперкуба Z2k . Следовательно можно определить расстояние dij = d(x(i), x(j))  для любых двух элементов i, jÎI.  Далее, обозначим 

где  xij — случайное число из множества {0, 1, 2, 3, 4} с равномерным распределением. Любой совершенный код C порождает разбиение булевого гиперкуба Z2k на  непересекающихся шаров единичного радиуса. Каждое такое разбиение соответствует допустимому решению задачи о p-медиане. Число совершенных кодов растет экспоненциально с ростом k. Наилучшая известная нижняя граница на число совершенных кодов получена Д. Кротовым и имеет вид

Минимальное расстояние между двумя совершенными кодами или допустимыми решениями задачи о p-медиане не менее

Примеры для   k = 7,  p = 16, n = m = 128  приведены в таблице:

(Архив со всеми примерами на совершенных кодах mp-pc.zip 109 Kb)

Номер Оптимум

Разрыв
двойственности
 (%)

Оптимальное решение

 334

 232

 5.98

 5, 12, 24, 25, 35, 46, 50, 63, 66, 79, 83, 94, 104, 105,  117, 124

 434

 217

 2.72

 2, 11, 23, 30, 40, 45, 49, 60, 69, 80, 84, 89, 99, 106, 118, 127

 534

 227

 1.25

 3, 13, 18, 32, 40, 42, 53, 59, 70, 76, 87, 89, 97, 111, 116, 126

 634

 219

 1.96

 1, 12, 23, 30, 38, 47, 52, 57, 72, 77, 82, 91, 99, 106, 117, 128

 734

 223

 4.14

 3, 13, 18, 32, 40, 42, 53, 59, 70, 76, 87, 89, 97, 111, 116, 126

 834

 215

 1.46

 3, 16, 22, 25, 37, 42, 52, 63, 66, 77, 87, 92, 104, 107, 113, 126

 934

 221

 1.92  4, 14, 23, 25, 37, 43, 50, 64, 65, 79, 86, 92, 104, 106, 115, 125

1034

 217

 2.48

 2, 7, 27, 30, 44, 45, 49, 56, 73, 80, 84, 85, 99, 102, 122, 127

1134

 220

 4.40

 4, 9, 22, 31, 37, 48, 51, 58, 71, 78, 81, 92, 98, 107, 120, 125

1234

 223

 1.51

 4, 13, 23, 26, 38, 43, 49, 64, 65, 80, 86, 91, 103, 106, 116, 125

1334

 211

 1.51

 6, 12, 17, 31, 35, 45, 56, 58, 71, 73, 84, 94, 98, 112, 117, 123

1434

 226

 2.77

3, 13, 24, 26, 34, 48, 53, 59, 70, 76, 81, 95, 103, 105, 116, 126

1534

 209

 0.17

 8, 11, 21, 26, 34, 45, 51, 64, 65, 78, 84, 95, 103, 108, 118, 121

1634

 226

 0.17

 7, 10, 22, 27, 36, 45, 49, 64, 65, 80, 84, 93, 102, 107, 119, 122

1734

 221

 0.17

 12, 13, 18, 23, 33, 40, 59, 62, 67, 70, 89, 96, 106, 111, 116 117

1834

 225

 1.95

 1, 8, 27, 30, 42, 47, 52, 53, 76, 77, 82, 87, 99, 102, 121, 128

1934

 222

 1.74

 4, 15, 21, 26, 38, 41, 51, 64, 65, 78, 88, 91, 103, 108, 114, 125

2034

 205

 0.00 

 8, 11, 21, 26, 33, 46, 52, 63, 66, 77, 83, 96, 103, 108, 118, 121

2134

 226

 0.77

 4, 13, 23, 26, 33, 48, 54, 59, 70, 75, 81, 96, 103, 106, 116, 125

2234

 229

 2.79

 6, 11, 17, 32, 39, 42, 52, 61, 68, 77, 87, 90, 97, 112, 118, 123

2334

 215

 0.74

 3, 14, 21, 28, 34, 47, 56, 57, 72, 73, 82, 95, 101, 108, 115, 126

2434

 212

 2.83

2, 11, 21, 32, 40, 45, 51, 58, 71, 78, 84, 89, 97, 108, 118, 127

2534

 209

 0.80

 7, 9, 22, 28, 34, 48, 51, 61, 68, 78, 81, 95, 101, 107, 120, 122

2634

 207

 1.31

 7, 14, 18, 27, 33, 44, 56, 61, 68, 73, 85, 96, 102, 111, 115, 122

2734

 220

 0.48

 8, 11, 18, 29, 33, 46, 55, 60, 69, 74, 83, 96, 100, 111, 118, 121

2834

 220

 2.06

 12, 13, 19, 22, 33, 40, 58, 63, 66, 71, 89, 96, 107, 110, 116, 117

2934

 207

 0.00

 2, 15, 24, 25, 35, 46, 53, 60, 69, 76, 83, 94, 104, 105, 114, 127

3034

 222

 0.00

 2, 13, 23, 28, 35, 48, 54, 57, 72, 75, 81, 94, 101, 106, 116, 127

3134

 223

 2.37

 6, 11, 23, 26, 33, 48, 52, 61, 68, 77, 81, 96, 103, 106, 118, 123

3234

 204

 3.44

 8, 13, 17, 28, 34, 43, 55, 62, 67, 74, 86, 95, 101, 112, 116, 121

ballred.gif (861 bytes) Библиотека тестовых задач ballred.gif (861 bytes) Задача о p-медиане ballred.gif (861 bytes)