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

Cтраница 3

Из этого следует, в частности, что корню дерева присвоена оценка, равная цене игры для первого игрока. Рассмотрим, например, рис. 3.9; здесь терминальным вершинам присвоена оценка нуль, если выигрывает первый игрок, но за максимальное количество ходов, - 1, если выигрывает второй игрок, и 1, если первый выигрывает раньше, чем за максимум ходов. Число, написанное около каждой вершины, представляет собой оценку, присвоенную этой вершине алгоритмом минимаксной оценки. Заметим, что корню присвоена оценка нуль, а это указывает, что первый игрок может добиться выигрыша при максимальном количестве ходов - тот же самый результат был установлен в разд. Мы рекомендуем в качестве упражнения дать оценки для большого дерева, изображенного на рис. 3.8. ( Какую оценку следует присвоить корню этого дерева. [31]

Рост СДБ-дерева при включении вершин из последовательности. [32]

В каждой строке рисунка приведены последовательные состояния соответствующего дерева в моменты, как и раньше отмеченные в последовательности ключей точкой с запятой. Рисунки особенно наглядно демонстрируют третье свойство СДБ-деревьев - все терминальные вершины лежат на одном уровне. По-лому напрашивается сравнение этих структур с только что подстриженным садовым кустарником. [33]

Иерархическая модель ИНЕС представляет базу данных в виде дерева, терминальные вершины которого соответствуют элементарным данным ( как правило, это числа и тексты), корень - всей базе данных, а прочие вершины - структурным информационным объектам различной сложности. Важно понимать, что реальные данные содержатся только в терминальных вершинах дерева, нетерминальные вершины служат для структуризации информационных объектов, объединяя данные, соответствующие подчиненным вершинам. Посредством использования ссылочных связей модель допускает создание сетей и потенциально бесконечных деревьев. [34]

Рассмотрим схему R как гиперграф. Поскольку к нему редукция неприменима, то в R нет ни ребер, содержащих терминальные вершины, ни ребер, содержащихся в каком-нибудь другом ребре. Докажем, что R не может содержать разделяющего ребра. [35]

Исполнительная система может работать с планами, не абсолютно успешными, если предусмотреть возможность повторного вызова планирующей системы, когда достигается терминальная вершина плана, но задача еще не решена. Возможно, более предпочтительно было бы вызывать планирующую систему еще до того, как терминальная вершина будет достигнута, а именно когда достигается вершина плана, у которого ни одна из дочерних вершин не удовлетворяет задаче. Даже если большая часть этапов плана остается не выполненной в этой ситуации, все-таки уже ясно, что они не смогут удовлетворить задаче, и планирующая система тогда предпримет поиск другой последовательности шагов, более желательной в смысле успешного завершения исполнения плана. Можно возразить, что планирующей системе следовало бы предоставить возможность постепенно развертывать дерево поиска после каждого шага исполнения плана, поскольку вероятности вхождения вершин и успеха плана в целом изменяются на каждом шаге. [36]

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

Фрагмент дискриминационной сети для обобщенного события ПЕРЕДАТЬ ИНФОРМАЦИЮ. [38]

Средством, с помощью которого может быть решена проблема выбора лексемы, являются дискриминационные сети [ Фейгенбаум, 1963 ], соответствующие различным обобщенным событиям семантической сети. Каждая дискриминационная сеть представляет собой бинарное дерево с предикатами, стоящими в вершинах ветвления, и конкретными лексемами, стоящими в терминальных вершинах. [39]

Если у Нг больше одного ребра, то по индуктивному предположению он имеет два выступа. Поскольку некоторое ребро гиперграфа HI, скажем Elt содержит F, то самое большее один из выступов Нг может обладать тем свойством, что все содержащиеся в нем терминальные вершины принадлежат F. [40]

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

Теперь можно точно сформулировать действительный алгоритм построения дерева достижимости. Каждая вершина / дерева связывается с расширенной маркировкой mU ]; в расширенной маркировке число фишек в позиции может быть либо неотрицательным целым, либо со. Каждая вершина классифицируется или как граничная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Граничными являются вершины, которые еще не обработаны алгоритмом; алгоритм превратит их в терминальные, дублирующие или внутренние вершины. [42]

К сожалению, исключение элемента обычно проходит не так просто, как включение. Простым оно оказывается лишь в случае, если исключаемый элемент - терминальная вершина или вершина с одним потомком. Трудность возникает, если нужно удалить элемент с двумя потомками: ведь мы не можем указать с помощью одной ссылки сразу два направления. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева, причем они должны иметь самое большее одного потомка. [43]

Если рассматривать иерархические связи между информационными объектами, то информацию, содержащуюся в БД, можно изобразить в виде дерева, терминальные вершины которого изображают элементарные данные ( как правило, числа и тексты), корень - всю БД, а прочие вершины - структурные информационные объекты различной сложности. Такое дерево мы будем называть деревом базы данных ( ДБД), оно отражает логическую структуру информации. Каждое элементарное данное ( число или текст) изображается в ДБД отдельной терминальной вершиной; нетерминальным вершинам не соответствуют реальные данные - эти вершины изображают структурные информационные объекты, объединяющие в себе данные, соответствующие подчиненным вершинам. [44]

При поиске в глубину сначала раскрывается та вершина, которая была построена самой последней. Глубина вершины в графе определяется следующим образом: 1) глубина вершины-корня равна нулю; 2) глубина промежуточной вершины равна единице плюс глубина наиболее близкой вершины-предка. При практической реализации поиск в глубину в некотором направлении завершается в следующих случаях: 1) при достижении целевой вершины; 2) при достижении терминальной вершины; 3) при построении в ходе поиска вершины, глубина которой превышает некоторую граничную глубину. [45]

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