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


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


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

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

Функциональной зависимости (F->Y1), где F -функциональная величина типа (X->-Y), предполагающей предварительный синтез процедуры вычисления F, входными параметрами которой являются величины из списка X.

Операторных зависимостей, предполагающих синтез т процедур с входами "условиями подзадач" X1, Х2, ..., Хь-

Вариантных зависимостей, предполагающих, что создаются две ветви вычислений: для первой известны значения всех величин из списка Y1, для второй - из списка У2.

Рассмотрим простой (но типичный) пример. Пусть имеют место функциональная зависимость D1: (A, В, СR Е) и операторные зависимости D2: ((СR Е ) R Е1), D3:(( BR Е1))R Е2)), D4: ((AR Е2 ) R Е3). Необходимо найти Ез. Для этого следует решить подзадачу (AR Е2 ). Если воспользоваться зависимостью D3, то придем к поиску решения новой подзадачи ( BR Е1). Если использовать зависимость D2, то придем к необходимости решения подзадачи ( CR Е), которая согласно D1 разрешима только тогда, когда A и В известны.


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



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