Жадные алгоритмы. Лекция 5

допуская, что конечное решение также окажется оптимальным. 

Жадные алгоритмы:
Поиск кратчайшего пути
Алгоритм Дейксты
Алгоритм Флойда
Задача о минимальном покрывающем дереве
Алгоритм Прима
Алгоритм Крускала;
Сжатие информации
Алгоритм Хаффмена

присваивается вес равный бесконечности, а первой вершине – 0.
Шаг 2. Все вершины не выделены.
Шаг 3. Первая вершина объявляется текущей.
Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной.
Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.
Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
Шаг 7. Переход на шаг 4.

vj, vk и заданы расстояния между ними. Если выполняется неравенство (wik + wkj) Шаг 1. Положим k=0.
Начальный граф.
Шаг 2. K=k+1.
Шаг 3. Для всех i≠k, таких, что wik≠∞, и для всех j≠k, таких, что wkj≠∞, введем операцию wij=min[wij, (wik + wkj)]. Проверка на окончание.

Указать кратчайшие пути из 1 вершины в 4, из 2 в 3.

Определить кратчайшее расстояние между любыми двумя вершинами графа на основе алгоритма Флойда.

все вершины графа и являющийся деревом.

Цикломатическое число λ(G) графа G – число ребер, которые необходимо удалить, чтобы граф стал ациклическим (т.е. деревом, если связный и лесом, если несвязный).

Вес остова равен сумме весов всех ребер, составляющих остов.

начальном этапе T представляет собой граф, состоящий из n компонент связности - n изолированных вершин графа, множество ребер ET пусто.
На каждом шаге добавляем в ET новое ребро из E\ET , которое имеет минимальный вес и не образует циклов с ребрами из ET.
Добавляя ребра мы уменьшаем число компонент связности графа T.
Алгоритм продолжаем до тех пор, пока число компонент связности не уменьшится до одной - остова графа G.

дерево T(VT,ET) следующим образом: к множеству ребер уже построенного дерева добавляем ребро минимального веса один конец которого находится в множестве VT, а второй - в множестве V\ VT.

основе алгоритма Крускала. Указать цикломатическое число и вес остова.

В неориентированном графе найти кратчайшее остовное дерево на основе алгоритма Прима. Указать цикломатическое число и вес остова.

присваивается оптимальный префиксный код, основанный на вероятности его появления в тексте.

Префиксные коды – это коды, в которых каждое слово не является префиксом любого другого кодового слова.

Оптимальный префиксные код – это префиксный код, имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа:
определение вероятности появления символов;
нахождение оптимального префиксного кода.
Находят два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x , который имеет вероятность появления, равную сумме вероятностей появления символов a и b .
Используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов.
Код для исходного множества символов получается из кодов замещающих символом путем добавления 0 или 1 перед кодом замещающего символа.

Информационная энтропия — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита.