Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов




НазваниеБудем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов
Дата конвертации17.07.2013
Размер445 b.
ТипПрезентации



Будем рассматривать задачу в терминах ориентированных графов.

  • Будем рассматривать задачу в терминах ориентированных графов.

  • Граф – конечное множество V, называемое множеством вершин, на котором задано симметричное антирефлексивное отношение R и выделено множество E двухэлементных подмножеств V, определяемое как {a,b}€ E тогда и только тогда, когда (a,b) € R и a ≠ b, и (b,a) не входит в Е.

  • Вес – параметр дуги, длина дуги.

  • Путь – сумма длин входящих в него дуг.

  • Полустепенью исхода(захода) называется число исходящих (входящих) дуг.

  • Две вершины – смежные, если они соединены дугой.

  • Длина пути(во взвешенном графе) – ∑ весов дуг графа.

  • Цикл – путь, который начинается и заканчивается в одной той же вершине и содержит как минимум 1 дугу.

  • Ациклическим считается граф, не содержащий ни одного цикла.

  • В разреженном графе m<

  • Иначе , m=c*n, где с – константа, с≤4.

  • В насыщенном графе m≈n2 или

  • m ≈ c*n2 , где с – константа, с<1.



Библиотека содержит пять основных видов компонентов: * алгоритм (algorithm): определяет вычислительную процедуру. * контейнер (container): управляет набором объектов в памяти. * итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера. * функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами. * адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

  • Библиотека содержит пять основных видов компонентов: * алгоритм (algorithm): определяет вычислительную процедуру. * контейнер (container): управляет набором объектов в памяти. * итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера. * функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами. * адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.



Матрица смежности(vector >)

  • Матрица смежности(vector >)

    • для насыщенного графа
    • Структура смежности(vector< list > )
      • Для разреженного графа
  • Представление в форме map

    • Для представления при входе




Если граф взвешенный:

  • Если граф взвешенный:

    • Представление графа в виде массива дуг с помощью STL map.
    • Дуге(из 2-х вершин) сопоставляется её вес.
    • Пример: представление визуальное и в форме map


Если граф насыщенный:

  • Если граф насыщенный:

    • Используется двумерная матрица смежности A.
    • Для дуги (vi,wj) с весом ci,j
  • A[i][j] = ci,j

    • Несуществующие дуги – значение «бесконечность»
    • В STL представляется как vector >


Если граф разреженный и связный:

  • Если граф разреженный и связный:

    • Используется структура смежности:
    • массив списков.
    • vector< list >




typedef pair vertex;

  • typedef pair vertex;

  • typedef multimap::iterator edgesIt;

  • vector vertices;

  • multimap edges;

  • deque q;

  • while(1)

  • { current = q.front();

  • q.pop_front();

  • vector::iterator vIt = find(vertices.begin(), vertices.end(), vertex(current.first, current.second));

  • (*vIt).second = true;

  • cout << "Visited: " << (*vIt).first << endl;

  • pair rangeIt = edges.equal_range(current.first);

  • for(edgesIt eIt = rangeIt.first; eIt != rangeIt.second; eIt++)

  • { if((find(vertices.begin(), vertices.end(), vertex((*eIt).second, true)) == vertices.end()) && (find(q.begin(), q.end(), vertex((*eIt).second, false)) == q.end())) { push_back(vertex((*eIt).second, false)); cout << "To deque: " << (*eIt).second << endl;

  • } }

  • if(q.empty()) break;

  • } cout << "End." << endl;

  • return EXIT_SUCCESS;}



Алгоритм:

  • Алгоритм:

  • Выбираем непройденную вершину

  • Выбираем 1 из непройденных смежных вершин

  • Если нет смежных непройденных вершин, то помечаем вершину пройденной и возвращаемся в запомненную вершину.



Рекурсивная реализация:

  • Рекурсивная реализация:

    • vector < vector > g; // граф
    • int n; // число вершин
    • vector used;
    • void dfs (int v)
    • { used[v] = true;
    • for (vector::iterator i=g[v].begin(); i!=g[v].end(); ++i)
    • if (!used[*i]) dfs (*i);
    • }




Алгоритм:

  • Алгоритм:

    • Если – длина дуги (i,j).
  • Шаг 0. Помечаем нулевую вершину индексом 0

  • Шаг i. Помечаем вершину i индексом λi = min(λi+ λij).





Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

  • Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.





Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

  • Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

  • Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

  • Следующий сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<, устанавливаем метку вершины 4 равной 22.





priority_queue, Cheapest> candidates;

  • priority_queue, Cheapest> candidates;

  • while(1) {

  • for(list::iterator p = outgoing_services[from].begin(); p!=outgoing_services[from].end();p++){

  • int b = cities[from]->total_distance+(*p)->distance;

  • int c = cities[from]->from_city;

  • if(cities[from]->visited==false){

  • if(cities[(*p)->destination]->total_fee==0)

  • { cities[(*p)->destination]->total_fee = a;

  • cities[(*p)->destination]->total_distance = b;

  • cities[(*p)->destination]->from_city = c; }

  • else if(cities[(*p)->destination]->total_fee>a) { cities[(*p)->destination]->total_fee=a;

  • cities[(*p)->destination]->total_distance = b;

  • cities[(*p)->destination]->from_city = from; }

  • candidates.push(cities[(*p)->destination]); }}

  • cities[from]->visited = true;

  • if (cities[to]->visited) {

  • return pair(cities[to]->total_fee, cities[to]->total_distance);}

      • Else { return pair(INT_MAX, INT_MAX); } }


