Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • B.assign(G.V(), 0) ;






    for (h = 0, N = 0; h < E; h++)

    { Edge *e = a[h];

    i =uf.find(e-> v()), j = uf.find(e-> w())/ if (i == j) continue;

    if <! b[i] || e-> wt() < b[i]-> wt()) b[i] - e; if (! b[j] || e-> wt() < b[j]-> wt()) b[j] m e; a[N++] = e;

    }

    for (h = 0; h < G.V(); h++) if (b[h]) if (! uf.find(i - b[h]-> v(), j = b[h]-> w()))

    { uf.unite(i, j); mst[k++] = b[h]; } } } };


    Свойство 20.11. Время прогона алгоритма Бо­рувки с целью вычисления дерева MTS заданного графа есть O(E lgV lg*E).

    Доказательство: Поскольку число деревьев в лесе уменьшается наполовину на каждом этапе, число этапов непревышает значения lg V. Вре­мя выполнения каждого этапа, самое большее, пропорционально затратам на выполнение Е операций find, что меньше E lg*E, или линейно с точки зрения практических приложений. ■

    Время прогона, оценка которого дается свой­ством 20.11, представляет собой консервативную верхнюю границу, поскольку оно не учитывает су­щественное уменьшение числа ребер на каждом этапе. На выполнение операций find затрачивается постоянное время на ранних проходах, а на пос­ледующих проходах число рассматриваемых ребер существенно уменьшается. В самом деле, для мно­гих графов число ребер уменьшается по экспонен­те от числа вершин, а общее время прогона ока­зывается пропорциональным Е. Например, как показано на рис. 20.16, рассматриваемый алго-


    РИСУНОК 20.15. ПРИМЕНЕНИЕ МАССИВА ПОИСКА-ОБЪЕДИНЕНИЯ В АЛГОРИТМЕ БОРУВКИ

    На данной диаграмме показано содержимое массива поиска-объедине­ния, соответствующего примеру, представленному на рис. 20.14. Первоначально каждый элемент содержит свой собственный индекс, указывающий вершину в лесе изолиро­ванных вершин. В результате выполне­ния первого этапа мы получаем три компоненты, представленные вершина­ми 0, 1 и 3 (в условиях этого крохотного примера деревья, построенные при помощи операций поиска и объединения, лежат в одной плоскости). По оконча­нии второго этапа мы получаем единственную компоненту, которую представляет вершина 1


    Глава 20, Минимальные остовные деревья



     


    ритм отыскивает дерево MTS приводимого нами в качестве примера более крупного графа всего лишь за четыре этапа.

    Можно сдвинуть коэффициент lg*£ в область более низких теоретических границ времени прогона алгоритма Борувки и сделать его пропорциональным E lgV зa счет представления поддеревьев MTS в виде двухсвязных списков вместо исполь­зования операций union и find. Однако это усовершенствование достаточно трудно для реализации и возможное повышение производительности не настолько заметно, чтобы можно было рекомендовать его для применения в практических приложе­ниях (см. упражнения 20.66 и 20.67).

    Как было отмечено выше, алгоритм Борувки — это самый старый алгоритм из числа тех, которые мы рассматриваем: его идея впервые была выдвинута в 1926 г. применительно к при­ложениям по распределению энергии. Этот метод был открыт вторично Соллиным (Sollin) в 1961 г.; несколько позже он привлек к себе внимание как основа для алгоритмов вычис­ления деревьев MTS с эффективной асимптотической произ­водительностью и как основа для параллельного построения деревьев MTS.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.