Cтраница 3
Задача ( 1 2) разветвлена на три подзадачи, как это показано на рис. 3.26, где представлено полное дерево ветвления. На этом рисунке отмечены подзадачи, для которых 1-дерево является циклом. [31]
На практике, если две точки находятся далеко друг от друга, этот алгоритм обычно выполняетсядолыпе, чем вычисление полного дерева кратчайших путей. Это объясняется тем, что в каждом цикле алгоритма проверяется, достигнут ли искомый узел. С другой стороны, если узлы расположены близко друг к другу, выполнение этого алгоритм а займе т меньше времени, чем построение полного дерева кратчайших путей. [32]
В целях нумерации последовательных вершин ветвления положим, что я обозначает k - ю вершину ветвления в ситуации, когда полное дерево допустимых частичных решений Р просмотрено с использованием правила S и вершины не исключены посредством какого бы то ни было правила исключения. Когда в ВВ или ВВ2 добавляются правила исключения, то я & не будет подвергнута ветвлению, если она или кто-либо из ее предков были исключены из активного множества. Поскольку SiSzS и LiL2L, последовательности ветвлений в ВВ: и ВВ2 являются подпоследовательностями только что описанного порядка. Эти подпоследовательности отыскиваются путем рассмотрения только тех вершин, которые действительно подвергаются ветвлению. Докажем () методом индукции по вершинам яь, являющимся последовательными кандидатами для ветвления, вплоть до окончания BBi ( при nknt) - В качестве предположения индукции примем, что система () справедлива для nb-nh. Покажем, что () справедлива для вершины nk 1, являющейся следующим возможным кандидатом на ветвление. [33]
Интуитивно понятно, что каждый основной факт, который может быть выведен из Р и EDB восходящим методом путем конструирования полного дерева доказательства G, может быть также выведен нисходящим методом ( с помощью обратного вывода) вначале путем конструирования дерева поиска Т, а затем путем трансформации Т в G. Поскольку для каждого основного факта, который является следствием Р и EDB, существует полное дерево доказательства, мы приходим к заключению, что каждый такой факт может быть получен с помощью обратного вывода. [34]
Поскольку существует максимально maxdepth ( P, EDB) различных основных фактов, которые могут встречаться в качестве меток, то любое полное дерево, содержащее по крайней мере один новый факт на каждом уровне, не может иметь более maxdepth ( P, EDB) уровней. [35]
В добавление к ограничениям и склеиванию, которые, очевидно, могут сократить поиск в случае, если ищутся все решения на полном дереве, существует эвристический метод, который может оказаться полезным, когда существование решения вызывает сомнения или когда вместо всех решений нужно найти только одно. [36]
Используя программу 9.5 в программе 9.6 непосредственно для перемещения по массиву слева направо, применим функцию fixUp с тем, чтобы элементы, располагающиеся слева от указателя просмотра, образовывали пирамидально упорядоченное полное дерево. Затем, во время выполнения процесса нисходящей сортировки мы помещаем наибольший элемент на то место, которое освобождается по мере уменьшения размеров сортирующего дерева. Иначе говоря, процесс нисходящей сортировки подобен сортировке выбором, однако при этом он пользуется более эффективным методом обнаружения наибольшего элемента в неотсортированной части массива. [37]
В некоторых приложениях необходимо находить кратчайший путь между двумя точками, при этом остальные пути в полном дереве кратчайшего маршрута не важны Простой способ нахождения двухточечного кратчайшего пути ( point-to - point shortest path) состоит в том, чтобы вычислить полное дерево кратчайших путей с помощью алгоритмов расстановки или коррекции меток, а затем выбрать из дерева кратчайший путь между двумя точками. [38]
В матрице (6.2.26) с ранее зафиксированными ( s - 1) строками фиксируется s - я строка. Для получения полного дерева решений необходимо г 0 шагов ветвления. [39]
Выберем какой-либо узел порядка / гь допустим х1 ( в полном дереве в качестве первого концевого узла кодового дерева. Все узлы полного дерева любого порядка, большего или равного nt, еще можно использовать как концевые узлы кодового дерева, за исключением доли D - узлов, которые исходят из узла хх. [40]
Прежде всего определим полное дерево графа. Далее, когда речь будет идти о деревьях, под ними имеются в виду покрывающие деревья графа. Дерево содержит п - 1 ветвей и т-п 1 хорду. [41]
При решении этой задачи было решено 11 оценочных подзадач, каждая из которых сводилась к нахождению кратчайшего 1-дерева. На рис. 3.26 показано полное дерево ветвления для симметричной задачи. [42]
В следующем разделе мы расширим обсуждения до полного дерева процессов к до лесов таких деревьев, которые представляют логически независимые процессы. [43]
Строится покрывающее дерево сети N. Если это дерево не имеет солистов, то построение полного дерева закончено и оно совпадает с покрывающим деревом. [44]
Причина заключается в том, что отношение неразличимости не является более транзитивным. Условимся также при отсутствии особых оговорок под базисом S3 полного дерева понимать базис, определяемый той процедурой, которая была принята в § 2 гл. [45]