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

Как было отмечено в главе 5, идеально декомпонуемые задачи являются очень привлекательными, но встречаются редко1. Проекты многих систем планирования (особенно планировщиков с частичным упорядочением, описанных в разделе 11.3) основаны на предположении, что большинство задач реального мира являются частично декомпонуемыми. Это означает, что планировщик может работать над подцелями независимо, но, скорее всего, ему потребуется также выполнить определенную дополнительную работу по объединению результирующих субпланов. Применительно к некоторым задачам такое предположение не оправдывается, поскольку велика вероятность того, что работа над одной подцелью будет приводить к разрушению результатов работы над другой подцелью. Именно из-за такого взаимодействия подцелей и являются трудноразрешимыми многие головоломки (подобные задаче игры в восемь).