Разделы презентаций


Основы теории графов.ppt

Содержание

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВГрафом называется тройка  , где  M — непустое конечное множество вершин,  N — конечное множество дуг, соединяющих вершины,  T — отображение из  N  в  M × M, которое сопоставляет каждой дуге упорядоченную пару вершин.

Слайды и текст этой презентации

Слайд 1Основы теории графов
Теория графов изучает математические объекты, описывающие связи между

элементами конечного множества

Основы теории графовТеория графов изучает математические объекты, описывающие связи между элементами конечного множества

Слайд 2ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
Графом называется тройка  , где  
M — непустое конечное

множество вершин,  
N — конечное множество дуг, соединяющих вершины,
 T — отображение

из  N  в  M × M, которое сопоставляет каждой дуге упорядоченную пару вершин. Первая из них называется началом этой дуги, а вторая — концом дуги.

M ={A, B, C, D, E} 
N = {1, 2, 3, 4, 5},
T(1) = (D,A); T(2) = (D,B);
T(3) = (B,C); T(4) = (C,E); T(5) = (E,D);

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВГрафом называется тройка  , где  M — непустое конечное множество вершин,  N — конечное множество дуг, соединяющих

Слайд 3Ребро – неориентированная дуга.
Граф называется неориентированным, если каждая его дуга не

ориентирована, ориентированным (орграфом), если ориентированы все его дуги, смешанным, если есть как

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


ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Ребро – неориентированная дуга. Граф называется неориентированным, если каждая его дуга не ориентирована, ориентированным (орграфом), если ориентированы все его дуги, смешанным,

Слайд 4Наглядное представление
Одному графу можно сопоставить несколько графических представлений.
Изображение призвано

лишь показать, какие пары вершин соединены рёбрами, а какие — нет.

Граф

можно изобразить графически: сопоставить его вершинам точки, а дугам – линии, идущее от начальной вершины к конечной.

ВАЖНО: Форма линии и расположение вершин на рисунке произвольны.


Наглядное представлениеОдному графу можно сопоставить несколько графических представлений. Изображение призвано лишь показать, какие пары вершин соединены рёбрами,

Слайд 5Табличное представление

Табличное представление

Слайд 6СВЯЗНОСТЬ ГРАФА
Маршрутом называется такая конечная или бесконечная последовательность ребер, что каждые

два соседних ребра имеют общую вершину.
Маршрут называется циклическим, если его конечная

вершина совпадает с начальной.
Циклический маршрут называется циклом, если каждое его ребро встречается в нем не более одного раза; вершины могут повторяться и несколько раз.
Две вершины  А и В называются связанными, если существует маршрут с концами  А и В. 
Граф называется связным, если любая пара его вершин связана.


СВЯЗНОСТЬ ГРАФАМаршрутом называется такая конечная или бесконечная последовательность ребер, что каждые два соседних ребра имеют общую вершину.Маршрут называется циклическим,

Слайд 7Цикл Эйлера
Среди таких задач наибольшей известностью пользуется задача о семи кёнигсбергских

мостах: в городе Кёнигсберге в начале XVIII века было семь

мостов. Возник вопрос: возможна ли такая прогулка, в которой путь пройдет по всем мостам, и по каждому мосту ровно один раз.
Этот вопрос был предложен знаменитому Леонарду Эйлеру, и в 1735 г. он эту задачу решил: нельзя.

Долгое время отдельные задачи теории графов появлялись как занимательные задачи, которые легко формулиро-вались, но были почему-то очень трудны для решения.

Цикл ЭйлераСреди таких задач наибольшей известностью пользуется задача о семи кёнигсбергских мостах: в городе Кёнигсберге в начале XVIII

Слайд 8В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин

(к которым ведёт нечётное число рёбер) графа должно быть чётно.

Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Карта из статьи 28-летнего Эйлера в трудах Санкт-Петербургской Академии наук 

Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.

В ходе рассуждений Эйлер пришёл к следующим выводам:Число нечётных вершин (к которым ведёт нечётное число рёбер) графа

