Сначала вычислить ценовую функцию h' каждого нового потомка. Затем выбрать тот узел, поле (yields) которого имеет минимальную цену среди всех нерасширенных узлов.
На фиг. 5 дан пример расширения узла. Сначала непокрытый набор содержит элементарную операцию store(sig1-,,sig1,4r), в которой sig1 изменяет состояние в каждых четвертых циклах, и некоторые другие элементарные операторы ({u}).
Uncovred U: store(sig1-,,sig1,4r), {u} Added A: {a} Covered C: {c} Function F: {f} / \ / \U: value(cnt1,rising 4r), {u} U: {u}A: {a} A: store(sig2-,sig2,2r),C: store(sig1-,cnt1,sig1,), {c} store(sig3-,,sig3,1r), {a}F: load sig1- to sig1, {f} C: store(sig1-,,sig1,4r) F: 3-bit count sig1,sig2,sig3 {f}Фиг. 5 Пример образования графа. (node expansion)
После расширения узла функция Load (загрузка), функция трех-битового счетчика и другие функции могут выполнить функцию операции памяти (store). Если система выбрала Load, то служебный оператор, генерирующий сигнал load-control каждый четвертый такт цикла, будет добавлен к набору непокрытых операторов.
Если система выбирает трехбитовый счетчик, тогда она же выбирает "clock" (тактовый сигнал) как управляющий сигнал счетчика (count-control) так, чтобы не нужно было служебной операции. С другой стороны, два первых выхода счетчика не используются и, следовательно, эти операторы должны быть помещены в набор дополнительных операторов.
При функциональном описании целью проектирования является выбор наименьшего числа функций, покрывающих каждый элементарный оператор. Число добавленных элементарных операторов должно быть наименьшим по возможности. Таким образом, система использует следующую эвристическую ценовую функцию направленного поиска (to direct the search) - h':
h' = W * UCO + AO + F,
где W - weight (вес);
UCO - uncover - число непокрытых операторов;
АO - add operation - число добавленных операторов;
F - число функций.
Увеличение веса непокрытых операторов смещает стратегию по направлению использования параметризованных функций, которые обычно покрывают больше элементарных операторов. Эта стратегия сокращает итоговое время поиска (search time complexity). Цена заключается в том, что увеличивается число добавленных операций, а новые добавленные операции ведут к затратам (are likely to be wasted).
Как было установлено ранее (As we stated earlier) целью шага функционального описания является поиск минимума набора функций, которые покрывают все элементарные операции (ЭО).
Подцелью является выбор функции, покрывающей часть ЭО. Так как (since) различные функции могут покрывать несколько ЭО, эти подцели взаимосвязаны (interact). Простейший путь управления взаимосвязью есть определение порядка достижения подцелей. / Sacerdoti E. D. Нелинейная природа планирования.
Proc. Int'l Joint Conf. Artificial Intelligence. 1975 pp. 206-214 /.
Этот порядок гарантирует, что действия по достижению некоторой подцели не отрицают уже достигнутых подцелей или не блокирует (процесс...?
(or block an as yet unachieved one).
Стратегия порядка в системе выполняется точно по ценовой функции h'. Стратегия есть выбор функции, которая покрывает наибольшее число непокрытых ЭО, однако оставляющей минимум неиспользованных (добавленных) операторов.
Для исполнения этой стратегии в системе используются методы планирования и метапланирования.
Планирование есть решение проблем искусственного интеллекта, обращенных к таким сверхзадачам моделей как объединение интерактивных подзадач (подцелей). Это означает попытку решить всю проблему путем решения конкретных подцелей, которые часто легче выполнить.
Метапланирование есть метод планирования, имеющий дело с управлением взаимодействия между подцелями. Это обеспечивается указаниями, помогающими определить порядок достижения каждой подцели и выбрать лучшее решение среди различных альтернатив. Таким образом, метапланирование связано с управлением решениями по планированию - с определением когда и каким образом делать заключения для достижения подцелей и когда их делать.
Метапланирование помогает повысить КПД поиска путем сокращения неперспективных направлений поиска. Без метапланирования для покрытия некоторых типов ЭО потребуется слишком много функций. Например, оператор store(a-,,a,8r), который говорит, что сигнал а изменяет свое состояние
в каждый восьмой такт циклически и может быть покрыт (преобразован) функциями Load (загрузка), Change states (изменение состояния) и Count (счет). Кроме того, существуют различные возможные функции счетчика.
Оператором может быть старший четвертый разряд счетчика с сигналом тактирования как управляющим сигналом счетчика. Или взять 3-битовый счетчик с управляющим сигналом, кратным двум по отношению к тактирующему сигналу. Или можно взять двухбитовый счетчик с управляющим сигналом тактирования, который имеет более продолжительный период.
Без метапланирования покрытие узла сгенерировало бы всех потомков узлов, которые содержат эти функции. С методом метапланирования, однако, система может выбрать более подходящие функции - те, которые содержат только один неиспользованный оператор, между двумя. Например, 4- битовый счетчик может покрыть те операторы, которые только что описали, за исключением (only if there is) оператора store(b-,,b,2r) - второго младшего бита разряда.
Существует неиспользованный оператор (третий младший разряд) функции между этими двумя операторами и другой неиспользованный оператор - самый младший разряд функции счетчика.
Другим преимуществом метапланирования является то, что безразлично в каком порядке представляются ЭО. Методы поиска по метапланированию обычно дают результаты быстрее, чем без него.
С целью иллюстрации эффективности этой программы она применена к входной последовательности фиг. 1 (x - 10110, z - 00001). Найдены следующие функции:
1. Последовательно - параллельный регистр.
Эта функция покрывает четыре утверждения (value). Значения входного сигнала X запоминаются последовательно входами V1.. V4.
2. "Нет" - эта функция покрывает оператор отрицания. Функция инвертирует значение V2 для генерации V5.
3. "И". Эта функция покрывает оператор И. Она генерирует выходной сигнал Z = V1 & V2 & V3 & V4 & V5.