Презентация Основы программирования. Пути на графах онлайн

Содержание слайда: Основы программирования Пути на графах

Содержание слайда: Поиск кратчайших путей в графе Пусть – взвешенный ориентированный граф с матрицей весов дуг , если . Если в графе существует некоторый путь, проходящий через вершины , то его весом является величина . Если существует несколько различных путей из в , то можно сформулировать задачу поиска кратчайшего (минимального по весу) пути. 3 варианта задачи поиска кратчайших путей в графе: кратчайший путь между парой вершин и , кратчайшие пути из одной вершины во все остальные, кратчайшие пути между всеми парами вершин.

Содержание слайда: Алгоритм Дейкстры Алгоритм Дейкстры позволяет найти кратчайшие пути из одной вершины-источника во все остальные вершины взвешенного ориентированного графа. Вес кратчайшего пути из в будем обозначать . Пусть кратчайший путь проходит через вершины , тогда (это можно легко доказать от противного). Следовательно, для задачи поиска кратчайшего пути выполняется свойство оптимальности подзадач.

Содержание слайда: Алгоритм Дейкстры Пусть для некоторого мн-ва вершин (старых) найдены кратчайшие пути из с весами ( никогда не пусто, т.к. ). Для остальных вершин (новых) проверка пока не завершена, но определены текущие значения длин путей: , т.е. соответствующий путь проходит только через старые вершины. При начальные значения . Если в графе еще не найдены пути из в , проходящие только через старые вершины, то .

Содержание слайда: Алгоритм Дейкстры Выберем ) и соответствующую вершину . По условию выбора, любой путь, проходящий из в через произвольную новую вершину , не может иметь вес, меньший чем (вес такого пути ). Поэтому (т.е. текущий путь является кратчайшим), и вершину можно включать во множество старых вершин. После этого необходимо скорректировать текущие длины путей для оставшихся новых вершин : .

Содержание слайда: Алгоритм Дейкстры Процесс поиска кратчайших путей продолжается, пока все вершины графа не станут старыми. Поиск можно прекратить, если на некотором шаге все – это означает, что оставшиеся новые вершины недостижимы из источника .  , т.е. для каждой новой вершины на каждом шаге определена старая вершина – предыдущая в пути. Сохраняя ссылки на предыдущие вершины, можно получать не только веса путей , но и соответствующие им последовательности пройденных вершин графа.

Содержание слайда: Алгоритм Дейкстры Для добавления к вершины производится локально оптимальный выбор : , не закрывающий путь к оптимальному решению для остальных новых вершин. Таким образом, выполнены условия, позволяющие реализовать эффективный жадный алгоритм поиска всех кратчайших путей из одной вершины-источника. Приведенный ниже метод minpath реализует алгоритм Дейкстры. Он получает в качестве параметров и формирует массивы, которые должны быть выделены заранее: double D[vernum] – текущие/кратчайшие веса путей из источника s, int P[vernum] – номера предыдущих вершин в пути.

Содержание слайда: Методы WGraph для алгоритма Дейкстры void WGraph::minpath(int s, double *D, int *P) { int i, j, w; double wmin; bool *old = new bool[vernum]; for (i = 0; i < vernum; i++) { old[i] = false; D[i] = mat[s][i]; P[i]=s; } old[s] = true; D[s] = 0; for (i = 1; i < vernum; i++) { for (w=-1, wmin=MAX, j=0; j<vernum; j++) if (!old[j] && D[j] < wmin) { w = j; wmin = D[j]; } if (w < 0) break; for (old[w] = true, j = 0; j < vernum; j++) if (!old[j] && D[j] > D[w]+mat[w][j]) { D[j] = D[w]+mat[w][j]; P[j] = w; } } delete [] old; }

Содержание слайда: Выделение кратчайшего пути Оптимальный (кратчайший) путь в вершину проходит через вершины, для которых оптимальный путь был найден раньше (т.е. ставшие старыми раньше, чем ). Для каждой вершины существует одна ссылка на непосредственного предка в оптимальном пути – по данным ссылкам можно отследить весь оптимальный путь (назад, вплоть до источника). Если после выполнения minpath для вершины v выполняется D[v]=MAX, то v недостижима из s. В противном случае нужно переходить по ссылкам P[v], пока мы не придем в s (P[s]=s). Трудоемкость алгоритма Дейкстры составляет .

Содержание слайда: Вычисление кратчайших расстояний от вершины s до всех остальных Матрица расстояний в общем случае несимметричная s=0 + вершина 3: D + вершина 2: D + вершина 1: D

Содержание слайда: Вычисление кратчайших расстояний от вершины s до всех остальных Матрица расстояний: s=0 Кратчайшие расстояния от вершины 0: D Кратчайшие пути от вершины 0 в обратном порядке: P

Содержание слайда: Алгоритм Флойда-Уоршалла Ищет веса кратчайших путей между всеми парами вершин. Для ориентированного (в общем случае) графа задана матрица весов дуг , если . Рассмотрим последовательность матриц , элементы которых определяются рекуррентно: – это вес пути из в , в котором в качестве промежуточных могут использоваться только вершины из множества , которые могут следовать в произвольном порядке и не обязательно все (число дуг в пути ).

Содержание слайда: Алгоритм Флойда-Уоршалла Докажем, что – вес кратчайшего пути из в при заданных ограничениях на промежуточные вершины (по матиндукции): 1. Базис – очевидно. 2. Пусть – это вес кратчайшего пути из в , проходящего только через вершины (зеленые). На следующем шаге кратчайший путь либо останется прежним ( ), либо обязательно пройдет через вершину (если ).

