ПРИМЕРЫ ФОРМАЛИЗАЦИИ И РЕШЕНИЯ ЗАДАЧ ДЛЯ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

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

П р и м е р 1 . Формула простых процентов.

В качестве примера можно привести значение наращенной суммы S(n) на конец срока в п лет для ссуды Р. Если / — ставка наращения процентов (десятичная дробь), то согласно формуле наращения по простым процентам

Приведенная формула обладает постоянной сложностью: одно сложение и два умножения. Она не зависит от п, и мы обозначаем ее порядок как 0(1).

Для получения результата знание явной формулы не является обязательным, если известен способ получения результата. Мы будем записывать его в условном виде — в виде процедуры, содержание которой легко выводится из контекста обсуждаемой задачи. В записи будет использоваться символ := , который означает «присвоить в качестве значения».

Пример 2. Формула сложных процентов.

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

Однако на этот раз мы воспользуемся следующей процедурой вычислений:

Чтобы получить ответ, система производит вычисления в обратном порядке, т.е. от Jf(I) до $(4), и затем очищает память. Так как число необходимых умножений имеет порядок 0(п), то и сложность процедуры имеет тот же порядок. Здесь мы имеем про- стейшую рекурсивную схему процесса вычислений, которая постепенно, шаг за шагом, приводит к результату.

П р и м е р 3 . Вычисление чисел Фибоначчи F(n).

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

формулы. Для этого достаточно непосредственно воспользоваться ранее приведенным определением чисел Фибоначчи:

Процедура Фибоначчи 1: рекуррентное вычисление п-то числа Фибоначчи F(n)

Если η > 2 то F(n) := F(n - I) + F(n - 2)

Иначе F(η) := I Конец «Если»

Конец Процедуры

Попытка осуществить схему запоминания информации, как в предыдущем примере, покажет, что ситуация становится более сложной. Оказывается, что число операций сложения для поиска F(n) имеет порядок самого этого числа, а значит, и сложность процедуры будет иметь порядок 0(F(n)). Такие требования к объему памяти мало кого смогут удовлетворить, так как, например, F(36) = 14930352.

Для преодоления этой трудности достаточно запоминать всякий раз не все числа от F(n) до F(I), а только два предыдущих: Gl = F(n — I) и G2 = F(n — 2). Тогда, привлекая вспомогательную переменную G3, получаем итерационный алгоритм:

Процедура Фибоначчи 2\ итерационное вычисление п-то числа Фибоначчи F(n)

k: = 2; Gls= I; G2: = 1;

Повторять до тех пор пока к ф η

к:= к + I; G3: = Gl; Gls= Gl + G2; G2s= G3;

Конец цикла по к

Результат Gl [ F(n) = Gl ]

Конец Процедуры

И результатом упрощения алгоритма становится уменьшение порядка сложности с 0(F(n)) до 0(п).

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

Пример 4. Поиск кратчайшего пути.

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

не о длине ребер как расстояниях между вершинами графа, а о стоимости ребер.

Мы не будем приводить весь алгоритм решения сформулированной задачи.

Можно показать, что для графа с п вершинами предлагаемый алгоритм итеративного распространения минимальных путей имеет сложность 0(п²).

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