Второй способ формализации задач

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

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

Соответствующая задача в замкнутой форме, т. е. формализованная задача, представляется теперь так: найти такую последовательность.

правил декомпозиции Я, Я₂, …, Я", сводящую решение исходной задачи к решению одной или нескольких примитивных подзадач. Когда примитивные подзадачи невозможно заранее указать явно, как в случае с задачей на упрощение алгебраического выражения, так как неизвестно, как должно выглядеть окончательное упрощенное выражение, задаются целевые условия. Это — условия, однозначно определяющие, какие задачи следует относить к примитивным подзадачам.

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

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

При втором способе формализации задачи должны быть заданы:

• 1) множество Р всех подзадач, к которым может быть сведено решение исходной задачи; это множество называют пространством подзадач; в нем должны быть указаны исходная задача, которую следует решить, и простейшие (примитивные) подзадачи, к которым может быть сведено решение исходной задачи и решения которых известны заранее;
• 2) множество правил декомпозиции П_ь П_ъ …, П," позволяющие сводить решение одних задач к решению других задач;
• 3) множество примитивных подзадач; при невозможности явно указать эти подзадачи задаются условия, однозначно характеризующие примитивные подзадачи; такие условия называют целевыми условиями.

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

Пространство подзадач для задач, формализованных вторым способом, можно представить графически в виде ориентированного графа особого типа — И-ИЛ И дерева. Тогда решение задач, представленных вторым способом, сводится к поиску на И-ИЛИ дереве решающего поддерева, в котором корневая вершина соответствует исходной задаче, а листья И-ИЛИ дерева соответствуют примитивным подзадачам. Общий метод (стратегия) решения здесь — сведение к подзадачам, каждая из которых может быть представлена своим способом решения. При этом могут использоваться те же стратегии поиска, что и для решения задач, формализованных первым способом: поиск в глубину, поиск в ширину или эвристический поиск, например, алгоритм программы GPS (General problem solver — Общий решатель задач), предложенной А. Ньюэллом, К. Шоу и Г. Саймоном [8, С. 289].

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