Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.), страница 9

33.6). В качестве набора вершин может выступать любое из 2" подмножеств множества точек. Однако недостаточно знать, какие точки являются вершинами выпуклой оболочки, нужно еще указать порядок их обхода. Таким образом, чтобы найти выпуклую оболочку, приходится перебрать множество вариантов. В главе 33 описаны два хороших метода определения выпуклой оболочки. Приведенные выше случаи применения алгоритмов отнюдь не являются исчерпывающими, однако на их примере выявляются две общие характеристики, присущие многим интересным алгоритмам.

1. Есть множество вариантов-кандидатов, большинство нз которых решениями не являются. Поиск среди них нужной комбинации является довольно трудоемким. 2. Задачи имеют практическое применение. Простейший пример среди перечисленных задач — определение кратчайшего пути, соединяющего два перекрестка. Любая компания, занимающаяся авто- или железнодорожными перевозками, финансово заинтересована в том, чтобы определить кратчайший маршрут. Это способствовало бы снижению затрат труда и расходов горючего. Маршрутизатору 1п1еше1 также нужно иметь возможность находить кратчайшие пути в сети, чтобы как можно быстрее доставлять сообщения.

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

Методические указания Данную книгу можно рассматривать как "сборник рецептов" для алгоритмов. Правда, однажды вам встретится задача, для которой вы не сможете найти опубликованный алгоритм (например, таковы многие из приведенных в книге упражнений и задач). Данная книга научит вас методам разработки алгоритмов и их анализа. Это позволит вам разрабатывать корректные алгоритмы и оценивать их эффективность самостоятельно. Глава 1. Роль алгоритмов в вычислениях Сложные задачи Большая часть этой книги посвящена эффективным алгоритмам.

Обычной мерой эффективности для нас является сюрость и время, в течение которого алгоритм выдает результат. Однако существуют задачи, для которых неизвестны эффективные методы их решения. В главе 34 рассматривается интересный вопрос, имеющий отношение к подобным задачам, известным как ХР-полные. Почему же ХР-полные задачи представляют интерес? Во-первых, несмотря на то, что до сих пор не найден эффективный алгоритм их решения, также не доказано, что такого алгоритма не существует. Другими словами, неизвестно, существует ли эффективный алгоритм для ХР-полных задач.

Во-вторых, набор МР- полных задач обладает замечательным свойством. Оно заключается в том, что если эффективный алгоритм существует хотя бы для одной из этих задач, то его можно сформулировать и для всех остальных. Эта взаимосвязь между ХР-полными задачами и отсутствие методов их эффективного решения вызывает еще ббльший интерес к ним. В третьих, некоторые ХР-полные задачи похожи (но не идентичны) на задачи, для которых известны эффективные алгоритмы. Небольшое изменение формулировки задачи может значительно ухудшить эффективность самого лучшего из всех известных алгоритмов. Полезно располагать знаниями о ХР-полных задачах, посюльку в реальных приложениях некоторые из них возникают неожиданно часто.

Если перед вами встанет задача найти эффективный алгоритм для ИР-полной задачи, скорее всего, вы потратите много времени на безрезультатные поиски. Если же вы покажете, что данная задача принадлежит к разряду ХР-полных, то можно будет вместо самого лучшего из всех возможных решений попробовать найти достаточно эффективное.

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

Эффективный алгоритм решения для нее неизвестен, однако при неюторых предположениях можно указать такие алгоритмы, в результате выполнения юторых полученное расстояние будет ненамного превышать минимально возможное. Подобные "приближенные алгоритмы" рассматриваются в главе 35. 52 Часть 1. Основы Упражнения 1.1-1. Приведите реальные примеры задач, в которых возникает одна из таких вычислительных задач: сортировка, определение оптимального порядка перемножения матриц, поиск выпуклой оболочки. 1.1-2. Какими еще параметрами, кроме скорости, можно характеризовать алгоритм на практике? 1.1-3. Выберите одну из встречавшихся вам ранее структур данных и опишите ее преимущества и ограничения.

