Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 30
Текст из файла (страница 30)
В тех редких случаях, когда кодирование может вызвать определенные трудности, будем явно указывать на эту проблему и давать способ ее разрешения. Поскольку мы договорились, что вход алгоритма представляется в виде последовательности (или цепочки) символов, определим размер входа как длину этой последовательности, т. е. число символов в ней. Пример 8.3. Во многих задачах (например, в задаче определения, является ли целое число простым) входная информация является просто целым числом. Существует много экономных способов представления целых чисел; наиболее общие — системы счисления с некоторым фиксированным основанием, такие, как десятичная или двоичная.
В этих системах число символов, необходимых для представления целого числа п, равно Г 1одвп'1 '), где В)2 — основание з) Через 1 х 1 обозначается наименьшее целое д, такое, что Ч~)х, и через 1 х 1 — наибольшее целое ч, такое, что д «х. Гл. 8. Алгоритма и олоооноппь системы. Мы видим, что независимо от используемого основания размер представления и есть 6()од и); напомним, что !орал=в 1ои и !ок В и !он 8 при фиксированном В является константой. П Пример 8А. Что такое размер задачи линейного программирования? Как и раньше, мы считаем, что элементы матрицы А и векто- и, (оы оп ог) ~о~ ол! ~от ог, од, ои 1олг А(о,) = Ашг) = гног1 = г1(о„) = '1( 51 ог о5 (а) (б) Рис. 8.1.
ров Ь и с — целые числа. Поэтому размером задачи линейного программирования должно быть число символов, необходимых для записи А, Ь и с. Поскольку это можно сделать, выписывая элементы матриц в двоичной (или десятичной) системе, используя подходящие разделители для горизонтальных и вертикальных линий в таблице, то размер задачи ЛП с тхп-матрицей есть 0(та+ ! 1од!Р! !), где Р— произведение всех ненулевых коэффициентов. Пример 8.5. Во многих интересных задачах входом является граф.
Что такое размер графа? Граф можно представить многими способами. Например, любому графу 6=()г, Е) сопоставить его матрицу смежностей Аа=!аи! размера !Цх 71, в которой ам=1, если !ои о;)ЕЕ, и ам=0 в противном случае. Но этот способ может оказаться не самйм экономным способом представления графа, Граф (и', Е) может иметь до ф)=хо(!)'!') ребер, Однако многие графы являются разреженными, т. е. число ребер в них много меньше, чем(',"). Например, граф может иметь 100 вершин и 500 ребер. Представление этого графа матрицей смежностей потребовало бы 10 000 разрядов для записи всех элементов.
Простое выписывание ребер подряд намного экономнее. Одним из полезных способов представления графа являются списки смежностей. При этом для каждой вершины оЕУ выписывается множество А (о)о:-$' вершин, смежных с о (рис. 8.1). Размер этого представления зависит от суммы длин списков. Так как каждое ребро добавляет 2 к этой общей длине (1 в списке для В.З, Размер индивидуазьнвд задачи одного конца ребра плюс ! для другого конца), го в целом требуется записать 2(Е! элементов. Имеется, однако, другой фактор, влияющий на общую длину представления. Даже для графов среднего размера невозможно использовать различные буквы для всех вершин (напомним, что наш алфавит должен иметь фиксированный конечный размер).
Поэтому для различения вершин мы должны использовать индексы. Поскольку у нас (У! вершин, то для этого нам потребуется приблизительно 0((ой (У!) двоичных (или десятичных) разрядов. Следовательно, для представления графа 6=(У, Е) требуется (д(!Е! (ой (У!) символов. Тогда почему на практике мы говорим, что граф (У, Е) можно закодировать, используя память О(!Е!)У Причина состоит в том, что современные ЭВМ обычно одинаково обращаются со всеми целыми числами в своих пределах — обычно от О до 2".
Они отводят одну и ту же память (слово) как для 3, так и для 71О. Поскольку почти наверняка графы более чем с триллионом вершин никогда не появятся в приложениях, то 0((Е!) таких слов достаточно для хранения списков смежностей графа с использованием индексов в этих пределах для идентификации вершин. Следовательно, !Е! является разумной аппроксимацией размера графа, и анализ сложности алгоритмов на графах с использованием (Е! в качестве параметра практически приемлем. Тем не менее иногда мы будем использовать в качестве параметров для характеристики сложности алгоритма обе величины !У! и !Е!. Это связано с тенденцией рассматривать (У! как главную характеристику размера графа, возможно, потому, что в большинстве приложений теории графов У является исходным объектом при построении 6.
Естественно, (У!и (Е(связаны неравенством (Е!~ (!У(((У! — !)12, и можно считагь, что (Е!)(У!'2 (например, если в нашем графе нет изолированных вершин). Однако в этих пределах (Е! может очень сильно меняться, делая граф 6 нарын(енным (когда (Е!=0((У!')) или разреженным (когда !Е! много меньше, чем его максимальное значение). Следовательно, алгоритм с оценкои 0((Е!') может быть предпочтительнее, чем алгоритм с оценкой 0((У!'(Е!), когда граф разреженный, тогда как для насьпценных гра ов оправдан противоположный выбор. некоторых комбинаторных задачах, таких, как ЗК, задача о кратчайшем пути и МОД, вход состоит, по крайней мере частично, из целых чисел.
Алгоритмы для этих задач обычно включают такие операции, как сложение и сравнение целых чисел. Например, в алгоритме Флойда — Уоршелла для задачи о кратчайшем пути большинство шагов состоит из сравнений и сложений пар целых чисел. Поскольку нет явных границ для величины этих целых чисел, может оказаться, что они настолько велики, что их нельзя представить словом конечной длины нашей гипотетической вычислительной машины. В этом случае требуется применить специальные методы для выполнения сложений и сравнений очень больших целых Гл, В.
Алеорнтмы и сложность чисел, и такие методы требуют для каждой операции времени (числа элементарных шагов), растущего приблизительно как логарифм участвующих в операции целых чисел. В этой книге мы упростим дело, рассматривая каждую такую операцию как элементарный шаг единичной стоимости, называемый арифметической операцией. Например, мы будем говорить, что алгоритм Флойда — Уоршелла решает задачу о кратчайшем пути в орграфе 0=(У, А) за 0()У!з) арифлевгпичвских операций, или, для краткости, за прелая 0()У)з).
Под этим в действительности будем понимать, что число элементарных операций не превосходит 0((У)з!ой М), где М вЂ” наибольшее целое число, появляющееся в данной индивидуальной задаче. Мы можем принять это соглашение, не изменяя существа наших результатов, поскольку алгоритмы, которыми мы будем интересоваться, включают операции над целыми числами, не намного большими, чем числа во входе '). Совершенно другая (и более тонкая) ситуация возникает, когда общее число арифметических операций зависит от значений участвующих в задаче целых чисел. В следующем параграфе мы увидим, что таким свойством обладает алгоритм пометок для задачи о максимальном потоке, описанный в гл.
6. В.4 льнвннз впге»рнтмезв Получение хороших верхних оценок времени работы алгоритма — не всегда простая задача; оно может потребовать такой же изобретательности и умения, как построение алгоритма. Пример 8.6. Алгоритм Флойда — Уоршелла длп задачи о кратчайшем пути в орграфе 0=(У, А) имеет временную сложность 0((У!з) арифметических операций, В этом случае анализ особенно прост и время, необходимое для работы алгоритма, незначительно изменяется в зависимости от орграфа и расстояний, подаваемых на вход алгоритма.
Основным здесь является тот факт, что алгоритм, по существу, состоит из трех «вложенных циклов», каждый из которых выполняется примерно )У! раз; самую внутреннюю операцию «треугольника» можно реализовать с использованием всего двух арифметических операций. () Пример 8.7. Какова сложность алгоритма пометок для решения задачи о максимальном потоке (гл. 6) для сети )е'=(з, 6 У, А, Ь)? Заметим, что этот алгоритм состоит нз начального шага, который можно выполнить за время, пропорциональное )У), и множества итерационных шагов. Каждый итерационный шаг включаеч просмотр вершин и приписывание нм пометок.
Чтобы оценить сложх ') В симолекс-методе встречаются только рациональные чисча, в которых как числитель, так и знаменатель ограничены по абсолютной величине размером входа (вспомните доказательство леммы 2.)). 8.4. Ааааа аморитмав ность каждой итерации, заметим, что в процессе просмотра каждая дуга (о, и) сети М может рассматриваться не более двух раз— один раз при просмотре о и один раз при просмотре и. Таким образом, процесс приписывания пометок требует порядка 0((А() арифметических шагов. С другой стороны, возвращение по пометкам можно выполнить за 0(р) шагов, где р — длина (число дуг) обнаруженного увеличивающего пути. Заметим, что в увеличивающем пути вершины не могут повторяться; поэтому р~~Ц.
Следовательно, каждая итерация алгоритма требует 0(71+ 1А ))=0((А 1) времени. Таким образом, в целом алгоритм имеет сложность 0(Я (А(), где Я вЂ” число итераций, Поскольку пропускные способности всех дуг целые, то поток остается целочисленным на всех шагах, что можно показать несложной индукцией по числу итераций Следовательно, приращения также имеют положительные целочисленные значения, и поэтому на каждой итерации величина потока увеличивается по меньшей мере на Е Таким образом, если о — величина максимального потока, то 5 св Однако в этой оценке кое-что заведомо неправильно: мы оценили сложность решения задачи через ее решение! На самом же деле нам нужна априорная оценка сложности, выраженная через вход.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
