Конструирование алгоритмов

Привет, сегодня поговорим про конструирование алгоритмов, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое конструирование алгоритмов , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

" Узнавать о новых алгоритмах и учиться их применять - важная часть программистского образования. "
Говард Джонстон

" Надо сочинить закон или таблицу, по которой числа росли бы необъяснимыми непериодическими интервалами. "
Даниил Хармс

Мы столько внимания уделили собственно возможности оценивать временнУю эффективность алгоритма, но пока даже не пытались выяснить, а насколько это нужно практически.

В самом деле, вычислительный процесс, согласно сконструированному алгоритму, должен выполняться на современном компьютере, который, кажется нам, работает "довольно быстро". Не будет ли экономия ресурсов, которой алгоритмист так старательно добивается, столь малой, что представит лишь чисто теоретический интерес? Или, как говорят в подобных случаях, стоит ли игра свеч?

Попробуем выяснить это, оперируя некоторыми цифрами. Предположим, для определенности, что в нашем распоряжении процессор, который способен осуществлять десяток миллионов - 10⁷ - микроинструкций за секунду (mips), и порадуемся за читателя, у которого на столе уже стоит компьютер с таким быстродействием. Еще условимся, что спроектированный нами алгоритм требует, в среднем, по десять mips на каждый свой шаг. Это не много, если шаг алгоритма включает, скажем, вычисление адреса памяти, где располагается элемент массива, выборку его и какую-то дальнейшую обработку. Очевидно, при таких условиях всего-то одной секунды машинного времени хватит на целый миллион - 10⁶ - алгоритмических шагов вычислительного процесса!

"Что ж это за алгоритмы такие, где подобного быстродействия может быть недостаточно?" - спросит читатель. "Да много таких алгоритмов!" - ответим мы скептику. И упомянем, для начала, приводившийся ранее пример отбора треугольников, исходное "сырье" для которых извлекается из набора отрезков. В самом деле, эффективность напрашивающегося, "лобового", решения оценивается как O(n³), и, стало быть, набор из тысячи отрезков (10³) будет обрабатываться более четверти часа. Так долго ожидать результат, сидя у экрана компьютера, - занятие мало увлекательное.

Не станем утверждать, что предлагаемый вариант, требующий O(n³) шагов, - единственно возможный. Напротив, читателю стоит поразмышлять над тем, как распорядиться ресурсами более экономно, и, тем самым, ступить на путь конструирования эффективных алгоритмов. Но ведь это и требовалось доказать: уже имеющийся в нашем распоряжении алгоритм провоцирует нас на поиски более качественного механизма. Тем более, стоит поискать лучшее решение, если временнАя сложность готового алгоритма оценивается как O(n⁴) или O(n⁵). И не говорите, что таких задач не бывает, - ошибетесь.

Однако вас, возможно, удивит, что вычислительные процессы с трудоемкостью O(n³), O(n⁴) и даже O(n⁵) отнюдь не обязательно являются продуктами плохой алгоритмизации. Напротив, такие задачи не единичны, хотя здесь пока рано переходить к их постановке. Скажем лишь, что нередко более эффективных алгоритмов либо не сконструировать в принципе, либо просто до сих пор не придумали. Отметим их общее свойство: все они относятся к классу так называемых алгоритмов с полиномиальной временнОй сложностью - O(n^k), где k - константа, и, естественно, не меняется с ростом количества элементов n.

Как же решаются, если в том возникает необходимость, задачи класса O(n⁴) или O(n⁵) для "больших" n? Ну, во-первых, не стоит забывать, что мы рассматриваем процессы, в основе которых лежит последовательное выполнение инструкций, а существует ведь и такая альтернатива, как параллельные вычисления. Кроме того, злополучные "четверть часа ожидания" критичны для пользователя, работающего непосредственно за компьютером, но совершенно безразличны ему, если вычислительный процесс идет в фоновом режиме работы его "персоналки" или, тем более, в пакетном режиме большой вычислительной машины.

