Глубина - дерево
Cтраница 2
Рассматривая эти процедуры с точки зрения времени их выполнения, напомним, что каждая из процедур РАСЦЕПИТЬ и СЦЕПИТЬ выполняется за время 0 ( ogk), где k - размер очереди до расцепления или после сцепления. А так как глубина дерева Т также равна O ( logjV), то время выполнения процедуры СПУСК равно 0 ( og2N) в худшем случае. Что касается процедуры ПОДЪЕМ, то, как мы видели ранее, время выполнения процедуры СОЕДИНИТЬ также равно O ( logjV), и поэтому та же оценка применима и в этом случае. Аналогичный анализ времени выполнения можно использовать и в случае удаления точки из текущего множества, и мы оставляем его в качестве упражнения для читателя. [16]
Единственный способ уменьшения глубины дерева - это объединение дочерних узлов корня, при котором образуется новый корень. [17]
 |
Пары предок-потомок, разделенных разным числом поколений. [18] |
Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения. [19]
Поисковые шаги и шаги доказательства SLD-опровержения в общем случав перемежаются. Кроив того, из-за линейной структуры SLD-опровержения можно ожидать, что глубина линейного дерева опровержения в худшем случае экспоненциально зависит от глубины соответствующего дерева доказательства. [20]
Отсюда получаем при L 80, что условием целесообразности использования системы PROMPTER является требование, чтобы угадывалось не менее 27 символов из числа задуманных оператором. Сразу же отметим, что из приведенных выкладок следует, что при глубине дерева меньшей, чем размер экрана, требование на размер угаданной части вводимой строки ослабляется. [21]
Отправной точкой может послужить И / ИЛИ-дерево, приведенное на рис. 14.2. Постарайтесь либо построить систему на определенную глубину дерева, либо сделать ее более специализированной, разрисовав подробнее одно из поддеревьев, выбор усилителя или гитары. [22]
 |
Объекты, показанные на рисунке, удовлетворяют отношению встав ( Дер 6НДа Мб НДб. [23] |
Деревья Дер и НовДер имеют одну и ту же глубину. Разумеется, не всегда возможно сохранить ту же глубину дерева. [24]
При применении к дереву мемо-версии, составленной из функций depth и deepest, происходит последовательное вычисление величин depth и deepest для поддеревьев, начиная с листьев. Затем, двигаясь вверх по дереву, вычисляются соответствующие величины для внутренних вершин путем операции просмотра для получения результатов для их ближайших потомков. Это приводит к эффективной реализации, ограничивающей размер таблицы глубиной дерева, поскольку при занесении результата для данной внутренней вершины в мемо-таб-лицу удаляются два ее элемента и остается только один элемент, соответствующий всему поддереву, для которого данная внутренняя вершина является корневой. [25]
Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину ( или размер) и сами сбалансированы. Глубина сбалансированного дерева приближенно равна log п, где п - Число вершин дерева. Бремя, необходимое для вычислений, производимых отношениями внутри, добавить и удалить над двоичными справочниками, пропорционально глубине дерева. [26]
Таким образом, может показаться, что иерархические указатели всегда оказываются более предпочтительными. Справедливо, что в случае дерева с единственным корнем и его порожденными сегментами иерархические указатели и указатели вида порожденный / подобный являются, по существу, одними и теми же. Поэтому мы могли бы предпочесть первые по соображениям экономки используемого пространства. Однако при глубине дерева более чем два, каждый сегмент которого имеет много порожденных, команда GET, специфицирующая путь к листу, находящемуся в дереве далеко вправо, выполняется значительно быстрее, если используются указатели вида порожденный / подобный. [27]
Как было показано в разд. Как правило, для комбинаторных задач оценка более точная, чем граничная оценка, теряет свойство быть границей. Если бы для какой-то комбинаторной задачи удалось построить достаточно точную оценку критерия оптимизации, да еще являющуюся верхней ( или нижней) границей для значений критерия оптимизации, тогда решение этой задачи методом, изложенным в разд. Иными словами, на каждом уровне дерева вариантов выбиралась бы одна вершина с максимальной оценочной функцией, уменьшение оценочной функции по мере увеличения глубины дерева было бы маловероятным, поэтому маловероятным был бы и возврат на предыдущие уровни дерева к вершинам с большим, чем текущее, значением оценочной функции. Другими словами, число висячих вершин было бы равно минимальному NVmtn, дерево имело бы минимальное число ветвей, а целенаправленность поиска Р N. INV min была бы максимально высока для данного алгоритма поиска. [28]
Во-первых, если интуиция подсказывает, что все решения будут иметь некоторый определенный вид, то благоразумно строить поиск так, чтобы раньше других исследовать возможные решения именно этого вида. В общем случае, для того чтобы обнаружить, что путь не может вести к решению, должно быть накоплено несколько ограничений, и обычно это случается на фиксированной глубине дерева. В результате большее число узлов будет запрещено, если большая часть ветвлений будет находиться ближе к листьям, чем к корням. Конечно, нужно понимать, что такой вид перестройки дерева может оказаться бесполезным, если должно быть исследовано все дерево. Более того, даже если не требуется исследовать все дерево, перестройка может переместить решения не ближе к началу поиска, а дальше от него. [29]
Здесь уместно сделать несколько замечаний относительно эффективности поиска в справочниках. В среднем нам придется просмотреть примерно половину списка. Если множество представлено двоичным деревом, то время поиска будет пропорционально глубине дерева. [30]
Страницы: 1 2 3