Содержание слайда: Алгоритм Флойда-Уоршалла При включении вершины на путях из в и из в не может быть совпадающих промежуточных вершин (в противном случае последнее неравенство не выполняется). Следовательно, - это действительно вес кратчайшего пути, проходящего только через вершины из множества . Таким образом, значения - это искомые веса кратчайших путей.

Содержание слайда: Алгоритм Флойда-Уоршалла Вычисляется матрица весов всех кратчайших путей. double** WGraph::allminpath() { int i, j, l; double **W = new double* [vernum]; for (i = 0; i < vernum; i++) W[i] = new double[vernum]; for (i = 0; i < vernum; i++) for (j = 0; j < vernum; j++) W[i][j] = mat[i][[j]; for (l = 0; l < vernum; l++) for (i = 0; i < vernum; i++) { if (W[i][l] < MAX) for (j = 0; j < vernum; j++) W[i][j]=min(W[i][j], W[i][l]+W[l][j]); return W; }

Содержание слайда: Замечания к алгоритму Флойда-Уоршалла Алгоритм Флойда-Уоршалла –пример использования динамического программирования. Условия, при которых применимо ДП: оптимизационная задача, для которой выполняется свойство оптимальности для подзадач; относительно небольшое (полиномиальное от длины входа) число различных подзадач; многократное решение одних и тех же подзадач при поиске общего решения на основе полного перебора вариантов – перекрывающиеся подзадачи.

Содержание слайда: Замечания к алгоритму Флойда-Уоршалла Порядок решения задачи с помощью ДП: описать структуру оптимальных решений задачи и подзадач; найти рекуррентное соотношение, связывающее оптимальные параметры\решения подзадач разных уровней; двигаясь снизу вверх, от подзадач самого низкого уровня, вычислять их оптимальные параметры\решения только один раз и сохранять результаты в специальной таблице; использовать данные из таблицы при поиске оптимального параметра\решения подзадач следующего уровня. В приведенном алгоритме allminpath оптимальные решения подзадач разных уровней последовательно вычисляются в матрице W.

Содержание слайда: Эйлеровы циклы и пути Эйлеров цикл в неориентированном графе: начинается в произвольной вершине a проходит по всем ребрам графа по одному разу завершается в вершине a. Условия существования эйлерова цикла: граф является связным степени всех вершин графа (число инцидентных ребер) четные (т.е. если существует ребро, по которому можно прийти в вершину, то всегда найдется ребро, по которому можно выйти). Если в графе существуют ровно 2 вершины a и b с нечетными степенями, то можно найти эйлеров путь, который начинается в a, проходит по всем ребрам по одному разу и заканчивается в b.

Содержание слайда: Идея алгоритма построения цикла/пути Вычисляются степени всех вершин. Если условия существования цикла/пути не выполняются, то выход. Выбирается произвольная вершина a (для цикла) или выделяются 2 вершины с нечетными степенями a и b (для пути). Строится произвольный начальный (текущий) цикл из a или путь из a в b. Для всех вершин v текущего цикла/пути (начиная с v=a) проверяется, есть ли еще не пройденные ребра, инцидентные v. Если есть, то выделяется побочный цикл, который начинается и заканчивается в v и проходит по не проверенным ранее ребрам. Далее побочный цикл включается в текущий непосредственно за вершиной v.

Содержание слайда: Замечания по алгоритму Текущий путь и побочные циклы выгодно строить в виде списков. Используем для этого класс List из раздела «Линейные списки». Элементы списков будут хранить номера пройденных вершин. Для представления графа используем класс LGraph (списки смежных вершин). Для исключения пройденных ребер можно просто удалять элементы в списках смежных вершин. Чтобы сохранить исходный массив списков lst, следует создать и модифицировать его копию, но для упрощения алгоритма мы используем сам lst. Для вставки побочного цикла в текущий (вставки списка в список с заданной позиции) добавим в класс List новый метод insert(List &sec).

Содержание слайда: Вставка побочного цикла в текущий

Содержание слайда: Вставка списка в список Вставка списка sec после текущего элемента (текущая позиция pcurpos не изменяется): bool List::insert(List &sec) { if (!pcurpos || sec.is_empty()) return false; (sec.pend)->next = pcurpos->next; if (pcurpos == pend) pend = sec.pend; pcurpos->next = sec.pbeg; sec.pend = sec.pbeg = NULL; return true; } bool List::is_empty() { return (!pbeg)? true : false; }

Содержание слайда: Вспомогательные методы Проверка существования эйлерова цикла/пути и расчет начальной и конечной вершины (a и b, для цикла a=b=0). bool LGraph::is_euler_path(int &a, int &b) { int i, k = 0; for (i = 0; i < vernum; i++) if (lst[i].getcount() % 2 == 1) { k++; if (k == 1) a = i; else if (k == 2) b = i; else return false; } if (!k) a = b = 0; return true; }

Содержание слайда: Вспомогательные методы Выделение произвольного пути из a в b (a=b в случае цикла) с исключением просмотренных ребер. Путь формируется в виде списка пройденных вершин path. void LGraph::get_path(int a, int b, List &path) { int i, vpre = a, vnex; path.clear(); path.push_back(a); while (true) { vnex = lst[vpre].pop_front(); lst[vnex].remove(vpre); path.push_back(vnex); if (vnex == b) break; vpre = vnex; } }

Содержание слайда: Выделение эйлерова цикла/пути Цикл/путь формируется в виде списка пройденных вершин. List LGraph::get_euler_path() { List curpath, secpath; int beg, end, *pver; if (!is_euler_path(beg, end)) return curpath; get_path(beg, end, curpath); pver = curpath.get_first(); while (true) { if (lst[*pver].is_empty()) { pver = curpath.get_next(); if (pver == NULL) return curpath; continue; } get_path(*pver, *pver, secpath); secpath.pop_front(); curpath.insert(secpath); } }