1.1-4. Что общего между задачей об определении кратчайшего пути и задачей о коммивояжере? Чем они различаются? 1.1-5. Сформулируйте задачу, в которой необходимо только наилучшее решение. Сформулируйте также задачу, в которой может быть приемлемым решение, достаточно близкое к наилучшему. 1.2 Алгоритмы как технология Предположим, быстродействие компьютера и обьем его памяти можно увеличивать до бесконечности. Была бы в таком случае необходимость в изучении алгоритмов? Была бы, но только для того, чтобы продемонстрировать, что метод решения имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы любой корректный метод решения задачи.

Возможно, вы бы предпочли, чтобы реализация решения была выдержана в хороших традициях программирования (т.е. качественно разработана и аккуратно занесена в документацию), но чаще всего выбирался бы метод, который легче всего реализовать. Конечно же, сегодня есть весьма производительные компьютеры, но их быстродействие не может быть бесконечно большим.

Память тоже дешевеет, но она не может быть бесплатной. Таким образом, время вычисления — это такой же ограниченный ресурс, как и объем необходимой памяти. Этими ресурсами следует распоряжаться разумно, чему и способствует применение алгоритмов, эффективных в плане расходов времени и памяти. Эффективность Алгоритмы, разработанные для решения одной и то же задачи, часто очень сильно различаются по эффективности. Эти различия могут быть намного значительнее, чем те, что вызваны применением неодинакового аппаратного и программного обеспечения. Глава 1.

Роль алгоритмов в вычислениях 53 В качестве примера можно привести два алгоритма сортировки, которые рассматриваются в главе 2. Для выполнения первого из них, известного как сортировка вставкой, требуется время, которое оценивается как с1пз, где п — количество сортируемых элементов, а с| — константа, не зависящая от п. Таким образом, время работы этого алгоритма приблизительно пропорционально пз. Для выполнения второго алгоритма, сортировки слиянием, требуется время, приблизительно равное сап !к и, где !кп — краткая запись 1окз и, а сз — некоторая другая константа, не зависящая от п.

Обычно константа метода вставок меньше константы метода слияния, т.е. с| ( сз. Мы убедимся, что постоянные множители намного меньше влияют на время работы алгоритма, чем множители, зависящие от и. Для двух приведенных методов последние относятся как )кп к и. Для небольшого количества сортируемых элементов сортировка включением обычно работает быстрее, однако когда и становится достаточно большим, все заметнее проявляется преимущество сортировки слиянием, возникающее благодаря тому, что для больших и незначительная величина 1к и по сравнению с п полностью компенсирует разницу величин постоянных множителей. Не имеет значения, во сколько раз константа с1 меньше, чем сз. С ростом количества сортируемых элементов обязательно будет достигнут переломный момент, когда сортировка слиянием окажется более производительной.

В качестве примера рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нем работает алгоритм сортировки вставкой, а компьютер Б более медленный, и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоящего из миллиона чисел. Предположим, что компьютер А выполняет миллиард инструкций в секунду, а компьютер Б — лишь десять миллионов. Таким образом, компьютер А работает в ! 00 раз быстрее, чем компьютер Б. Чтобы различие стало еще ббльшим, предположим, что код для метода вставок (т.е. для компьютера А) написан самым лучшим в мире программистом с использованием команд процессора, и для сортировки и чисел надо выполнить 2пз команд (т.е.

с1 = 2). Сортировка же методом слияния (на компьютере Б) реализована программистом-середнячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения 50п 1кп команд (т.е. сз = = 50). Для сортировки миллиона чисел компьютеру А понадобится 2 (10а/ команд = 2000 с, 10экоманд / с а компьютеру Б— 50 10в 1б 10акоманд = 100 с.

10ткоманд / с Как видите, использование кода, время работы которого возрастает медленнее, даже при плохом компиляторе на более медленном компьютере требует на по- Часть Ь Основы 54 рядок меньше процессорного времени! Если же нужно выполнить сортировку 10 миллионов чисел, то преимущество метода слияния становится еще более очевидным: если для сортировки вставкой потребуется приблизительно 2.3 дня, то для сортировки слиянием — меньше 20 минут.