Слайд 9Гамильтонов цикл
Гамильтонов путь — маршрут, содержащий каждую вершину графа ровно один раз.


Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

Уильям

Роуэн Гамильтон

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.

Гамильтонов циклГамильтонов путь — маршрут, содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого

Слайд 10ВЗВЕШЕННЫЙ ГРАФ (СЕТЬ)
Сетью называется граф, элементам которого поставлены в соответствие некоторые

параметры (стоимость, расстояние, пропускная способность и т.п.).

Сеть автомобильных дорог

ВЗВЕШЕННЫЙ ГРАФ (СЕТЬ)Сетью называется граф, элементам которого поставлены в соответствие некоторые параметры (стоимость, расстояние, пропускная способность и т.п.).Сеть

Слайд 11Построение остовного дерева
В семь населенных пунктов нужно провести кабельное телевидение.

Определить маршруты прокладки кабелей вдоль существующих дорог, схема которых представлена

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

Слайд 12Математическая постановка
Предположим, что задан связный граф , и каждой его дуге j∈N сопоставлено

некоторое число w(j), называемое весом или длиной этой дуги.
Сумму весов дуг дерева называют весом дерева.


Требуется найти такое основное дерево, у которого вес был бы минимален.
Такое дерево называют минимальным остовным деревом.

Рассмотрим два метода: алгоритм Прима и алгоритм Краскала

Математическая постановкаПредположим, что задан связный граф , и каждой его дуге j∈N сопоставлено некоторое число w(j), называемое весом или длиной этой дуги. Сумму весов

Слайд 13Алгоритм Прима 
 —алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.



Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом

Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э.Дейкстрой в 1959 году.

Суть алгоритма: находим ребро минимального веса и выделяем подмножество V* связывающих его вершин. Для всех вершин выделенного подмножества находим ребро с минимальным весом среди всех ребер, ведущих к вершинам, не входящим пока в подмножество V*. Включаем соответствующую вершину в подмножество V*. И так далее, пока все вершины графа не будут включены в подмножествоV*

Алгоритм Прима  —алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году

Слайд 14Алгоритм Прима
Находим ребро минимального веса (V1, V6 ) = 1.

Вводим эти вершины в множество V*={ V1,V6}.
Выбираем ребро минимального

веса, исходящее из вершин V*: (V1, V4)=3.
Добавляем V4 в V*: V*={V1, V4, V6}

Выбираем ребро минимального веса, смежное с вершинами V*: (V4, V5)=1;
добавляем вершину V5 в V*: V*={V1, V4, V5, V6}
Выбираем ребро минимального веса, смежное с вершинами V*: (V4, V2 ) = 3;
добавляем вершину V2 в V*: V*={V1, V2, V4, V5, V6}.
Выбираем ребро минимального веса, смежное с вершинами V*: (V2 ,V7) = 1; добавляем вершину V7 в V*: V*={V1, V2, V4, V5, V6, V7}.
Выбираем ребро минимального веса, смежное с вершинами V*: (V2, V3 ) = 2; добавляем вершину V3 в V*: V*={V1, V2, V3, V4, V5, V6, V7}.
Неохваченных вершин не осталось.
Длина остовного дерева: L= 1+3+1+3+1+2 = 11

Алгоритм ПримаНаходим ребро минимального веса (V1, V6 ) = 1. Вводим эти вершины в множество V*={ V1,V6}.

Слайд 15Алгоритм Краскала
Алгоритм, более привлекательный в вычислительном отношении, был предложен Джозефом Краскалом в

1957 г.
Алгоритм состоит из двух фаз.


Джозеф Краскал
На подготовительной фазе

все дуги удаляются из дерева и упорядочиваются по возрастанию их весов. В графе остаются только вершины, каждая из которых образует отдельную компоненту связности.
Во второй фазе дуги перебираются в порядке возрастания веса. Если начало и конец очередной дуги принадлежат одной и той же компоненте связности, дуга игнорируется. Если же они лежат в разных компонентах связности. дуга добавляется к графу, а эти две компоненты связности объединяются в одну. Если число компонент связности дойдет до 1, цикл завершается досрочно.

