1.4. СВЕДЕНИЕ ЗАДАЧИ К ПОДЗАДАЧАМ

В некотором смысле более тонкий подход к решению задачи связан с понятием подзадач. При таком подходе производится исследование исходной задачи с целью выделения такого множества подзадач, чтобы решение некоторого определенного подмножества этих подзадач содержало в себе решение исходной задачи. Рассмотрим, например, задачу о проезде на автомобиле из Пало-Альто (шт. Калифорния) в Кембридж (шт. Массачусетс). Эта задача может быть сведена, скажем, к следующим подзадачам:

Подзадача 1. Проехать из Пало-Альто в Сан-Франциско.

Подзадача 2. Проехать из Сан-Франциско в Чикаго, шт. Иллинойс.

Подзадача 3. Проехать из Чикаго в Олбани, шт. Нью-Йорк.

Подзадача 4. Проехать из Олбани в Кембридж.

Здесь решение всех четырех подзадач обеспечило бы некоторое решение первоначальной задачи.

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

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

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

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