Гораздо хуже обстоит дело с алгоритмами, трудоемкость которых составляет O(2ⁿ), O(n!), O(nⁿ) и более. В этом перечне каждая очередная функция "перекрывает", при достаточно больших n, предыдущие функции того же ряда. Или, как говорят,мажорирует их. Притом, любая из них мажорирует трудоемкость полиномиальную. Такие алгоритмы принято характеризовать как имеющие экспоненциальную сложность.

Обратимся к примеру.

Как видим, применять алгоритмы с вычислительной трудоемкостью O(n!) надо очень осторожно, если хотим дождаться конечного результата. Что же делать?

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

Предположим, что в классе из 15 человек, формируя очередное размещение их по партам, мы зафиксировали выбор 5 определенных учеников на места с 1-го по 5-е. Стало быть, на остающиеся 10 мест претендуют остальные 10 учеников, что соответствует 10! возможностям выбора. Если используемый в задаче критерий отбора позволяет зафиксировать нерентабельность уже исходного отбора "первой пятерки", то и все семейство из 10! соответствующих ему рассадок нет смысла перебирать.

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

Кстати говоря, если из условий задачи о подсчете количества треугольников изъять указание о попарном неравенстве отрезков во входном наборе, то указанный метод вполне применим. Так, первичный выбор двух одинаковых отрезков делает бессмысленным перебор всех остальных претендентов на третью позицию.

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

Вот пример ситуации, когда знакомство с методом частных целей автору пригодилось практически. Так, за несколько дней до написания этого фрагмента текста у него возникла проблема срочного "переезда" - из одной комнаты квартиры в другую - в связи с ремонтом. Поскольку останавливать "производственный процесс" не хотелось, то пришлось переносить рабочее место, то есть письменный стол, компьютер и прочее. Вот и подзадачи: разъединить составные части компьютера, перенести их в места новой дислокации, а там собрать. Каждая из подзадач решается автономно, правда, последовательность нарушать нельзя. Если вы этот текст читаете, значит, метод себя оправдал. Конечно, в описываемой ситуации возникли и другие, столь же неприятные подзадачи, но перечислять их не хочется.

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

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

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

Действительно, никому еще не удалось точно вычислить значение числа π, - по причине невозможности. Однако же сделать это с обусловленной заранее точностью удается, для чего, кстати, существует довольно много различных алгоритмов, и, - главное, - во всех случаях вычислительный процесс конечен. Один из них описан в первом из предлагаемых читателю упражнений.

Алгоритмы, описанные в приведенных упражнениях, относятся к классу приближенных. Их общее свойство - это возможность получения такого, пусть и неточного, решения, которое "сколь угодно мало" отличалось бы от верного. Для практических нужд, как уже сказано, этого может быть достаточно.

Уделив внимание возможностям применения точных и приближенных алгоритмов, мы обязаны, хотя бы конспективно, коснуться алгоритмов эвристических.

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

В поисках иллюстрации вновь обратимся к "незаконным" аналогиям за рамками конечной математики.

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

Или: как высоко может прыгнуть вверх спортсмен, не прибегая к специальным приспособлениям? В качестве приближенного значения кажется разумным принять текущее мировое достижение. Его превышение очередным атлетом дает новую итерацию, уменьшая абсолютную невязку с неким "точным", но практически недостижимым результатом. В этом смысле, похоже, мы имеем дело с приближенным алгоритмом. С другой стороны, изменение спортивной техники выполнения прыжка может существенно сдвинуть планку высших достижений, как это случилось при переходе от стиля "перекидной" к "фосбюри-флопу". Не примени американец Фосбюри свой "флоп", и мы вполне могли оставаться в неведении, принимая приближающийся с годами локальный экстремум прежнего стиля за экстремум абсолютный.

К сожалению, в одной статье не просто дать все знания про конструирование алгоритмов. Но я - старался. Если ты проявишь интерес к раскрытию подробностей,я обязательно напишу продолжение! Надеюсь, что теперь ты понял что такое конструирование алгоритмов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов