Cтраница 1
Жадный алгоритм требует предварительной сортировки ребер по их весам. [1]
Жадный алгоритм может быть выполнен в два этапа. Сначала ребра сортируются по весу и затем строится остовное дерево путем выбора наименьших из имеющихся в распоряжении ребер. Время, требуемое для сортировки Е ребер, равно 0 ( E og E) ( гл. Используя эффективные алгоритмы на множествах из разд. [2]
Жадный алгоритм - это оптимизационный алгоритм, который основан на жадной стратегии. Он просматривает серию альтернатив, выбирая лучшее решение. [3]
Жадный алгоритм построения минимального остовного дерева непригоден для поиска кратчайшего пути между двумя вершинами, поскольку на каждом проходе он учитывает длину лишь одного ребра. Если же изменить его так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего в целом пути из начальной вершины, то мы получим требуемый результат. [4]
Применяя жадный алгоритм ( см. § 5.4), можно сформировать подмножество Т С Е, являющееся базой с наибольшим весом. [5]
Справедливость жадного алгоритма является следствием следующих двух лемм. [6]
Кроме жадного алгоритма из разд. [7]
Таким образом, жадный алгоритм отбирает такое множество S, в котором г-й по величине элемент не меньше г-го по величине элемента произвольной базы. [8]
S, найденное жадным алгоритмом, является независимым множеством с наибольшим весом. [9]
Этот процесс известен как жадный алгоритм. [10]
Легко видеть, что жадный алгоритм конечен. Минимальность результирующего дерева Т не так очевидна, но это можно доказать следующим образом. Предположим, что Т не является минимумом остовных деревьев. Ясно, что С 1, и так как Т не является минимумом остовных деревьев, то и. [11]
Возникает вопрос: всегда ли жадный алгоритм правильно находит подмножество S Е J с наибольшим весом. Оказывается, так происходит тогда, когда пара М ( Е, J) является матроидом. [12]
Приближенный алгоритм упаковки рюкзака представляет собой простой жадный алгоритм, выбирающий наилучшее отношение стоимости к размеру. [13]
В намеченной выше модели матроидных алгоритмов жадный алгоритм, обеспечивающий отыскание независимого множества с максимальным весом, может быть реализован за время nlog n, где п - число вершин в матроиде. Более Трудные задачи, например такие, как отыскание наибольшего общего независимого множества в двух матроидах, тоже могут быть решены за время, полиномиальное относительно количества элементов в этих двух матроидах. [14]
В этом алгоритме, являющемся вариантом жадного алгоритма для матроида M ( G), мы строим стягивающий лес графа G, шаг за шагом добавляя последовательно к S ребра, не вызывающие замыкания цикла. РАЗБ содержит разбиение множества V на множества вершин компонент связности графа, определяемого текущим содержанием множества S. Ребро ei, анализируемое в строке 5, добавляем к S тогда и только тогда, когда оно имеет оба конца в различных блоках разбиения РАЗБ, в противном случае его добавление вызвало бы образование цикла. После добавления ei к S следует заменить блоки А, В е РАЗБ, содержащие концы ребер et, их суммой A ( J В. [15]