Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 31
Текст из файла (страница 31)
Для получения такой оценки достаточно заметить, что о~ 7 Ь(х, ц). Окончательно получаем, оь д7еА что алгоритм пометок имеет сложность 0(( Х Ь(х, у)) /А!~. В следующей главе мы увидим, что эта оценка в худшем случае действительно достигается. Пример 8.8. Симплекс-алгоритм гак же, как алгоритм пометок из примера 8.7, включает в себя начальный шаг и некоторое число итераций. Если матрица А имеет размеры тхп, го начальный шаг требует 0(тп) арифметических операций. Аналогично, каждую итерацию можно грубо рассматривать как умножение матрицы на вектор, и, следовательно, ее также можно выполнить за 0(ииг) арифметических операций.
Поскольку зацикливание устранено, симплекс-метод может в худшем случае пройти по всем базисным допустимым решениям, число которых не превосходит ( +"). В 8 8.б мы покажем, что действительно существуют задачи ЛП, в которых симплекс-алгоритм вынужден выполнять много (хотя н не ровно ("'+")) итераций. С) 168 Гл. В. Ллгоритмы и слоягнасть в.з Попмноммапьиые т] аягормтмы В каком случае вычислительную задачу можно считать удовлетворительно решенной? Ответ, очевидно, содержится в поведении алгоритмов, известных для этой задачи. Задачу можно считать решенной в том и только в том случае, если существует алгоритм ее решения, требующий не слишком много времени (это основной критерий, которым мы будем пользоваться). Фактически, как было указано выше, практическая польза алгоритма определяется скоростью роста наилучшей из известных оценок времени. Какие же скорости роста следует считать приемлемыми для решения вычислительных задач? В настоящее время среди специалистов по вычислительным наукам широко распространено мнение, что алгоритм окажется практически полезным для вычислительной задачи только в том случае, если его сложность растет полиномиально относительно размера входа.
Например, при таком подходе алгоритмы со сложностью 0(п) или О~пи) приемлемы. (Заметим, что полиномиальная скорость роста полностью определяется степенью полинома.) Также, естественно, допускаются алгоритмы, асимптотическая сложность которых не выражается полицомом, ио ограничена полиномом. Примерами могут служить оценки п'-1' и п (од п. Чтобы понять значение класса полиномиально ограниченных алгоритмов, рассмотрим те алгоритмы, сложность которых для достаточно больших индивидуальных задач превосходит любую полиномиальную оценку.
Обычно эти алгоритмы называют экспоненциальными, поскольку 2" является представителем неполииомиальных скоростей роста. К примерам экспоненциальных скоростей роста относятся А" (при любом фиксированном )г)1), п1, 2 ', пи и и"я" '). Очевидно, что с ростом размера входа любой полиномиальный алгоритм станет в конечном итоге более эффективным, чем любой экспоненциальный алгоритм (см. табл, 8.1). Другая положительная особенность полиномиальных алгоритмов заключается в том, что они в некотором смысле лучше используют достижения технологии. Например, каждый раз, когда технологические достижения приводят к увеличению скорости ЭВМ в 1О раз, наибольший размер задач, решаемых полиномиальным алгоритмом, скажем за ') В оригинале ро1упощ)з!-1)ще.
Этот термин введен в последнее время в ниострзнной литературе для того, чтобы различать алгоритмы, полиномизльные относительно времени и полнномизльные относительно пзмятп (ро1упощ)з!-зресе). Однвко мы сочли возможным дать упрощенный перевод этого термине, поскольку алгоритмы, полиномизльиые относительно времени, являютси автоматически и полиномнзльными относительно памяти, тзк что их естественно называть просто полиномиельнымн.— Прим.
лгргг. ') Скорости роста, такие, кзк пм, которые превосходят любой полипом, но меныпе чем 2лг для любого е)0, называются иногда губгкгпояенчиальными. 8.8. Полиномиальнеы алгоритмы час, умножается на константу, заключенную между 1 и 10. В противоположность этому для экспоненциального алгоритма произойдет всего лишь аддитивное увеличение размера задачи, которую этот алгоритм может решить за фиксированное время (см. табл. 8.2). Наконец, отрадно отметить, что полиномиальные алгоритмы обла- Таблица 8П Рост поаипомиааьиых и еиспоиепциальпых фупиций дают свойством «замкнутости»: можно комбинировать полиномиальные алгоритмы для решения частных случаев одной и той же задачи; один погиномнальный алгоритм может вызывать другой в качестве «подпрограммы», при этом в целом алгоритм останется полиномиальным.
При разделении алгоритмов на полиномиальные и экспоненциальные необходима особая осторожность в тех случаях, когда оценка времени включает в себя численные входные данные задачи. Например, для алгоритма пометок была получена оценка времени 0 ((~~'см «~«л Ь Гх, и)) ! А /) (см. пример 8.7). На первый взгляд кажется, что эта функция асимптотически растет как полипом, поскольку в ней нет явной экспоненты или эквивалентной операции. Тем не менее эта функция не будет полиномиально ограниченной огносительно размера входа, и связано это с тем, что она выражена через численные входные данные задачи. Чтобы продемонстрировать это, допустим, что все дуги в сети имеют пропускную способность 2~ л ~. Индивидуальную задачу о максимальном потоке можно закодировать, выписывая (А~ целых чисел, каждое с ~А ~ разрядами; так что размер этой индивидуальной задачи есть 0((А ~'-').
С другой стороны, оценка времени принимает вид 0(2г л ~ ° (А Р), и эта функция не является полиномиальной относительно размера рассматриваемой задачи. В гл. 1б для алгоритмов с подобными временными оценками будет введен термин пссадололиномиальиосшо. 170 Гл. 8. Алеориглмы и слокносгль А будет ли алгоритм с оценкой пм практическим решением задачи? Вероятно, нет. Уже время, необходимое для решения индивидуальной задачи размера 3, выражается астрономическим числом, и может оказаться, что некоторый экспоненциальный алгоритм работает лучше при всех разумных входных данных.
Таким Таблица 8.2 Полнномнельные алгоритмы лучше используют успехн технологии образом, утверждение о том, что полииомиальные алгоритмы <хороши» в экстремальной ситуации, выглядит сомнительным. Однако в поддержку этого утверждения выступает опыт. При решении большинства задач как только обнаруживается какой-нибудь полиномиальный алгоритм, так сразу же степень полииома быстро претерпевает ряд уменьшений. Это вызвано тем, что различные исследователи улучшают идею алгоритма. Обычно окончательно получается скорость роста 01п») или лучше.
Экспоненциальные алгоритмы, напротив, требуют на практике столько же времени, сколько и в теории, и от них тут же отказываются, как только для той же задачи обнаруживается полиномиальный алгоритм. Эти эмпирические правила отнюдь не универсальны и в некоторых случаях могут оказаться совершенно неверными. В следующих двух параграфах мы рассмотрим основания полемики, ведущейся вокруг симплекс-алгоритма и недавно открытого полиномиального алгоритма для ЛП. В ходе полемики были выдвинуты наиболее серьезные контраргументы утверждению о том, что поликомиаланый и практический — синонимы. а.о.
Симялекс-алгоритм ме яеляется яолияомиальяам 171 8.6 Симплекс-алгоритм не является полиномиальным Среди обсуждавшихся в предыдущих главах алгоритмов симплекс-алгоритм — самый важный. Поэтому естественно попытаться применить к нему предложенный в предыдущем параграфе математический критерий выделения «хорошихь алгоритмов и выяснить, полиномиальный ли он. В данном параграфе мы представим простые аргументы, принадлежащие Кли и Минти (КМ), устанавливающие, что симплекс-алгоритм не полиномиален. Симплекс-алгоритм, приведенный на рис. 2.3, содержит не полностью определенный шаг: выбор 1. Анализ такого алгоритма в худшем случае означает нахождение а) самой неблагоприятной индивидуальной задачи и б) самой неудачной последовательности выборов на не полностью определенных шагах.
Поэтому для доказательства того, что симплекс-алгоритм не полиномнален, достаточно представить семейство индивидуальных задач, на которых он может использовать экспоненциальное число замещений. Для этого достаточно представить экспоненциальную (относительно размере задачи ЛП) последовательность базисных допустимых решений к„сь ..., я„такую, что х; и х,, смежны и удовлетворяют неравенству а'я;е, -с'х, при всех 1=1, ..., й — 1. В этом месте удобно привлечь некоторую геометрическую интуицию. Нам известно (теорема 2.2), что базисные допустимые решения (бдр) задачи ЛП являются вершинами соответствующего многогранника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
