Reasoning: goal
trees and problem
solving
Асирян Александр
Глоссарий
Problem reduction – декомпозиция задачи
И/ИЛИ-дерево – структура, отображающая
замену решения одной задачи решением серии
более простых задач
Глубина декомпозиции – высота И/ИЛИ-дерева
Знания – задачи, решение которых известно
Асирян
2
Глоссарий
И/ИЛИ-дерево состоит из двух видов вершин:
И-вершина – для решения задачи необходимо
решить все задачи, отвечающие дочерним A
вершинам
B
И
C
ИЛИ-вершина – для решения задачи необходимо
решить хотя бы одну задачу, отвечающую
A
дочерней вершине
ИЛИ
B
Асирян
C
3
Глоссарий
Безопасное преобразование –
изменение, не влияющее на ход решения
задачи
(соответствует ребру из И-вершины)
Эвристическое преобразование –
изменение, от которого зависит
существование решения задачи
(соответствует ребру из ИЛИ-вершины)
Асирян
4
Алгоритм декомпозиции
задачи
Применить все
безопасные
преобразования
Посмотреть
задачи в Знаниях
Исходная задача
решена?
НЕТ
Применить
эвристическое
преобразование
Асирян
ДА
Выбрать задачу
для решения
5
Способы выбора задачи
Поиск в глубину
Поиск в ширину
Выбор вершины с лучшей оценкой
Асирян
6
Символьное
интегрирование
∫
−5 �
4
A
5
2 2
( 1− � )
Асирян
Безопасные
преобразования
ⅆ�
Разделить
многочлен
ы
Разделить
многочлен
ы
7
Символьное
интегрирование
∫
−5�
4
ⅆ�⇒
∫
1
5
22
(1−� )
Асирян
4
Безопасные
преобразования
A
5�
ⅆ�
5
B
22
(1−� )
Разделить
многочлен
ы
Разделить
многочлен
ы
8
Символьное
интегрирование
Безопасные
преобразования
A
B
C
Асирян
Разделить
многочлен
ы
Разделить
многочлен
ы
9
Символьное
интегрирование
Знания
C
Асирян
10
Символьное
интегрирование
Знания
C
Асирян
11
Символьное
интегрирование
Эвристические
преобразования
C
Асирян
12
Символьное
интегрирование
Эвристические
преобразования
C
D
Асирян
13
Символьное
интегрирование
Эвристические
преобразования
C
D
E
Асирян
F
14
Символьное
интегрирование
Эвристические
преобразования
F
G
Асирян
15
Символьное
интегрирование
Безопасные
преобразования
F
G
H
Асирян
Разделить
многочлен
ы
Разделить
многочлен
ы
16
Символьное
интегрирование
Безопасные
преобразования
F
G
H
I
Асирян
J
K
Разделить
многочлен
ы
Разделить
многочлен
ы
17
Символьное
интегрирование
Знания
3
�
2
� :∫ � ⅆ � ⇒2
3
F
G
H
I
Асирян
J
K
18
Символьное
интегрирование
Эвристические
преобразования
F
G
H
I
Асирян
J
K
L
19
Символьное
интегрирование
1
ⅆ�⇒
1ⅆ�⇒
z
∫ 1+�2 3∫ 2
Знания
F
G
H
I
J
K
L
Асирян
20
SAINT
В 1961 году Джеймс Роберт Слейгл разработал
программу SAINT (Symbolic Automatic INTegrator)
для решения задачи символьного интегрирования.
Она состояла из:
26 элементов знаний
12 безопасных преобразований
12 эвристических преобразований
Асирян
21
Спасибо за внимание!
