1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 26

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

ОБщее исследование 1Р5 результата оптимального упорядочения: один — для дерева формулы вычисления лм, другой — более сложный (римскими цифрами указаны значения функции ширины, арабскими — оптимальный порядок в обратной нумерации)*). Оценки числа шагов. Для основной нити нашего нале»кения этот пример поучителен формой алгоритма, решающего поставленную комбинаторную задачу. Наиболее важным свойством этого алгоритма является его направленность.

С одной стороны, мы по существу испольауем информацию, заложенную в дереве формулы, являющуюся «материалом» нашей задачи. Нам надо «пройти» каждую вершину и «обработать» каждое бинарное отношение, образующее ту или иную дугу дерева. Мы'замечаем разницу между висячими и прочими вершинами. С другой стороны, в работе алгоритма можно усмотреть некоторое единое направление его развития: сначала от висячих верп3ин к корню при построении функции ширины, а затем — наоборот, при упорядочивании. Если мы н откладываем некоторые вершины «про запас» (запоминание вершин с ббльшим значением функции ширины), то и это мы делаем систематически: мы пе рыскаем произвольно среди них, а берем всегда вершину, запомненную последней.

Для математического рассмотрения нам, однако, недостаточно такого интуитивного представления об эффективности алгоритма, которое мы выра>каем только словами: переборный алгоритм, направленный алгоритм и т. и. Роль критериев эффективности алгоритмов играют уже упоминавшиеся оценки сложности алгоритма. Мы уже знаем, что каждая программа характериауется числом команд и объемом расходуемой памяти.

Заметим, что число команд можно понимать двояко: как число команд в программе, так и число выполнившихся команд при выполнении программы. В ряде разделов математики и программирования первая характеристика тоже важна, однако эффективность программы лучше характеризуется вторым показателем. Аналогичные характеристики рассматривают и для алгоритмов. Если зафиксировать способ описания алгоритма (алгоритмический язык), точно описать, как данные размещаются в памяти, то тогда, выполняя алгоритм для некоторых исходных данных, можно точно посчитать или оценить как число элементарных шагов выполнения алгоритма, так и число единиц информации, которое надо одновременно размещать в памяти. Если исходные данные имеют некоторый характеризукнций их параметр (норядок матрицы, число вершин,нли дуг в графе, количество независимых переменных и т. п.), то тогда н подсчнтываемое нлн *) Для читателей, которые заинтересовались алгоритмом оптимального упорядочения самиы по себе, заметим, что нопыткн его обобщения на лнйейные программы с более сложными, чем деревья, информационными связями наталкиваются на большие трудности.

гл. 3. Алгогитмизлцип оцениваемое число шагов н объем памяти становятся функциями этого параметра. Эти функции и называют показателями иля оценками сложности алгоритма (или программы). Оценки числа шагов называют «ременными оценками, оценки числа требуемых ячеек памяти так и называются оценками памяти, яли емкостны.ни оценками. Обычно в качестве параметра, характеризующего исходные данные алгоритма, берут некоторое натуральное число п, как-то <вязанное о их объемом.

Тогда эффективность алгоритмов по времени их работы сопоставляют со скоростью роста временной оцении как функции г'(п). В этой градации скоростей роста различают лгрежде всего следующие функции: г"(п) = и — линейная оценка, Р(п) = и 1ои, и — логарифмическая оценка, г"(п) = и' — квадратичная оценка, Г(п) = а,п" +а,п" '+... '- ໠— полиномиальная оценка, г"(и) = а" — экспоненциальная оцеяка, г'(п) = и! — факториальная оценка, 1(а) = и" — гиперэкспоненциальная оценка.

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

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

Типичный пример— суммирование чисел. Здесь то, что мы назвали направленностью алгоритма, выступает в своем чистом виде: выполнив несколько операций над входной переменной, мы к ней больше не возвраецаемся. Квадратичные оценки появляются тогда, когда вклад Э Э.Э. РАСКРАСКА ВЕРШЕН ГРАФА. ОВЩЕЕ ЕССЛЕДОВАНЕЕ 1гг каждой входной переменной в результат существенно зависиР от ее «взаимодействия» со всеми, или почти со всеми, другими переменными. Читателю может покаааться странным, но ему будеР не очень просто сразу придумать задачу, которая, по существу, требовала бы для своего решения алгоритма с квадратичной оценкой.

Первое, до чего додумался автор, размышляя над этими строками,— это построение многочлена, принимающего заданные и. значений (такие многочлееы называются интерполяционнымн, и кто-нибудь из читателей анает про многочлены Лагранжа„ удовлетворяющие такому требованию). Там, для заданных значений многочлена х„х„..., х„, нужно вычислить все возможныо их разности хэ — хг (э, у = 1, ..., п), что и даст квадратичную оценку. Вернемся теперь к нашей задаче. Для того чтобы связать ео с только что проведенными рассуждениями, нам надо договориться о том, что характеризует «независимые переменные» и их число в исходных данных и «единицу действия» в алгоритмах раскраски.

Мы уже оценив»ля комбинаторпый объем различных раскрасок как функцию числа и вершин графа. Мы можем полностью описать граф, если для каждой вершины указать множество ребер„ которым она принадлежит, ели, что то же самое, множество смежных ей вершин. Такое описание «ближайшего окружения» вершины или, как мы будем говорить, окрестности 1-го порядка мы к будем считать «единицей информации» в задании графа. Конечно, строго говоря, ее нелвзя по-настошцему считать единицей информации, так как ее объем весьма различен.

Изолированная вершина имеет пустую окрестность 1-го порядка, а «звезда», т. е. вершина графа, смежная со всеми остальными, содержит в этой окрестности вершины всего графа. Общий объем этой информации тоже весьма рааличен при фиксированном и: от нуля ребер в графе, состоящем из изолированных вершин, 'до п — 1 ребра в самом. простом связном графе (незамкнутая цепочка из п Ъершин) и, наконец, до п(п — 1) ребер в п-полпог«графе (в котором все и вершин попарно смежны). Тем не менее для прикидочных рассуждений об эффективности алгоритмов раскраски, когда мы ЕФ делаем никаких дополнительных предположений о способах представления графов, такая трактовка единицы информадии для нас пока достаточна.

Там же, где еам удастся вставить в рассуждение число р ребер графа, мы будем также иепольаовать его и качестве параметра задачи. При таком подходе естественно рассматривать в качестве «шага» алгоритма раскраски совокупность действий, относящихся к вершине и ее окрестности 1-го порядка. Если же нам требуется большая детальность, то тогда одним шагом может стать «отработка» одного ребра графа, например, проверка, какой краской. окрашена смежная вершина.

гл. 3. Алгоэитмизапия $3.4. Раскраска вершин графа. Поиск алгоритма Итак, мы приступаем к поискам практичного алгоритма раскраски вершин графа, сознавая, что минимальные раскраски в общем случае требуют экспоненциального числа шагов. Это означает, что нам придется подойти к построению алгоритма с другого конца: отказавшись от претензии на нахождение заведомо минимальных раскрасок, мы аадаемся некоторой общей организацией алгоритма, обеспечивающей приемлемую временную оценку, но з рамках атой органиаации постараемся действовать каким-то разумным способом, конкретнзирующим общий принцип здравого смысла: «поступай наилучшим образом в пределах возможногое.

Рамки возможного и то, что считается наилучшим, это и есть содержание того конкретного анализа нашей задачи, который мы пытаемся предпринять. Эвристические методы. Человеку в повседневной жизни постоянно приходится сталкиваться с ситуациями, которые в их математическом, выражении выглядят как комбинаторные задачи, требующие непомерных затрат на поиск абсолютно наилучшего решения и поэтому заставляющие вырабатывать какую-то ограниченную тактику поиска приемлемого решения. Вот примеры таких правил: — не отменяй принятых решений; — упаковывая вещи в чемодан, начинай с самых громоздких гредметов; — в поисках, максимума функции двигайся в направлении градиента; — лучше синица в руках,- чем журавль з небе; — не зная, как поступитть поступай как-нибудь.

Характеристики

Список файлов книги