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


[Старт] [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]


133

Рис. 12.7

С интуитивной точки зрения этот алгоритм кажется весьма разумным. Он не начинает заполнять новый контейнер, пока среди контейнеров есть хотя бы один, в который можно поместить очередной предмет.

Проанализируем насколько близко к оптимальному решение, полученное алгоритмом «в первый подходящий». Вначале рассмотрим число контейнеров, требующихся для указанного алгоритма, как функцию от параметров задачи. Обозначим эту функцию как FF(r). Имеют место неравенства:

FF(r}> 1

FF(7)<[2 is(Uin i=\

Последнее неравенство следует из того, что в результате работы алгоритма не может получиться более одного контейнера, заполненного более чем на половину. В противном случае первый же предмет, попавший в такой контейнер с наибольшим номером, должен быть помещен алгоритмом «в первый подходящий», т.е. такой же контейнер с тем же номером. То, что указанная граница наилучшая из возможных, следует из рассмотрения индивидуальной задачи V= {С/1, U2, ... Un}, где S(Ui) = Vi + г; \ < i < п. Поскольку никакие два предмета не могут попасть в один ящик, то FF(r) = «, в то время как сумма размеров предметов равна п/2 + пе и если е достаточно малое, то она будет как угодно близка к п/2.

Сделанное замечание позволяет нам также оценить, во сколько раз плохое решение, получаемое алгоритмом «в первый подходящий» может отличаться от оптимального решения задачи. Поскольку ясно, что

ОРГ(/)>[Г5(С/0], / = 1



то отсюда вытекает, что для всех индивидуальных задач I вытекает неравенство FF{I) < 20РТ(1).

В [34] приводится теорема, что для FF(I) имеется лучшая оценка.

Теорема 12.2. Для всех индивидуальных задач / об упаковке имеет место неравенство FF(I) < 17/10 ОРТ(Г) + 2.

Более того, существует индивидуальная задача /, для которой ОРТ(1) сколь угодно велико FF(l) > 17/10 (ОРТ(1) - 1).

Таким образом, теорема 12.2 характеризует асимптотическое поведение в худшем случае алгоритма «в первый подходящий». Величина FF(r) никогда не отличается от оптимума более чем на 70% и в некоторых случаях такое отличие действительно достигается.

Далее перейдем к анализу алгоритмов с лучшей оценкой поведения. Ясно, что алгоритм «в первый подходящий» можно видоизменить, пользуясь, например, следующим более совершенным правилом размещения: каждый следующий предмет Ui помещать в контейнер, содержимое которого ближе всего к величине 1 - Si(U), но не превосходит ее (если имеется несколько таких контейнеров, то выбирается контейнер с наименьшим номером). Этот алгоритм называется «в наилучший из подходящих». Этот алгоритм, как показано в [34], в наихудшем случае имеет те же характеристики, что и алгоритм «в первый подходящий».

Несколько лучший приближенный алгоритм получается, если учесть, что наихудшей для алгоритма «в первый подходящий» (а также для алгоритма «в наилучший из подходящих») оказывается ситуация, когда в упорядочении предметов предметы с наибольшими размерами идут раньше предметов с наименьшими размерами, т.е. S(U\) > S(U2) > ... > S{Uri). Алгоритм применения процедуры «в первый подходящий» к переупорядоченному таким образом списку предметов называется «в первый подходящий в порядке убывания» (соответствующая функция обозначается FFD(I)y Работа этого алгоритма характеризуется следующей теоремой Джонсона.

Теорема 12.3. Для всех индивидуальных задач об упаковке выполняется неравенство FFD(I) < (11/9) ОРТ(1) + 4.

Более того, существуют индивидуальные задачи, для которых 0РТ{1) произвольно велико и FFD(I) > (11/9) OPT(I).

Таким образом, мы имеем гарантию, что алгоритм «в первый подходящий в порядке убывания» даже в худшем случае выдает решение, отличающееся от оптимального не более чем на 22%. Более того, встречаются задачи, для которых эта оценка достигается. Такой же результат



имеет место для аналогичного алгоритма «в наилучший из подходящих в порядке убывания».

Нетрудно понять причину, в силу которой желательно иметь такие оценки погрешностей приближенных алгоритмов. Даже если конкретная оценка погрешности не столь сильна как хотелось бы, тем не менее весьма разумно начать решение задачи с простого алгоритма, имеющего такую оценку погрешности, а затем улучшить ее, пользуясь более совершенными эвристиками и методами оптимизации. Естественно, наибольший интерес для нас представляет, в какой степени наш алгоритм «на практике» будет приближен к оптимальному. В качестве альтернативы к анализу погрешности алгоритмов «в худшем случае» можно было бы попытаться оценить погрешность «в среднем». Изучение поведения алгоритмов «в среднем» чаще всего сводится к формированию типовых индивидуальных задач и апробации нескольких алгоритмов на этих задачах с последующим сравнением результатов.

[Старт] [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]