Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 207
Текст из файла (страница 207)
* Сформулируйте задачу поиска кратчайшего пути из одного источника в виде задачи линейного программирования для задачи поиска циркуляции минимальной стоимости. Заключительные замечания В данной главе мы только приступили к изучению обширной области линейного программирования. Множество авторов написали книги, посвяшенные исключительно линейному программированию. Среди них Чватал (СЬч61а1) (68), Гасе (Оазз) (129), Карлов (Каг!ой) (196), Шрайвер (ЯсЬп1чег) (301) и Ванлербей (ЧапдегЬе() (342]. Во многих других книгах линейное программирование подробно рассматривается наряду с другими вопросами (см., например, работы Пападимитриу (Рарж)пп)цтоц) и Штейглиц (В1е)й!йх) (269) и Ахуя (АЬща), Магнанти Глава 29.
Линейное нрограммирование 939 (Майпапй) и Орлин (Огйп) [7]). Изложение в данной главе построено на подходе, предложенном Чваталом (СЬнага1). Симплекс-алгоритм для задач линейного программирования был открыт Дж. Данцигом (О. Пап!х!й) в 1947 году. Немного позже было обнаружено, что множество задач из различных областей можно сформулировать в виде задач линейного программирования и решить с помощью симплекс-алгоритма. Осознание этого факта привело к стремительному росту использования линейного программирования и развитию его алгоритмов. Различные варианты симплекс-алгоритма остаются наиболее популярными методами решения задач линейного программирования. Эта история описана во многих работах, например в примечаниях к [68] и [196]. Эллипсоидный алгоритм, предложенный Л.Г.
Хачияном в 1979 году, стал первым алгоритмом решения задач линейного программирования с полиномиальным временем выполнения. Он был основан на более ранних работах Н.З. Шара, Д.Б. Юдина и А.С. Немировского. Испольювание эллипсоидного алгоритма для решения разнообразных задач комбинаторной оптимизации описано в работе Грбтшеля (ОгогзсЬе(), Ловаса ([,оиазх) и Шрайвера (ЯсЬп]нег) [153]. Однако на сегодняшний день эллипсоидный алгоритм с точки зрения практического применения не может конкурировать с симплекс-алгоритмом.
В работе Кармаркара (Каппагйаг) [197] содержится описание предложенного им алгоритма внутренней точки. Многие его последователи разработали свои алгоритмы внутренней точки. Хороший обзор этих алгоритмов можно найти в статье Гольдфарба (Оо!дГагЬ) н Тодда (ТвхЫ) [140] и в книге Ие ( г'е) [359]. Анализ симплекс-алгоритма относится к области активных исследований. Кли (К!ее) и Минти (М!п1у) построили пример, в котором симплекс-алгоритм выполняет 2" — 1 итераций. На практике симплекс-алгоритм работает очень эффективно, и многие исследователи пытались найти теоретическое обоснование этому эмпирическому наблюдению. Исследования, начатые Боргвардтом (Вогятгаггй) и продолженные многими другими, показывают, что при определенных вероятностных предположениях об исходных данных симплекс-алгоритм сходится за ожидаемое полиномиальное время. Последних результатов в этой области добились Спилмен (Яр!еЬпап) и Тенг (Тепй) [320], которые ввели понятие "сглаженный анализ алгоритмов" и применили его к симплекс-алгоритму.
Известно, что симплекс-алгоритм работает более эффективно в нежггорых частных случаях. К примеру, заслуживает внимания сетевой симплекс-алгоритм— разновидность симплекс-алгоритма, приспособленная для решения задач сетевых потоков. Для некоторых сетевых задач, включая задачи поиска кратчайшего пути, максимального потока и потока минимальной стоимости, варианты сетевого симплекс-алгоритма достигают результата за полиномиальное время. Обратитесь, например, к статье Орлина (Ог!)п) [266] и ссылкам в ней. Глава 30. Полиномы и быстрое преобразование Фурье Для непосредственного сложения двух полиномов степени п требуется время О(п), однако для их непосредственного умноженйя требуется время су(пз).
В данной главе показано, как с помощью быстрого преобразования Фурье (БПФ) (Разг Роцпег Тгапяэопп — РРТ) можно сократить время умножения полиномов до 6(п1бп). Наиболее часто преобразования Фурье (а следовательно, и БПФ) используются в обработке сигналов. Сигнал задается во временнбй области (бше боша(п) как функция, отображающая время в амплитуду. Анализ Фурье позволяет выразить сигнал как взвешенную сумму сдвинутых по фазе синусоид различных частот. Веса и фазы связаны с частотными характеристиками сигнала в частотной области (бег1целсу бошаш).
Множество современных приложений БПФ включает технологии сжатия цифровой видео- и аудиоинформации, в том числе МРЗ-файлы. Обработка сигналов — обширная область исследований, которой посвящено несколько отличных книг (в конце данной главы приводятся ссылки иа некоторые из них). Пол иномы Полинином (ро!упоппа1) относительно переменной х над алгебраическим полем Е называется представление функции А(х) в виде формальной суммы А(х) =~ а хэ.
Значения аы аэ,..., а„г называются коэффициентами данного полинома. Коэффициенты выбираются из некоторого поля Р'; как правило, это множество комплексных чисел С. Говорят, что полинам А(х) имеет стенень к, если его старшим ненулевым коэффициентом является аь, это записывается как г)еягее(А) = к. Любое целое число, строго большее степени полинома, называется границей степени (беятее-Ьоопб) данного полинома. Следовательно, степенью полинома с границей степени п может быть любое целое число от О до а — 1 включительно. Для полиномов можно определить множество разнообразных операций. Например, сложение нолиномов (ро1упоппа1 аоо111оп): если А(х) и В(х) — полиномы с границей степени и, то их суммой является полинам С(х), граница степени 941 Глава ЗЦ Повиномы и быстрое ореобралоеаиие Фурье которого также равна и, такой, что С(х) = А(х) + В(х) для всех х из соответ- ствующего поля. Таким образом, если А(х) = у а.хб о — 1 В(х) = ЕЬбхб, то С(х) = ~~~ с хв, бхз — 2х з — 30хз 24х4 + 28хз — 12хб — 14хб + 20х4 — 18хз + 7хг — 10х + 9 + 4х — 5 — 35хг + 50х — 45 — 40хг + Збх — 12хб — 14хз + 44хе — 20хз — 75хг + 86х — 45 По-другому произведение С(х) можно записать как С(х) = ~~~ с хб, (30.
1) с =~~ аьЬ1 ь (30.2) Заметим, что с1ебгее(С) = бебгее(А) + бебгее(В), откуда вытекает, что если А— полипом степени с границей степени п„а  — полипом с границей степени пь, то С вЂ” папином с границей степени па + пь — 1. Тем не менее, поскольку полипом с границей степени Й является также полиномом с границей степени Й + 1, где с = а + 5 для 9 = 0,1,...,п — 1.
Например, если мы имеем полиномы А(х) = бх + 7х — 10х+ 9 и В(х) = — 2хз+ 4х — 5, то С(х) = 4хз+ 7хг — бх+4. 3 г з Умноовсеине полинамае (ро!упопна! пш1йр!юабоп) определяется следующим образом: если А(х) и В(х) — полиномы с границей степени и, то их произведением (ргодпс1) С(х) является полипом с границей степени 2п — 1, такой, что С(х) = А(х)В(х) для всех х из соответствующего поля. Вероятно, вам уже приходилось перемножать полиномы, умножая каждый член полинома А(х) на каждый член полинома В(х) и выполняя объединение членов с одинаковыми степенями.
Например, умножение полиномов А(х) = бхз + 7хг — 10х + 9 и В(х) = — 2хз + 4х — 5 можно выполнить следующим образом. 942 Часть ед Избранные тсны обычно мы будем говорить, что произведение полиномов С является полиномом с границей степени па + пь. Краткое содержание главы В разделе 30.1 описаны два способа представления полиномов: представление, основанное на коэффициентах, и представление, основанное на значениях в точках.
Для непосредственного умножения полиномов (уравнения (30.1) и (30.2)) требуется время сз(нз), если полнномы представлены с помощью нэзффицнентов, и только В(тз), когда они представлены в форме, основанной на значениях в точках. Однако с помощью преобразования представлений можно умножить заданные с помощью коэффициентов полиномы за время зэ(н 1кн). Чтобы понять, как зто происходит, необходимо сначала изучить свойства комплексных корней из единицы, что и предлагается сделать в разделе 30.2.
Затем также описанные в разделе 30.2 прямое и обратное БПФ используются для выполнения указанных преобразований представлений. В разделе 30.3 показано, как быстро реализовать БПФ в последовательных и параллельных моделях. В данной главе широко используются комплексные числа, поэтому символ 1 будет использоваться в ней исключительно для обозначения з( — 1. 30.1. Представление цолиномов Представления полиномов в форме коэффициентов и в форме значений в точках в определенном смысле эквивалентны: папиному, заданному в форме точек- значений, соответствует единственный полинам в форме коэффициентов. В данном разделе мы познакомимся с обоими представлениями и покажем, как их можно скомбинировать, чтобы выполнить умножение двух полиномов с границей степенн зь за время сз(зз 1я н).
Представление, основанное на коэффициентах Основанным ня коэффициентах нредстаолениен (соейзс)епз гергезепгайоп) полинома А(х) = 2 ":,', а х' с границей степени п является вектор коэффициентов а = (ас, аы.,,, а„1). В матричных уравнениях данной главы мы будем считать векторы векторами-столбцами. Основанное на коэффициентах представление удобно при выполнении определенных операций над полиномами.
Например, операция вычисления (ена1па1шй) полинома А(х) в некой заданной точке хо заключается в вычислении значения А(хс). Если использовать схему Горнора (Ногпег'и гп)е), вычисление требует времени еэ(зз): А(хс) = ао + хо(а1+ хо(аз + . + хо(а„з + хо(а„з)) )) .
943 Глава 30. Полииаиы и быстрое ареобразоваиие Фурье Аналогично сложение двух полиномов, представленных векторами коэффициентов а = (ас, ап ., а„1) н Ь = (Ьс, Ьп..., 6„3), занимает время еэ(и): мы просто создаем вектор коэффициентов с = (со, сп ..,, с„,), где су = ау + Ьу для 3' = О, 1,..., п — 1. Рассмотрим теперь умножение двух полиномов, А(х) и В(х), с границей степени и, представленных в форме коэффициентов, Если использовать метод, описанный уравнениями (30.1) и (30.2), умножение данных полиномов займет время еэ(пз), поскольку каждый коэффициент из вектора а необходимо умножить на каждый коэффициент из вектора 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
