конспект (лекции)

Асирян АлександрReasoning: goal trees and problem solving. Конспект.Введение.Можем ли мы посчитать интеграл ∫−5 45(1− 2 )2ⅆ в уме? Скорее всего нет.Но можно ли считать программу, решающую эту задачу, разумной?Лекция посвящена моделированию решения задач в том виде, в котором этоделает человек. Алгоритм решения задачи символьного интегрирования,который будет рассмотрен на лекции, является общей идеей того, как людирешают задачи.Декомпозиция задачи символьного интегрирования.Имеется список табличных интегралов – это знания, то есть задачи, решениекоторых уже известно.

Если свести решение исходной задачи к решениютабличных интегралов, то и исходная задача будет решена. Этот процессназывается декомпозицией задачи. Преобразование задачи может бытьбезопасным и эвристическим. Последние похожи на подход генерации ипроверки решений. Разумно сначала применять безопасные преобразования,пока это возможно. Какие преобразования в данной задаче можно считатьбезопасными?Безопасные преобразования∫ −() ⅆ− ∫ () ⅆ∫ () ⅆ ∫ () ⅆ∫ ∑ () ⅆ∑ ∫ () ⅆ∫()ⅆ()РазделитьмногочленыВынесение константы безопасно, так как уполученной задачи есть решение, если оноесть и у исходной. Если представить этоталгоритм в виде дерева, то задачи отвечаютвершинам, а преобразование – ребру.Выделяется третье правило: оно разбиваетзадачу на несколько подзадач. Причемчтобы решить исходную, необходиморешить все подзадачи.

Такая вершинаназывается И-вершиной и обозначаетсятак:ABИCПрименим все возможные безопасные преобразования:−5 45 44∫5 ⅆ ⇒1 ∫5 ⅆ ⇒2 ∫5 ⅆ222(1 − )2(1 − )2(1 − )2Сначала выносится знак минус, после чего выносится константа. Так какприменить безопасные преобразования больше нельзя, то применяется одноих эвристических преобразований.Эвристические преобразованияsin , cos ,∫ (tan , cot ,) ⅆsec , csc ∫ 1 (sin , cos ) ⅆ∫45 ⅆ 2 )24(1 −sin ⇒3 ∫ⅆ ⇒1cos 4 ∫ 2 (tan , csc ) ⅆ∫ 3 (cot , sec ) ⅆ∫ (tan ) ⅆ∫⇒3∫1ⅆcot 4 ⇒1 [∫ tan4 ⅆ()ⅆ1 + 2Последнее преобразованиеможет быть применимо поразному.Приэтом, = sin 1 − 2достаточно решить только = tan 1 + 2однуизполученныхподзадач. В дереве такаявершина определяется ИЛИ-вершиной и обозначается как:AТаким образом, все дерево называется И/ИЛИ-деревом илидеревом декомпозиции задачи. Какую из полученныхИЛИподзадач следует решить? Выбор может основываться настандартных стратегиях поиска: в глубину, в ширину и наBCоснове функции оценки задач.

В данном случае в качестветакой функции может быть глубина вложенности композиции функций. Таккак ни одно из безопасных преобразований не применимо, то выбираетсявторое эвристическое преобразование:4∫ tan ⅆ ⇒2 ∫ⅆ1 + 24Применив ряд безопасных преобразований получаем И-вершину:411∫ⅆ ⇒⇒4 ∫( 2 − 1 +) ⅆ ⇒3,1 ∫ 2 ⅆ − ∫ 1 ⅆ + ∫ⅆ221+1+1 + 2Первые два интеграла табличные, поэтому вершины, отвечающие этимподзадачам, являются листьями в И/ИЛИ-дереве. Последняя подзадача спомощью преобразований также сводится к табличному интегралу:∫1ⅆ ⇒3 ∫ 1 ⅆ ⇒2 z1 + 2Таким образом, исходная задача является решенной, так как решены все ееподзадачи.

Полученный алгоритм можно изобразить в виде схемы:Заключение.В 1961 году Джеймс Роберт Слейгл разработал программу SAINT (SymbolicAutomatic INTegrator) для решения задачи символьного интегрирования. Онарешила 54 из 56 самых трудных задач.

Две неудачи связаны с недостаткомпреобразований, так что это исключение. Как много знаний было необходимодля этого? Программа состояла из: 26 элементов знаний 12 безопасных преобразований 12 эвристических преобразованийЗнание о знании – сила..