Алгоритм - объединение
Cтраница 3
После подготовки отдельных частей алгоритма хотелось бы алгоритм решения всей задачи в целом получить просто путем складывания готовых частей, не производя при этом каких-либо обязательных стыковочных изменений и исправлений внутри отдельных частей, чтобы было достаточно написать лишь алгоритм объединения частей в единый вычислительный процесс решения задачи. [31]
С каждой целью связана совокупность алгоритмов, соответствующих элементам шенноновскои схемы: генераторы ходов, вычисление статической оценки и генераторы анализирующих ходов. Алгоритм объединения статических оценок в рабочие оценки для каждого из предложенных ходов и правило окончательного выбора общие для всей программы и поэтому на рисунке отсутствуют. [32]
Немедленно возникает вопрос, можно ли найти алгоритм, обеспечивающий гарантированную линейную производительность. Существует множество способов дальнейшего совершенствования алгоритма взвешенного быстрого объединения. В идеале было бы желательно, чтобы каждый узел указывал непосредственно на корень своего дерева, но за это не хотелось бы расплачиваться изменением большого количества указателей, как это делалось в случае алгоритма быстрого объединения. К идеалу можно приблизиться, просто делая все проверяемые узлы указывающими на корень. На первый взгляд этот шаг кажется весьма радикальным, но его легко реализовать, а в структуре этих деревьев нет ничего неприкосновенного: если их можно изменить, чтобы сделать алгоритм более эффективным, это следует сделать. Этот метод, названный сжатием пути ( path compression), можно легко реализовать, добавляя еще один проход по каждому пути во время выполнения операции union и устанавливая запись id, соответствующую каждой встреченной вершине, указывающей на корень. [33]
На первый взгляд кажется, что алгоритм быстрого объединения работает быстрее алгоритма быстрого поиска, поскольку для каждой вводимой пары ему не нужно просматривать весь массив; но на сколько быстрее. В данном случае ответить на этот вопрос труднее, чем в случае быстрого поиска, поскольку время выполнения в большей степени зависит от характера ввода. Выполнив экспериментальные исследования или математический анализ ( см. главу 2), можно убедиться, что программа 1.2 значительно эффективнее программы 1.1 и ее можно использовать для решения очень сложных реальных задач. Одно из таких экспериментальных исследований будет рассмотрено в конце этого раздела. [34]
 |
Алгоритм для нахождения множеств эквивалентных состояний в предположении, что Si и sa эквивалентны. [35] |
СПИСОК содержит такие пары состояний ( s, s), что s и s оказались эквивалентными, а следующие за ними состояния ( 6 ( s, a), 6 ( s, a)) еще не рассматривались. Чтобы найти множества эквивалентных состояний, программа применяет алгоритм объединения непересекающихся множеств. НАБОР представляет некоторое семейство множеств. Вначале каждое состояние из St U Sa образует одноэлементное множество. Без потери общности можно считать, что множества Si и S2 не пересекаются. [36]
Верхняя и нижняя границы совпадают также и для алгоритмов union-find, использующих указатели. В 1975 г. Тарьян ( Tarjan) показал, что алгоритм взвешенного быстрого объединения со сжатием пути требует следования по менее, чем 0 ( % V) указателям в случае низкой производительности, и что любой алгоритм с указателями должен следовать более, чем по постоянному числу указателей в случае низкой производительности для некоторых входных данных. На практике эта разница очень мала, поскольку lg V очень мало, тем не менее, нахождение простого линейного алгоритма для этой задачи было темой исследования в течение долгого времени, и найденная Та-рьяном нижняя граница направила усилия исследователей на другие задачи. Более того, история показывает, что нельзя обойти функции наподобие сложной функции log, поскольку они присущи этой задаче. [37]
 |
Несводимый уграф, его каркасы и эквивалентный ему своди. [38] |
Нелинейная его оценка возникает здесь из-за подзадачи, которая формулируется как выполнение последовательности о команд, каждая из которых представляет собой операцию одного из двух видов: НАЙТИ и ОБЪЕДИНИТЬ, работающих над непересекающимися подмножествами вершин уграфа. НАЙТИ ( р) выдает имя того подмножества, которому в данный момент принадлежит вершина р; ОБЪЕДИНИТЬ ( S, S2, S3) строит подмножество 53 5t U 52, а а содержит не более п команд ОБЪЕДИНИТЬ и не более т команд НАЙТИ. Исследования в [20] показали, что алгоритм быстрого объединения непересекающихся множеств, решающих задачу ОБЪЕДИНИТЬ - НАЙТИ, имеет сложность 0 ( та ( т п)), где а ( иг, и) - очень медленно растущая функция, обратная функции Аккермана. Аналогичное утверждение справедливо и для алгоритма построения по уграфу дерева обязательного предшествования ( см. теорему 14), в котором также встречается подзадача ОБЪЕДИНИТЬ - НАЙТИ. [39]
Немедленно возникает вопрос, можно ли найти алгоритм, обеспечивающий гарантированную линейную производительность. Существует множество способов дальнейшего совершенствования алгоритма взвешенного быстрого объединения. В идеале было бы желательно, чтобы каждый узел указывал непосредственно на корень своего дерева, но за это не хотелось бы расплачиваться изменением большого количества указателей, как это делалось в случае алгоритма быстрого объединения. К идеалу можно приблизиться, просто делая все проверяемые узлы указывающими на корень. На первый взгляд этот шаг кажется весьма радикальным, но его легко реализовать, а в структуре этих деревьев нет ничего неприкосновенного: если их можно изменить, чтобы сделать алгоритм более эффективным, это следует сделать. Этот метод, названный сжатием пути ( path compression), можно легко реализовать, добавляя еще один проход по каждому пути во время выполнения операции union и устанавливая запись id, соответствующую каждой встреченной вершине, указывающей на корень. [40]
 |
Алгоритм построения остовного дерева наименьшей стоимости. [41] |
Ребра ( v, w) рассматриваются по очереди. Если v и w принадлежат одному и тому же множеству из VS, то ребро ( v, w) исключается из рассмотрения. Если v и w принадлежат разным множествам Wi и W2 ( это означает, что Wi и Wa еще не соединены), то сливаем их в одно множество и добавляем ( v, w) к множеству Т ребер, входящих в окончательное остовное дерево. Здесь можно воспользоваться алгоритмом объединения непересекающихся множеств, описанным в разд. [42]
Страницы: 1 2 3