Алгоритм Дейкстры - только в графе с положительными весами дуг.

  • Алгоритм Дейкстры - только в графе с положительными весами дуг.

    • Для графа с отрицательными весами :
      • как поступать с циклом с отрицательным весом?
      • он делает большинство путей неопределными.
  • Так, путь от V2 до V5 не определён, потому что можно попасть в петлю V3-V4-V1.



Аналогична реализации алгоритма Дейкстры

  • Аналогична реализации алгоритма Дейкстры

  • Отличие:

    • If (элемент есть в очереди)
    • then она не включается повторно.
  • КОД.

  • If(find(candidates.begin(), candidates.end(), cities[(*p)->destination)==candidates.end())

  • candidates.push(cities[(*p)->destination]



Задача поиска кратчайшего пути связана с топологической сортировкой.

  • Задача поиска кратчайшего пути связана с топологической сортировкой.

  • Топологическая сортировка упорядочивает вершины в направленном ациклическом графе так, что

    • If (имеется путь из u в v)
    • then {v появляется после u в очерёдности.}
  • Она невозможна, если граф имеет хотя бы 1 цикл.

  • Описание:

    • Находится вершина, не имеющая входных дуг. Она и все исходящие из неё дуги удаляются из графа.


Все непройденные вершины с полустепенью захода 0 добавляются в очередь.

  • Все непройденные вершины с полустепенью захода 0 добавляются в очередь.

  • Чтобы получить следующую вершину, мы извлекаем первый элемент из очереди.

  • Когда полустепень захода элемента понижается до 0, он помещается в очередь



vector < vector > g; // граф

  • vector < vector > g; // граф

  • int n; // число вершин

  • vector used;

  • vector ans;

  • void dfs (int v) // процедура пометки непройденных вершин

  • { used[v] = true;

  • for (vector::itetator i=g[v].begin(); i!=g[v].end(); ++i)

  • if (!used[*i]) dfs (*i);

  • ans.push_back (v); }

  • void topological_sort (vector & result)// сама сортировка

  • { used.assign (n, false);

  • for (int i=0; i

  • if (!used[i]) dfs (i);

  • result = ans; }



Data Structures and Problem Solving with C++ [2nd Ed] [M. A. Weiss] [Addison Wesley]

  • Data Structures and Problem Solving with C++ [2nd Ed] [M. A. Weiss] [Addison Wesley]

  • Полный справочник по С++, Г.Шилдт

  • http://www.rsdn.ru/

  • http://e-maxx.ru/algo/

  • Дж. А. Андерсон, Дискретная математика и комбинаторика, М:2004.



Похожие:

Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconМышление о мышлении над деятельностью
Триз в «Самсунге». Хронология первых шагов Представители «Заказчика» руководители отделов, подразделений, проектных групп в состоянии...
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconРешение задач части в (В1, В4) Схема решения практико-ориентированных задач Прочитать задачу, обдумать метод решения Решить задачу
Записать ответ ( он может быть выражен целым числом или десятичной дробью с ограниченным количеством десятичных знаков )
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconУчебный курс, излагающий основные положения теории ориентированных графов, призван привлечь внимание школьников, интересующихся математикой и ее приложениями

Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconЛекция 5 Поиск Задача поиска
Объекты в общем случае будем рассматривать как записи произвольной природы, однако имеющие в своей структуре один и тот же
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconПоиск визуально подобных изображений на основе машинного обучения
С этой точки зрения данную проблему можно рассматривать как задачу из теории распознавания образов, где каждый образ (пара изображений)...
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconЛитература Литература Мельников, О. И. Незнайка в стране графов: Пособие для учащихся / О. И. Мельников. Мн. Бел навука, 2000. 96 с ил
Основным аппаратом исследования послужила теория графов, в частности, теория деревьев, двудольных графов и т д. В качестве дальнейшего...
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconУправление каналами ит-дистрибуции Сергей Багузин Что мы будем обсуждать Место дистрибуции в маркетинг-микс
Бизнес, а не товар. При построении системы продаж через посредников-партнеров, необходимо понимать, как работает их бизнес-модель....
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconИзучить тему решения задач построением графов. Изучить тему решения задач построением графов
Попытаться составить текст задач, решаемых с помощью графов, на примере города Зеленодольска и острова Свияжска
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconЛекции по теории графов. М.: Наука, 1990. 14. Уилсон Р. Дж. Введение в теорию графов. М.: Мир, 1977
Журавлёв Ю. И., Флёров Ю. А. Дискретный анализ. Часть I: Учебное пособие. М.: Мфти, 1999
Будем рассматривать задачу в терминах ориентированных графов. Будем рассматривать задачу в терминах ориентированных графов iconВизуализация информации при помощи графов Введение Апанович З. В
Визуализация графов: история Изображения семейных деревьев из средневековых манускриптов
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница