Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[287]

Идея алгоритма проста: если через Рг- обозначить множество всех чисел, которые можно получить, складывая некоторые из

Х1,Х2,... , Xi, то

Pi = Pi-i U (Рг ! + Xi)(37.11)

(элемент жг- может не входить в сумму, а может и входить) мы видим (индукция по г, упражнение 37.4-1), что Li представляет собой список элементов множества Рг- в порядке возрастания (из которого выброшены элементы, большие t).

Сколько времени требует этот алгоритм? Список Li может содержать до 2г элементов, так что алгоритм экспоненциален. Впрочем, если t (или все элементы S) ограничено сверху многочленом от \S\, то время работы алгоритма также ограничено многочленом от \S\.

Полностью полиномиальная схема приближения Такая схема получается из описанного алгоритма, если хранить списки Li в сокращенной форме. Степень сокращения опредеояет-ся параметром 8 - чем он меньше, тем ближе список к полному. Список V называется -сокращением списка L, если V является частью L и для любого элемента у из L в списке V найдётся не превосходащий его элемент z, для которого

У-8 У

или, другими словами,

(1 - $)У z у.

Тем самым любой элемент у, выброшенный из L при получении меньшего списка V, представлен в V своим приближением снизу с относительной ошибкой (относительно у) не более 8. Например, для 8 = 0,1 и

L = (10,11,12,15,20,21,22, 23, 24, 29)

список

L = (10,13,15,20,23,29)

является -сокращением L, в котором выброшенное число 11 представлено числом 10, числа 21 и 22 представлены числом 20, а число 24 представлено числом 23. Важно иметь в виду, что 5-сокращение является частью оригинального списка. При этом число элементов может сильно уменьшится, но для всех выброшенны элементов чуть меньшие значения останутся.

Следующая процедура сокращает список L = (у\, у2, , ут), упорядоченный по возрастанию, за время О (то). Её результат V является 5-сокращеним L; список V также упорядочен по возрастанию.


\textsc{Trim} (L, \delta)

1m <- L

2L <- <y l>

3last <- y l

4for i<-2 to m

5do if last < (l-\delta) y i

6then дописать $y i$ в конец списка L

7last <- y i

8return L

Элементы списка L просматриваются в порядке возрастания, и в V помещается первый из них, а также те, которые слишком велики, чтобы быть представленными последним из уже имеющихся элементов списка V.

Теперь схема приближения для задачи о суммах подмножеств может быть построена следующим образом. Напомним, что исходными данными для неё являются последовательность S = (xi, х2,... ,хп) из п чисел (идущих в произвольном порядке), число t, а также параметр приближения е (в интервале 0 < е < 1).

\textsc{Approx-Subset-Sum}(S,t,\varepsilon)

1n <- SI

2L 0 <- <0>

3for i<-l to n

4do L i <- Merge-Lists(L {i-l>,L {i-l>+x i)

5L i <- Trim (L i, \varepsilon/n)

6все элементы $L i$, большие $t$, удаляются

7z <- наибольший элемент $L n$

8return z

Вначале (строка 2) в список Lq помещается единственный элемент 0. В строках 3-6 мы последовательно (для г = 1,...п) вычисляем список Li, который окажется сокращением множества Pi (всевозможных сумм, составленных из первых г элементов) из которого удалены все элементы, большие t. Отметим, что это требует специальной проверки, так как сокращения производятся на каждом шаге, и в строке 4 соединяются уже сокращенные варианты списков.

Прежде чем проверять это, рассмотрим пример: пусть

L = (104,102,201,101)

при этом t = 308 и е = 0,2. Тогда на каждом шаге производиться 0,05-сокращение, и вычисления проходят так:

строка 2: L 0 = <0>,


строка

4

L l

=

<0,104>

строка

5

L l

=

<0,104>

строка

6

L l

=

<0,104>

строка

4

L 2

=

<0,102,104,206>

строка

5

L 2

=

<0,102,206>

строка

5

L 2

=

<0,102,206>

строка

4

L 3

=

<0,102,201,206,303,407>

строка

5

L 3

=

<0,102,201,303,407>

строка

6

L 3

=

<0,102,201,303>

строка

4

L 4

=

<0,101,102,201,203,302,303,404>

строка

5

L 4

=

<0,101,201,302,404>

строка

6

L 4

=

<0,101,201,302>

В ответе получается z = 302, что отличается от оптимального варианта (307 = 104+102+101) менее чем на 2% (что много меньше разрешённого отклонения в 20%).

Теорема. Алгоритм Approx-Subset-Sum представляет собой полностью полиномиальную схему приближения для задачи о сумме подмножества.

Доказательство. Обе операции (сокращение списка в строке 5 и удаление слишком больших элементов в строке 6) могут лишь уменьшить список, так что список Li остаётся подмножеством множества Д. (Напомним, что через Pi обозначается множество всех чисел, которые можно получить, складывая некоторые из Ж1,Ж2,... , Xi.) Таким образом, число z действительно будет суммой некоторого подмножества, причём z t. Осталось проверить лишь, что оно не меньше (1-е), умноженного на максимально возможную сумму, не превосходящую t. (Именно этого требует неравенство (37.2) для нашейго случая.)

Посмотрим, к какой ошибке приводит сокращение списка на каждом шаге. При сокращении остающееся число будет меньше вычеркнутого, но не намного: не более чем на (е/п)-ую долю. Другими словами, остающийся элемент не меньше вычеркнутого, умноженного на (1 - е/п). Рассуждая по индукции, легко видеть, что для всякого элемента у множества Pi, не превосходящего t, можно указать элемент z в списке Li, для которого

В частности, при г = п можно взять в качестве у оптимальное решение задачи о сумме подмножества и убедиться, что существует z £ Ln, для которого

(1 -е/п)пу <z <у



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]