ВОПРОСЫ и ответы К ЭКЗАМЕНУ. Ответы к экзамену комбинаторный признак умножения. Количество битовых строк длины
 Скачать 2.8 Mb.
|
Взвешенные графыВ классических графах все рёбра считаются равноценными и длина пути соответствуетколичествурёбер, которые он содержит. Однако часто в задаче каждому ребру соответствует некоторый параметр -длинаребра илистоимостьпрохождения по нему. В терминологии графов такой параметр называетсявесомребра, а граф, содержащий взвешенные рёбра,взвешенным.  Типичная задача для таких графов - поиск кратчайшего пути. Например, в этом графе кратчайший путь между вершинами11и55:1−4−3−51−4−3−5, так как его вес равен30+20+10=6030+20+10=60, а вес ребра1−51−5равен100100. Классический алгоритм для поиска кратчайших путей во взвешенном графе - алгоритм Дейкстры (по имени автора Эдгара Дейкстры). Он позволяет найти кратчайший путь от одной вершины графа до всех остальных заO(MlogN)�(�log�)(N,M�,�- количество вершин и рёбер соответственно). Принцип работы алгоритма напоминает принцип работы BFS: на каждом шаге обрабатывается ближайшая ещё не обработанная вершина (расстояние до неё уже известно). При её обработке все ещё не посещённые соседи добавляются в очередь для посещения (расстояние до каждой из них рассчитывается как расстояние до текущей вершины + длина ребра). Главное отличие от BFS заключается в том, что вместо классической очереди используется очередь с приоритетом. Она позволяет нам выбирать ближайшую вершину заO(logN)�(log�). Анимация выполнения алгоритма Дейкстры для поиска кратчайшего пути из вершиныa�в вершинуb�: С помощью псевдокода алгоритм Дейкстры описывается следующим образом: ans = массив расстояний от начальной вершины до каждой. изначально заполнен бесконечностями (ещё не достигнута). ans[start] = 0 q = очередь с приоритетом, хранящая пары (v, dst), где dst - предполагаемое расстояние до v добавить (start, 0) в q пока q не пуста: (v, dst) = первая вершина в очереди (с минимальным расстоянием), и расстояние до неё извлечь (v, dst) из очереди если ans[v] < dst: //мы уже обработали эту вершину, используя другой путь перейти к следующей вершине для каждой v -> u: n_dst = dst + len(v -> u) //расстояние до u при прохождении через v если n_dst < ans[u]: //если мы можем улучшить ответ ans[u] = n_dst добавить (u, n_dst) в q Как видите, в очереди с приоритетом хранится не только номер вершины, но и вычисленное расстояние до неё, по которому и ведётся сортировка. Также возможна ситуация, при которой одна и та же вершина будет помещена в очередь несколько раз с разным расстоянием (так как она достижима по нескольким рёбрам). В такой ситуации обрабатываем её только один раз (с минимальным возможным расстоянием). 57. Первый алгоритм Флойда-Уоршолла. Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать. Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным. РемаркаЕсли граф не содержит рёбер с отрицательным весом, то для решения этой проблемы можно использовать алгоритм Дейкстры для нахождения кратчайшего пути от одной вершины до всех остальных, запустив его на каждой вершине. Время работы такого алгоритма зависит от типа данных, который мы будем использовать для алгоритма Дейкстры, это может быть как простая очередь с приоритетом, так и бинарная или фибоначчиева Куча, соответственно время работы будет варьироваться от O(V3) до O(V*E*log(V)), где V количество вершин, а E — рёбер. («О»-большое). Если же есть рёбера с отрицательным весом, можно использовать алгоритм Беллмана — Форда. Но этот алгоритм, запущенный на всех вершинах графа, медленнее, время его работы O(V2*E), а в сильно «густых» графах аж O(V4). 58. Условия для графа быть деревом. Граф называется деревом, если он связный и не имеет циклов. Дерево — это связный ациклический граф.[1] Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь. 59. Условия для графа быть корневым ориентированным деревом. Корневое ориентированное дерево — это ориентированное дерево, в котором выделена одна вершина — корень (будем обозначать его ) так, что все вершины графа можно достичь из , двигаясь по ориентированным рёбрам.  60. Теоремы о m-арных ориентированных деревьях. В теория графов, м-арное дерево (также известен как k-ари или же k-путь дерево) является укорененным дерево в котором каждый узел имеет не более м дети. А двоичное дерево это частный случай, когдам = 2, а тройное дерево другой случай с м = 3 это ограничивает количество его детей тремя. А полныйм-арное дерево является м-арное дерево, где на каждом уровне каждый узел имеет либо 0, либо м дети.А полныйм-арное дерево является м-арное дерево, максимально занимающее пространство. Он должен быть полностью заполнен на всех уровнях, кроме последнего. Однако, если последний уровень не завершен, все узлы дерева должны быть «как можно дальше слева».[1] А идеальном-арное дерево это полный[1]м-арное дерево, в котором все листовые узлы находятся на одной глубине.[2] М-арным назовем дерево у которого каждый из узлов кроме листьев содержит не более М деталей Если количество равно М то М-арное дерево будем называть полным. Специальным случаем М-арног8о дерева является бинарное у которого М=2 несложно получить формулу для количество узлов полного М-арного дерева h:  |