Побочная вершина
Cтраница 1
Эффективность метода побочных вершин ( без цепочек) примерно соответствует эффективности, достигаемой при методе копирования. Выполняется одинаковое количество редукций, поскольку в обоих случаях результирующий подграф ( с корнем PR) редуцируется к СЗНФ только один раз. Более того, в обоих случаях требуется одинаковое количество памяти, поскольку обе схемы генерируют только одну избыточную вершину: побочную вершину и дубликат вершины редекса соответственно. [1]
 |
Редукция графов с помощью копирования при применении функций-проекторов.| Редукция графов с использованием побочных вершин при применении функций-проекторов. [2] |
Недостатком метода побочных вершин является то, что каждая вершина может быть синонимом, и должна выполняться соответствующая проверка ( с помощью просмотра поля-метки), прежде чем содержимое вершины может быть использовано. Это требует небольшого, но постоянного дополнительного времени на этапе выполнения. [3]
Отсюда следует, что если мы выбираем вершину-редекс PR для редукции первой, то метод копирования, не требующий каких-либо изменений алгоритма редукции графов, является наилучшим. Однако метод побочных вершин также может ис пользовать изменение порядка выбора редексов, поскольку если PR редуцируется первой, то в момент замены РА будет уже известно, является ли PR вершиной-синонимом. [4]
На рис. 5.12 принят отражатель размером в четыре длины волны. К искателю возвращается только слабое звуковое давление, от размытой области побочной вершины при коротких импульсах и эхо-импульсы от краевых волн. [5]
В прогибе Сорокина в 1996 г. при работах по программе ЮНЕСКО Плавучий университет были открыты 26 грязевых вулканов. Газогидраты выявлены в колонках осадков и брекчии, поднятых со склонов или побочных вершин грязевых вулканов. Отсутствие газогидратов в жерлах основных вершин грязевых вулканов объясняется неблагоприятными геотермальными условиями. [6]
В каждом случае вершины, помеченные, могут быть разделяемыми, так что после редукции они не превращаются в мусор, но могут стать редексами. Это может привести к повторному вычислению выражения 12 ( соответствующий подграф в случае ( б) находится в СЗНФ), что является весьма неэффективным. Существуют два решения этой проблемы, первое из которых основано на использовании так называемых побочных вершин, или вершин-синонимов, помечаемых в графе буквой в. Если выражение представлено графом, корнем которого является побочная вершина, то оно интерпретируется точно так же, как выражение, представленное графом, корнем которого является вершина, подвешенная к побочной. [7]
Эффективность метода побочных вершин ( без цепочек) примерно соответствует эффективности, достигаемой при методе копирования. Выполняется одинаковое количество редукций, поскольку в обоих случаях результирующий подграф ( с корнем PR) редуцируется к СЗНФ только один раз. Более того, в обоих случаях требуется одинаковое количество памяти, поскольку обе схемы генерируют только одну избыточную вершину: побочную вершину и дубликат вершины редекса соответственно. [8]
В каждом случае вершины, помеченные, могут быть разделяемыми, так что после редукции они не превращаются в мусор, но могут стать редексами. Это может привести к повторному вычислению выражения 12 ( соответствующий подграф в случае ( б) находится в СЗНФ), что является весьма неэффективным. Существуют два решения этой проблемы, первое из которых основано на использовании так называемых побочных вершин, или вершин-синонимов, помечаемых в графе буквой в. Если выражение представлено графом, корнем которого является побочная вершина, то оно интерпретируется точно так же, как выражение, представленное графом, корнем которого является вершина, подвешенная к побочной. [9]
Страницы: 1