Сжатие - путь
Cтраница 1
Сжатие пути лишь незначительно увеличивает сложность операции отыскания, и, как мы увидим, ее использование дает существенный выигрыш во времени при достаточно большом числе операций отыскания. [1]
 |
Выполнение операции НАЙТИ ( (.| Выполнение операции ОБЪЕДИНИТЬ ( i, j, k. 54. [2] |
Покажем, что сжатие путей значительно ускоряет работу алгоритма. [3]
Крометого, применяем сжатие путей. [4]
Существует множество других способов реализации сжатия пути. Этот метод несколько проще реализовать, чем полное сжатие пути ( см. упражнение 1.16), но он дает тот же конечный результат. [5]
 |
Дерево после выполнения операций ОБЪЕДИНИТЬ. [6] |
Изложим еще одну модификацию этого алгоритма, называемую сжатием путей. Поскольку в общей сложности преобладает сложность операций НАЙТИ, попробуем уменьшить ее. УП г - узлы на этом пути. [7]
На практике пути бывают очень короткими ( особенно, если применяется сжатие путей), так что в данном случае дополнительные издержки, па-видимому, окажутся незначительными. [8]
 |
Результат сжатия путей. [9] |
Вся процедура слияния деревьев для задачи ОБЪЕДИНИТЬ - НАЙТИ, включая сжатие путей, выражена в следующем алгоритме. [10]
Здесь отображен результат обработки случайных пар 100 объектов алгоритмом взвешенного быстрого объединения с сжатием пути. Все узлы этого дерева, за исключением двух, находятся на расстоянии одного-двух шагов от корня. [11]
Рис, 2.17, Результат операции FIND ( 8), примененной к лесу из рис. 2.15, когда используется сжатие пути. [12]
 |
Результаты экспериментального исследования. [13] |
Эти сравнительные значения времени, затрачиваемого на решение случайных задач связности с использованием алгоритмов объединения-поиска, демонстрируют эффективность взвешенной версии алгоритма быстрого объединения. Дополнительный выигрыш благодаря использованию сжатия пути менее очевиден. Здесь М - количество случайных соединений, генерируемых до тех пор, пока все Л / объектов не оказываются связанными. Этот процесс требует значительно больше операций find, чем операций union, поэтому быстрое объединение выполняется существенно медленнее быстрого поиска. Ни быстрый поиск, ни быстрое объединение не годятся для случая, когда значение Л / очень велико. Время выполнения при использовании взвешенных методов явно пропорционально значению Л /, поскольку оно уменьшается вдвое при уменьшении Л / вдвое. [14]
Опрянды-васт ли достигаемая экономия время, требующиеся длн решиаинн сжатия пути. [15]
Страницы: 1 2