Алгоритм КраскалаАлгоритм, более привлекательный в вычислительном отношении, был предложен Джозефом Краскалом в 1957 г.Алгоритм состоит из двух фаз. Джозеф

Слайд 16Алгоритм Краскала
Находим ребро минимального веса 1: (V1, V6 ) =

1.
Вводим вершины в множество V*={ V1,V6}
Находим ребро веса

1: (V2, V7) = 1.
Вводим вершины в множество V*={ V1,V2,V6,V7}
Находим ребро веса 1: (V4, V5) = 1.
Вводим вершины в множество V*={ V1,V2, V4,V5, V6,V7}
Ребер веса 1 больше нет.
Теперь вводим ребра веса 2, так, чтобы не образовать циклы, но повышать связность графа.
Вводим в дерево ребро веса 2: (V3, V7) = 2.
Вводим вершины в множество V*={ V1,V2, V3, V4,V5, V6,V7}
Ребер веса 2 (не образующих циклов с существующими) больше нет.
Теперь вводим ребра веса 3, так, чтобы не образовать циклы, но повышать связность графа.
Находим ребро веса 3: (V1, V4) = 3.
Находим ребро веса 3: (V4, V7) = 3.
Все вершины включены в дерево. Граф связный.
Вес дерева L = 1+1+1+2+3+3 = 11.
Алгоритм КраскалаНаходим ребро минимального веса 1: (V1, V6 ) = 1. Вводим вершины в множество V*={ V1,V6}

Слайд 17Поиск кратчайшего пути в графе
У нас есть две точки:

начало и конец маршрута. Также у нас есть карта, представляющая

собой большой массив векторов. Мы должны использовать его и рассчитать оптимальный маршрут.

Существует несколько методов поиска кратчайших путей в графе:
алгоритм Дейкстры (поиск кратчайших путей от заданной вершины);
алгоритм Флойда (поиска длин всех кратчайших путей в графе);
алгоритм Данцига.

Поиск кратчайшего пути в графе У нас есть две точки: начало и конец маршрута. Также у нас

Слайд 18Алгоритм Дейкстры
Метод считается одним из наиболее эффективных алгоритмов решения

задачи. Предложен в 1959 г. голландским математиком Дейкстрой (1930-2002), известным,

в частности, своей борьбой против безбрежного использования в программировании оператора go to. Эта борьба привела к существенному улучшению стиля программирования.

Эдсгер Вибе Дейкстра

Главная идея, лежащая в основе алгоритма Дейкстры Предположим, что нам известны m вершин, ближайших к вершине S (близость любой вершины X к вершине S определяется длиной кратчайшего пути, ведущего из S в X). Пусть также известны сами кратчайшие пути, соединяющие вершину S с выделенными m вершинами). Нужно ввести правило, как может быть определена (m+1)-я ближайшая к S вершина.

Алгоритм Дейкстры Метод считается одним из наиболее эффективных алгоритмов решения задачи. Предложен в 1959 г. голландским математиком

Слайд 19Идея алгоритма Дейкстры
Окрасим вершину S и m ближайших к ней

вершин.
Построим для каждой неокрашенной вершины Y пути, непосредственно соединяющие с

