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

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

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

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

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

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

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

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

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

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

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

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