Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 20, Минимальные остовные деревья. PQi(int N, const vector<keyType> &a, int d = 3)
|
|
public:
PQi(int N, const vector< keyType> & a, int d = 3)
a(a), pq(N+l, 0), qp (N+l, 0), N(0), d(d) { } int empty () const { return N == 0; } void insert (int v)
{ pq[++N] = v; qp[v] = N/ fixUp (N); } int getmin()
{ exch(l, N); fixDown(l, N-l); return pq[N--]; } void lower (int k)
{ fixUp(qp[k]); }
};
Упражнения
о 20.71. [В. Высоцкий] Разработайте реализацию алгоритма, обсуждавшегося в разделе 20.2, который строит дерево MST путем добавления ребер по одному за раз и удаления самых длинных ребер из получающихся при этом циклов (см. упражнение 20.33). Воспользуйтесь представлением леса поддеревьев MST в виде родительских связей. Указание: При обходе путей в деревьях поменяйте направления указателей на обратные.
20.72. Проведите эмпирические тестирования с целью сравнения времени выполнения полученной вами реализации в упражнении 20.71 и времени выполнения алгоритма Крускала на взвешенных графах различного вида (см. упражнения 20.9—20.14). Проверьте, оказывает ли влияние на получаемые результаты рандомизация порядка, в котором проводится анализ ребер.
• 20.73. Опишите, как вы будете искать дерево MST графа настолько большого, что в
основной памяти одновременно могут находиться всего лишь V ребер.
о 20.74. Разработайте реализацию очереди с приоритетами, в которой операции remove the minimum и find the minimum выполняются за постоянное время и в которой время выполнения операции decrease key пропорционально логарифму размера очереди с приоритетами. Сравните полученную реализацию с 4-арными сортирующими деревьями, когда вы используете алгоритм Прима для отыскания дерева MST на разреженных графах, на различных видах взвешенных графов (см. упражнения 20.9-20.14).
20.75. Проведите эмпирические исследования с целью сравнения производительности различных реализаций при использовании алгоритма Прима на различных видах взвешенных графов (см. упражнения 20.9-20.14). Рассмотрите результаты применения d-арных сортирующих деревьев для различных значений d, биномиальных очередей, функции priority_queue из библиотеки STL, сбалансированных деревьев и любых других структур данных, которые, по вашему мнению, могут оказаться эффективными.
20.75. Разработайте реализацию, которая расширяет алгоритм Борувки за счет построения обобщенной очереди, содержащей лес поддеревьев MST. (Применение программы 20.9 соответствует использованию очереди FIFO.) Проведите эксперименты с другими реализациями алгоритма с обобщенными очередями на различных видах взвешенных графах (см. упражнения 20.9-20.14).
• 20.77. Разработайте генератор случайных связных кубических графов (каждая вершина
которого имеет степень 3), ребра которых снабжены случайными весами. Выполните
для этого случая тонкую настройку рассмотренных нами алгоритмов вычисления де
ревьев MST, а затем определите, какой из них обладает наибольшим быстродействи
ем.
Часть 5. Алгоритмы на графах
о 20.78. Для V= 106 начертите кривую отношения верхней границы стоимости алгоритма Прима с d-арным сортирующим деревом к Е как функцию от насыщенности d, для d из диапазона от 1 до 100.
о 20.79. Из таблицы 20.2 следует, что стандартная реализация алгоритма Крускала обладает значительно большим быстродействием, чем реализация с частичным упорядочением на графах с малой насыщенностью. Дайте объяснение этому явлению.
• 20.80. Проведите эмпирические исследования в стиле таблицы 20.2 для случайных полных графов, наделенных весами, подпадающими под распределение Гаусса (см. упражнение 20.18).