Системы искусственного интеллекта


Оценки сложности задачи планирования


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

1. Анализ вычислительных задач оказывается PSPACE-полной проблемой даже при условии, что "пустых" величин W нет .

2. Для вычислительных моделей без функциональных величин, т. е. с пустыми Db и F, проблема анализа вычислительных задач оказывается: а) PSPACE-полной для Н, содержащих функциональные и операторные зависимости без W ; б) NP-полной для Н, содержащих только функциональные и вариантные зависимости без "пустой" величины W ; в) полиномиальной (по времени работы планировщика) для Н, содержащих только функциональные и неявные зависимости; г) можно построить планировщики с линейным временем работы для Н только с функциональными зависимостями без W и для Н с функциональными и неявными зависимостями .

В системе ПГИЗ Db и F пусты, а в Н имеются только функциональные и операторные зависимости без "пустой" величины W. В системе автоматического синтеза программ СПОРА используется исчисление предикатов, для которого разработана специальная стратегия вывода .

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

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


Начало  Назад  Вперед



Книжный магазин