помощью дуг (х, у) каждую окрашенную вершину Х с Y.
Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины S в вершину Y.
Какая же из неокрашенных вершин является (m+1)-й ближайшей к S вершиной?
Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины S в (m+1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число m вершин, ближайших к вершине S.
Итак, если известны m ближайших к s вершин, то и (m+1)-я ближайшая к S вершина может быть найдена.
Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины S к вершине T.
Идея алгоритма ДейкстрыОкрасим вершину S и m ближайших к ней вершин.Построим для каждой неокрашенной вершины Y пути,

Слайд 20Алгоритм Дейкстры
Каждой вершине X в ходе алгоритма присваивается число d(x),

равное длине кратчайшего пути из вершины S в вершину X

и включающем только окрашенные вершины.
Положиv d(s)=0 и d(x)=∞ для всех остальных вершин графа.
Окрашиваем вершину S и полагаем Y=S, где Y – последняя окрашенная вершина.
Для каждой неокрашенной вершины X пересчитывается величина d(x) по следующей формуле:
d(x) = min {d(x); d(y)+ ay,x}
5) Если d(x)=∞ для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины S в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина d(x) является минимальной.
Окрашивается и дуга, ведущая в эту вершину, и полагаем Y=X.
6) Если Y=T, кратчайший путь из S в T найден. Иначе переходим к шагу 2.

Алгоритм ДейкстрыКаждой вершине X в ходе алгоритма присваивается число d(x), равное длине кратчайшего пути из вершины S

Слайд 21ПРИМЕР
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех

остальных.

Первый шаг. Минимальную метку имеет вершина 1.
Её соседями являются

вершины 2, 3 и 6.

«Проверим» всех «соседей» вершины 1. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

ПРИМЕРПусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.Первый шаг. Минимальную метку имеет вершина 1.

Слайд 22Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных

вершин. Это вершина 2 с меткой 7.
Пытаемся уменьшить метки соседей

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

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.Пытаемся

Слайд 23Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её

«обработки» получим:
Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это

будут вершины 6, 4 и 5, соответственно порядку.
Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим:Дальнейшие шаги. Повторяем шаг алгоритма для

Слайд 24Алгоритм Флойда - Уоршелла
Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом
В

отличии от алгоритма Дейкстры, который позволяет построить ориентированное дерево кратчайших

путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.
Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры требует значительных вычислительных затрат.

Роберт Флойд

Алгоритм Флойда - УоршеллаРазработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом В отличии от алгоритма Дейкстры, который позволяет построить

Слайд 25Обозначения
Перенумеруем вершины графа целыми числами от 1 до N.

Обозначим

через di,jm длину кратчайшего пути из вершины i в вершину j,

который в качестве промежуточных может содержать только первые m вершин графа (промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами).

Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=∞.

Величина di,j0, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе).
ОбозначенияПеренумеруем вершины графа целыми числами от 1 до N. Обозначим через di,jm длину кратчайшего пути из вершины i

Слайд 26Обозначения
Обозначим через Dm матрицу размера NxN, элемент (i,j) которой совпадает с

di,jm.
Если в исходном графе нам известна длина каждой дуги,

то мы можем сформировать матрицу D0, которая в алгоритме Флойда выступает в качестве исходной.
Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрица D2 и т. д. по формуле:
di,jm = min{ di,mm-1 + dm,jm-1; di,jm-1}
Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.


ОбозначенияОбозначим через Dm матрицу размера NxN, элемент (i,j) которой совпадает с di,jm. Если в исходном графе нам известна

Слайд 27Суть алгоритма Флойда
заключается в проверке того, не окажется ли путь

из вершины i в вершину j короче, если будет проходить

через некоторую промежуточную вершину m.

Пусть есть три вершины – i, j,m – и расстояния между ними: dij, dim, dmj.
Если выполняется неравенство dim + dmj < dij, то целесообразно заменить путь i? j путём i ? m ? j

«Треугольный оператор»

Суть алгоритма Флойдазаключается в проверке того, не окажется ли путь из вершины i в вершину j короче,

Слайд 28Этап 1. Перенумеровать вершины графа от 1 до N, определить

матрицу D0, каждый элемент di,j0 которой есть длина кратчайшей дуги

между вершинами i и j. Если такой дуги нет, положить значение элемента di,j0 = ∞. Значения диагональных элементов di,i = 0.

Алгоритм Флойда на примере

Этап 1. Перенумеровать вершины графа от 1 до N, определить матрицу D0, каждый элемент di,j0 которой есть

Слайд 29Матрицу S0, в которой будем запоминать последовательность вершин в кратчайшем

