Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Машинный расчет по Алгоритму Прима ⇐ ПредыдущаяСтр 3 из 3
Рис. 5.7 (а)
Рис. 5.7 (б)
Рис. 5.7 (в)
Рис. 5.7 (г)
Рис. 5.7 (д)
Рис. 5.7 (е)
В результате машинного расчета решения будут выбраны элементы , , , , и суммарная длина ребер при этом равна 43 (см. рис. 5.7, а-е). Выводы: Оба рассмотренных алгоритма позволяют при выполнении соот-ветствующих условий находить глобально-оптимальные или близкие к ним решения. При этом для работы алгоритма Краскала требуется n (n-1)/2 памяти ЭВМ для записи исходных данных, однако в процессе работы необходимо дополни-тельное время для проверки ребер на образование циклов. Для работы алгоритма Прима памяти необходимо n2, но зато отсутствует необходимость проверки ребер на образование циклов. Следовательно, алгоритм Краскала требует в два с лишним раза меньше памяти, чем алгоритм Прима; зато машинного времени меньше необходимо при расчёте по алгоритму Прима. Кроме этого надо отметить, что алгоритм Краскала более прост при реализации.
|
||
Последнее изменение этой страницы: 2018-04-12; просмотров: 173. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |