4.8. МЕХАНИЗМЫ ПЛАНИРОВАНИЯ ПРИ СВЕДЕНИИ ЗАДАЧ К ПОДЗАДАЧАМ

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

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

Решение всех этих задач эквивалентно решению первоначальной задачи.

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