КЛАССИФИКАЦИЯ ЗАДАЧ ПО СЛОЖНОСТИ

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

Следующим по сравнению с применением явной формулы шагом при обсуждении понятия сложности является использование рекурсивной формы решения задачи. В качестве примера можно привести ряд Фибоначчи, широко используемый в теории циклов — одной из основополагающих теорий экономического развития. В этом ряду каждый последующий член по определению состоит из суммы двух предыдущих: О I 1 2 3 5 8 13 21 ..., т.е.

F(n)=F{n~\)+F(n-2).

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

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

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

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

Обратим внимание на один из параметров сложности, очевидно влияющий на быстроту получения результата,— общее число необходимых элементарных операций. Тогда сложность процедуры, выполняемой на любой ЭВМ, можно определить как верхнюю границу числа таких операций. Эта граница зависит от размерности входных данных, которая является существенной характеристикой предметной области. Если размерность данных обозначить п, то можно сказать, что сложность процедуры выражается некоторой функцией f(n).

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

Принято относить задачи к классу полиномиальных, если существует алгоритм, сложность которого составляет полином заданной степени, которая не зависит от размерности п. Разнообразие таких задач относительно невелико. К классу экспоненциальных относятся задачи, которые имеют сложность не менее Cⁿ (С = const). Заметим, что различие между двумя классами задач быстро проявляется с увеличением размерности п.

Большое количество задач типа распределения персонала или подготовки планов проведения последовательности операций,

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

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