пути, заполним так: sij = j
Алгоритм Флойда на примере

Матрицу S0, в которой будем запоминать последовательность вершин в кратчайшем пути, заполним так: sij = jАлгоритм Флойда

Слайд 30Алгоритм Флойда на примере
Задаём строку m и столбец m как

ведущую строку и ведущий столбец.
Для всех элементов dij матрицы Dm-1

рассматриваем возможность применения треугольного оператора. Если выполняется неравенство:
dim + dmj < dij (i≠j, j≠m, i≠m),
то делаем следующее:
а) в матрице Dm заменяем элемент dij матрицы Dm-1 суммой dim + dmj;
b) в матрице Sm меняем элемент sij матрицы Sm-1 на m;
c) полагаем m=m+1, повторяем основной этап, пока m < N

Основной этап

Алгоритм Флойда на примереЗадаём строку m и столбец m как ведущую строку и ведущий столбец.Для всех элементов

Слайд 31Алгоритм Флойда на примере


Алгоритм Флойда на примере

Слайд 32Алгоритм Флойда на примере


Алгоритм Флойда на примере

Слайд 33Алгоритм Флойда на примере


Алгоритм Флойда на примере

Слайд 34Алгоритм Флойда на примере


Алгоритм Флойда на примере

Слайд 35Алгоритм Флойда на примере


Алгоритм Флойда на примере

Слайд 36Алгоритм Флойда на примере


Алгоритм Флойда на примере

Слайд 37Алгоритм Флойда на примере
Последний этап.
После реализации N этапов алгоритма определение

по матрицам Dn и Sn кратчайшего пути между узлами i

и j выполняется по следующим правилам:

Кратчайшее расстояние между узлами i и j равно элементу dij в матрице Dn.
Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i ? j? k.
Если далее sik = k и skj = j, то считаем, что весь путь определён. В противном случае повторяем процедуру для путей от узла i к узлу k и от узла k к узлу j.
Алгоритм Флойда на примереПоследний этап.После реализации N этапов алгоритма определение по матрицам Dn и Sn кратчайшего пути

Слайд 38d25 = 21
Путь: 2?4 ?5
d51 = 20
Путь: 5?6 ?3 ?

1


Алгоритм Флойда на примере

d25 = 21Путь: 2?4 ?5d51 = 20Путь: 5?6 ?3 ? 1Алгоритм Флойда на примере

Слайд 39Задача коммивояжёра
Формулировка (1934 г.)
Коммивояжер должен выйти из первого города, посетить

по разу в неизвестном порядке города 2, 3, …, n и вернуться

в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

В терминах теории графов задача формулируется так: имеется полный ориентированный граф G = (M, N), каждой дуге (i, j) которого сопоставлен вес dij. Требуется найти в этом графе гамильтонов контур наименьшей стоимости.

Задача коммивояжёраФормулировка (1934 г.)Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,

Слайд 40Идея метода состоит в следующем:
чтобы избежать полного перебора нужно

разделить огромное число перебираемых вариантов на классы и получить оценки

(снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами.

Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Метод ветвей и границ ("поиск с возвратом", "backtracking")

Идея метода состоит в следующем: чтобы избежать полного перебора нужно разделить огромное число перебираемых вариантов на классы

Слайд 41Применительно к задаче о коммивояжере идея метода ветвей и границ

такова:
Ветвление основано на следующем простом соображении: переезд из любого данного

города i в любой другой город j может либо принадлежать оптимальному циклу коммивояжера, либо не принадлежать ему. При вычислении же границ используется тот факт, что изменение длин всех путей, приводящих в данный город, или всех путей, выводящих из данного города, на одну и ту же величину приводит к новой задаче, оптимальный план которой совпадает с оптимальным планом исходной задачи.

Алгоритм Литтла для задачи коммивояжера (Литтла, Мурти, Суини и Кэрел)

Применительно к задаче о коммивояжере идея метода ветвей и границ такова:Ветвление основано на следующем простом соображении: переезд

Слайд 42В каждой строке матрицы стоимости найдем минимальный элемент и вычтем

его из всех элементов строки. Сделаем это и для столбцов,

не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
Для каждого нулевого элемента матрицы dij  рассчитаем коэффициент Гij, который равен сумме наименьшего элемента i строки (исключая элемент dij=0) и наименьшего элемента j столбца. Из всех коэффициентов  Гij выберем такой, который является максимальным Гkl = max{Гij}. В гамильтонов контур вносится соответствующая дуга (k,l).

Алгоритм Литтла

В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это

Слайд 43Удаляем k-тую строку и столбец l, поменяем на бесконечность значение

элемента dlk (поскольку дуга (k,l) включена в контур, то обратный путь

из l в k недопустим).
Повторяем алгоритм c шага 1, пока порядок матрицы не станет равным двум.
Затем в текущий ориентированный граф вносим две недостающие дуги, определяющиеся однозначно матрицей прядка 2. Получаем гамильтонов контур.

Алгоритм Литтла

Удаляем k-тую строку и столбец l, поменяем на бесконечность значение элемента dlk (поскольку дуга (k,l) включена в контур,

Слайд 44В ходе решения ведется постоянный подсчет текущего значения нижней границы.
Нижняя

граница равна сумме всех вычтенных элементов в строках и столбцах.


Итоговое значение нижней границы должно совпасть с длиной результирующего контура (пути).

Алгоритм Литтла

В ходе решения ведется постоянный подсчет текущего значения нижней границы. Нижняя граница равна сумме всех вычтенных элементов в

Слайд 45Матрица кратчайших расстояний, где dii = ∞
Алгоритм Литтла (пример)

Матрица кратчайших расстояний, где dii = ∞Алгоритм Литтла (пример)

Слайд 46Алгоритм Литтла (пример. Шаг 1)

Сумма констант приведения
равна 7+7+2+6+6+2 =

30
Во всех столбцах есть нулевые элементы.
Приводить по столбцам не

нужно
Алгоритм Литтла (пример. Шаг 1)Сумма констант приведения равна 7+7+2+6+6+2 = 30Во всех столбцах есть нулевые элементы. Приводить

Слайд 47Тур, проходящий только через ребра нулевой стоимости, будет, очевидно, минимальным.


Его стоимость 30.


Алгоритм Литтла (пример. Шаг 1)

Таким образом, мы получили

нижнюю оценку стоимости класса всех возможных туров.
То есть минимальный тур в данной задаче
не может стоить меньше, чем 30.

Тур, проходящий только через ребра нулевой стоимости, будет, очевидно, минимальным. Его стоимость 30.Алгоритм Литтла (пример. Шаг 1)Таким

Слайд 48Алгоритм Литтла (пример. Шаг 2)
Назовем оценкой нуля в позиции (i,

j) в матрице сумму минимальных элементов в i-й строке и

j-м столбце (не считая сам этот ноль).
Оценим каждый ноль в приведенной матрице:


max=12

Алгоритм Литтла (пример. Шаг 2)Назовем оценкой нуля в позиции (i, j) в матрице сумму минимальных элементов в

Слайд 49Оценка k нуля, в позиции (i, j) означает буквально следующее:

если в тур не будет включен путь из i в

j (стоимостью 0), то придется доплатить как минимум k. Поэтому, можно разделить класс всех возможных туров на два: туры, содержащие ребро (i, j) и туры, не содержащие его. Для последних минимальная оценка увеличится на k.

Алгоритм Литтла (пример. Шаг 2)

Оценка k нуля, в позиции (i, j) означает буквально следующее: если в тур не будет включен путь

Слайд 50Рассмотрим ребро, соответствующее нулю с максимальной оценкой. В данном случае

это ребро (4, 5). Нижняя оценка стоимости класса туров, не

содержащих (4,5) увеличивается до 30+12=42.
Чтобы определить оценку для класса туров, содержащих дугу (4,5), удалим из матрицы строку 4 и столбец 5. Элемент d54 заменим ∞, чтобы не было замкнутого контура.

Алгоритм Литтла (пример. Шаг 3)


Рассмотрим ребро, соответствующее нулю с максимальной оценкой. В данном случае это ребро (4, 5). Нижняя оценка стоимости

Слайд 51Алгоритм Литтла (пример. Шаг 1)


Сумма констант приведения равна 3 +

8 = 11

Алгоритм Литтла (пример. Шаг 1)Сумма констант приведения равна 3 + 8 = 11

Слайд 52Рассчитываем оценку для каждого нулевого элемента как сумму минимальных по

строке и столбцу
Алгоритм Литтла (пример. Шаг 2)
Дугу (4, 5) включаем

в путь

max=10

Рассчитываем оценку для каждого нулевого элемента как сумму минимальных по строке и столбцуАлгоритм Литтла (пример. Шаг 2)Дугу

Слайд 53Нижняя оценка стоимости класса туров, не содержащих (1,2) увеличивается до

41+10=51.

Чтобы определить оценку для класса туров, содержащих дугу (1,2),

удалим из матрицы строку 1 и столбец 2. Элемент d21 заменим ∞, чтобы не было замкнутого контура.

Алгоритм Литтла (пример. Шаг 3)

Нижняя оценка стоимости класса туров, не содержащих (1,2) увеличивается до 41+10=51. Чтобы определить оценку для класса туров,

Слайд 54Алгоритм Литтла (пример. Шаг 3)

Алгоритм Литтла (пример. Шаг 3)

Слайд 55Приведем матрицу, вычитая минимальные значения по строкам и столбцам.
Алгоритм Литтла

(пример. Шаг 1,2)

Сумма констант приведения
равна 0 + 7 =

7

max=4


Оценим нулевые элементы

Приведем матрицу, вычитая минимальные значения по строкам и столбцам.Алгоритм Литтла (пример. Шаг 1,2)Сумма констант приведения равна 0

Слайд 56Поскольку у двух нулевых элементов (6,3) и (2,4) одинаковые оценки,

то нужно рассмотреть оба варианта.
Алгоритм Литтла (пример. Шаг 1,2)

Поскольку у двух нулевых элементов (6,3) и (2,4) одинаковые оценки, то нужно рассмотреть оба варианта. Алгоритм Литтла

Слайд 57Получаем оценку нулевых элементов
Алгоритм Литтла (пример. Шаг 1,2)
Удаляем 6 строку

и 3 столбец; d36= ∞


В каждой строке и столбце есть

0, поэтому сумма констант приведения равна 0


max=9

Получаем оценку нулевых элементовАлгоритм Литтла (пример. Шаг 1,2)Удаляем 6 строку и 3 столбец; d36= ∞В каждой строке

Слайд 58Осталась матрица 2х2.
Первый путь найден.
Алгоритм Литтла (пример. Шаг 3)
Удалим 5

строку и 6 столбец
Путь: 1 ? 2 ? 4 ?

5 ? 6 ? 3 ? 1.
Длина пути: 48.
Осталась матрица 2х2.Первый путь найден.Алгоритм Литтла (пример. Шаг 3)Удалим 5 строку и 6 столбецПуть: 1 ? 2

Слайд 59Оценки совпадают у трёх нулевых элементов, но все дуги входят

в ранее найденный путь длиной 48
Алгоритм Литтла (пример. Возврат к

слайду 56)

Сумма констант приведения =0

Удалим 2 строку и 4 столбец



Оценки совпадают у трёх нулевых элементов, но все дуги входят в ранее найденный путь длиной 48Алгоритм Литтла

Слайд 60Алгоритм Литтла (оптимальное решение)
Путь: 1 ? 2 ? 4 ?

5 ? 6 ? 3 ? 1.
Длина пути: 48.

Алгоритм Литтла (оптимальное решение)Путь: 1 ? 2 ? 4 ? 5 ? 6 ? 3 ? 1.Длина

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика