Терминальная вершина

Cтраница 4

Доказательство леммы 13.2. Согласно предложению 13.2, редуктивный алгоритм Грэхема сохраняет ацикличность. Если в процессе редукции ациклического гиперграфа Я, выполняемой с помощью этого алгоритма, на каком-либо шаге окажется, что промежуточный гиперграф нередуцирован, то к нему можно применить правило УР. Если же этот промежуточный гиперграф редуцирован, то либо мы уже достигли гиперграфа с единственным ребром, либо выполняется предложение 13.4, и мы можем использовать правило УВ для удаления некоторой терминальной вершины. Поскольку при применении правил редукции в алгоритме Грэхема общее количество ребер и вершин уменьшается, то этот алгоритм постепенно редуцирует Я до пустого гиперграфа. С другой стороны, алгоритм редукции не может завершиться успешно в случае циклического гиперграфа Я. Действительно, такой гиперграф должен иметь по крайней мере три ребра. Если бы редукция Я завершалась успешно, то одним из ее промежуточных результатов оказался бы гиперграф, обладающий в точности двумя ребрами и тем самым ациклический. [46]

Структуру фрейма можно представить в виде сети, состоящей из узлов и связей между ними. Верхние уровни вершин фрейма определены, так как образованы понятиями, которые всегда справедливы по отношению к предполагаемой ситуации. На более низких уровнях имеется много особых вершин, называемых терминалами, которые заполняются в процессе активации фрейма характерными примерами или данными. Каждая терминальная вершина может быть связана с определенным условием задания этой вершины. Простые условия задаются маркерами, например, в виде требования на определенный тип данных или на объект подходящего размера, маркер может также указывать на другой фрейм, который определяет терминал. Более сложные условия определяют тип отношений между понятиями, которыми будут задаваться терминальные вершины фрейма. [47]

Описание заполнения макетов выводимых документов подготавливается по правилам системы макетного вывода. Описание заполнения окон макета производится отдельно по частям макета. Для каждой части в скобках через запятую указываются арифметические выражения, фрагменты запроса или системные переменные. Значения арифметических выражений, терминальных вершин БД, констант и рабочих полей, которые упоминаются во фрагменте запроса, и значения системных переменных заносятся в последовательные окна макета части. Обращение % % OUTP ( имя-части, имя-формы) вызывает печать заполненной части документа. [48]

Третий шаг построения дерева достижимости. [49]

Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок ( называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки - маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки называются терминальными вершинами. [50]

Поскольку мы допускаем возможность остановки планирующей системы до достижения абсолютного успеха, вполне допустима остановка системы и в случае, когда еще не достигнут абсолютный неуспех. Здесь сразу приходят в голову два случая. Первый из них имеет место, когда дерево поиска достаточно развернуто и можно уже определить, что ни один из планов дерева нельзя квалифицировать как успешный. Это обычно случается, когда для каждого плана в дереве вероятность достижения терминальной вершины, не удовлетворяющей цели, больше некоторой пороговой величины. [51]

Начальная вершина графа отображает М0, а остальные вершины соответствуют другим маркировкам. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т.е. по наличию листьев - терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях ограниченности. [52]

Говоря точнее, это означает, что для каждого i, 1 i т, в RJ найдется такое ребро Rit что RI Л X Y (, и нет ни одного ребра RJ, для которого Rt Л X содержалось бы в R f X собственным образом. Для каждого Yit 1 i т, существует X /, / i, и такие ребра Ri и RJ в R, что RI з Yit RJ э Yt и Rt связано с R, путем, не проходящим через X. Удаление вершин при редукции не меняет его свойств, поскольку в пересечениях соседних ребер нет терминальных вершин и ни одна из вершин в У - и Y, не является терминальной. [53]

Страницы: 1 2 3 4