🗊 Презентация Гамильтоновы циклы

Категория: Математика
Нажмите для полного просмотра!
Гамильтоновы циклы, слайд №1 Гамильтоновы циклы, слайд №2 Гамильтоновы циклы, слайд №3 Гамильтоновы циклы, слайд №4 Гамильтоновы циклы, слайд №5 Гамильтоновы циклы, слайд №6 Гамильтоновы циклы, слайд №7 Гамильтоновы циклы, слайд №8 Гамильтоновы циклы, слайд №9 Гамильтоновы циклы, слайд №10 Гамильтоновы циклы, слайд №11 Гамильтоновы циклы, слайд №12 Гамильтоновы циклы, слайд №13 Гамильтоновы циклы, слайд №14 Гамильтоновы циклы, слайд №15 Гамильтоновы циклы, слайд №16 Гамильтоновы циклы, слайд №17 Гамильтоновы циклы, слайд №18 Гамильтоновы циклы, слайд №19 Гамильтоновы циклы, слайд №20 Гамильтоновы циклы, слайд №21 Гамильтоновы циклы, слайд №22 Гамильтоновы циклы, слайд №23 Гамильтоновы циклы, слайд №24 Гамильтоновы циклы, слайд №25 Гамильтоновы циклы, слайд №26 Гамильтоновы циклы, слайд №27 Гамильтоновы циклы, слайд №28 Гамильтоновы циклы, слайд №29 Гамильтоновы циклы, слайд №30 Гамильтоновы циклы, слайд №31 Гамильтоновы циклы, слайд №32 Гамильтоновы циклы, слайд №33 Гамильтоновы циклы, слайд №34 Гамильтоновы циклы, слайд №35 Гамильтоновы циклы, слайд №36 Гамильтоновы циклы, слайд №37 Гамильтоновы циклы, слайд №38 Гамильтоновы циклы, слайд №39 Гамильтоновы циклы, слайд №40 Гамильтоновы циклы, слайд №41 Гамильтоновы циклы, слайд №42 Гамильтоновы циклы, слайд №43 Гамильтоновы циклы, слайд №44 Гамильтоновы циклы, слайд №45 Гамильтоновы циклы, слайд №46 Гамильтоновы циклы, слайд №47 Гамильтоновы циклы, слайд №48 Гамильтоновы циклы, слайд №49 Гамильтоновы циклы, слайд №50 Гамильтоновы циклы, слайд №51 Гамильтоновы циклы, слайд №52 Гамильтоновы циклы, слайд №53 Гамильтоновы циклы, слайд №54 Гамильтоновы циклы, слайд №55 Гамильтоновы циклы, слайд №56 Гамильтоновы циклы, слайд №57 Гамильтоновы циклы, слайд №58 Гамильтоновы циклы, слайд №59 Гамильтоновы циклы, слайд №60 Гамильтоновы циклы, слайд №61 Гамильтоновы циклы, слайд №62 Гамильтоновы циклы, слайд №63 Гамильтоновы циклы, слайд №64 Гамильтоновы циклы, слайд №65 Гамильтоновы циклы, слайд №66 Гамильтоновы циклы, слайд №67 Гамильтоновы циклы, слайд №68 Гамильтоновы циклы, слайд №69 Гамильтоновы циклы, слайд №70 Гамильтоновы циклы, слайд №71 Гамильтоновы циклы, слайд №72 Гамильтоновы циклы, слайд №73 Гамильтоновы циклы, слайд №74 Гамильтоновы циклы, слайд №75 Гамильтоновы циклы, слайд №76
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Гамильтоновы циклы. Доклад-сообщение содержит 76 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Гамильтоновы циклы Перебор вершин с возвратом
Описание слайда:
Гамильтоновы циклы Перебор вершин с возвратом

Слайд 2


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

Слайд 3


Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе… Не найдено ни одного необходимого и...
Описание слайда:
Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе… Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе…

Слайд 4


Постановка задачи Дан связный неориентированный граф. Найти все гамильтоновы циклы (если они есть).
Описание слайда:
Постановка задачи Дан связный неориентированный граф. Найти все гамильтоновы циклы (если они есть).

Слайд 5


“Простой” способ поиска: Сгенерируем все перестановки вершин графа. Дальше можно просто проверить каждую, не является ли она гамильтоновым циклом....
Описание слайда:
“Простой” способ поиска: Сгенерируем все перестановки вершин графа. Дальше можно просто проверить каждую, не является ли она гамильтоновым циклом. Так ли это просто?

Слайд 6


Рассмотрим пример: Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин?
Описание слайда:
Рассмотрим пример: Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин?

Слайд 7


А если вершин 100? Число перестановок будет равно:...
Описание слайда:
А если вершин 100? Число перестановок будет равно: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ≈ 9.3•10157

Слайд 8


Это не все… Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно затратить еще N операций. Таким образом, “лобовое” решение требует...
Описание слайда:
Это не все… Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно затратить еще N операций. Таким образом, “лобовое” решение требует N•N! операций. Это число растет с ростом N очень быстро…

Слайд 9


Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин...
Описание слайда:
Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин связаны друг с другом. Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин связаны друг с другом. Есть более рациональный алгоритм…

Слайд 10


Структуры данных: Будем использовать два массива целых: Arr[N] – в этом массиве будет находиться последовательность вершин; Nnew[N] – если i-й...
Описание слайда:
Структуры данных: Будем использовать два массива целых: Arr[N] – в этом массиве будет находиться последовательность вершин; Nnew[N] – если i-й элемент этого массива есть 0, значит на текущем шаге i-я вершина графа еще не посещалась. Для задания структуры графа будем использовать матрицу смежности Matr[N][N]

Слайд 11


Алгоритм Будем предполагать, что поиск циклов мы ведем c вершины 1. На очередном шаге в массиве Arr находится последовательность связанных друг с...
Описание слайда:
Алгоритм Будем предполагать, что поиск циклов мы ведем c вершины 1. На очередном шаге в массиве Arr находится последовательность связанных друг с другом вершин, которые, возможно, являются началом гамильтонова цикла.

Слайд 12


Алгоритм Центральной процедурой алгоритма является рекурсивная функция Step. Эта функция принимает один целый параметр – номер шага.
Описание слайда:
Алгоритм Центральной процедурой алгоритма является рекурсивная функция Step. Эта функция принимает один целый параметр – номер шага.

Слайд 13


Алгоритм 1. Функция берет последнюю добавленную в массив Arr вершину, делает ее текущей, и ищет (в цикле по матрице смежности) вершины, связанные с...
Описание слайда:
Алгоритм 1. Функция берет последнюю добавленную в массив Arr вершину, делает ее текущей, и ищет (в цикле по матрице смежности) вершины, связанные с текущей. 2. Если номер шага = N+1, а текущая вершина связана с первой вершиной, то в Arr находится гамильтонов цикл. Его можно вывести, а затем выйти из Step.

Слайд 14


Алгоритм 3. Если найдена вершина, связанная с текущей и еще непосещенная, то: Эта новая вершина добавляется в “хвост” Arr; Новая вершина отмечается...
Описание слайда:
Алгоритм 3. Если найдена вершина, связанная с текущей и еще непосещенная, то: Эта новая вершина добавляется в “хвост” Arr; Новая вершина отмечается как посещенная; Вызывается процедура Step cо значением параметра, увеличенным на 1; После возврата новая вершина вновь отмечается, как непосещенная. 4. Если все вершины, связанные с текущей уже посещались, то осуществляется выход из Step.

Слайд 15


На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. На...
Описание слайда:
На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. Смущает то, что после возврата из функции Step, последняя вершина помечается как непосещённая. Не приведет ли это к зацикливанию?..

Слайд 16


for (j=1; j
Описание слайда:
for (j=1; j

Слайд 17


Рассмотрим граф: Этот граф имеет два гамильтоновых цикла: (1,2,3,4,5) и (1,5,4,2,1)
Описание слайда:
Рассмотрим граф: Этот граф имеет два гамильтоновых цикла: (1,2,3,4,5) и (1,5,4,2,1)

Слайд 18


На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин На желтом поле показывается массив Arr, на зеленом – признаки...
Описание слайда:
На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин

Слайд 19


В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины В прямых скобках показан параметр цикла в соответствующем вызове...
Описание слайда:
В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины

Слайд 20


Гамильтоновы циклы, слайд №20
Описание слайда:

Слайд 21


Гамильтоновы циклы, слайд №21
Описание слайда:

Слайд 22


Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла. Параметр вызова=N+1 и из последней вершины достижима первая –...
Описание слайда:
Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла. Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла.

Слайд 23


Гамильтоновы циклы, слайд №23
Описание слайда:

Слайд 24


Гамильтоновы циклы, слайд №24
Описание слайда:

Слайд 25


Гамильтоновы циклы, слайд №25
Описание слайда:

Слайд 26


Гамильтоновы циклы, слайд №26
Описание слайда:

Слайд 27


Гамильтоновы циклы, слайд №27
Описание слайда:

Слайд 28


Гамильтоновы циклы, слайд №28
Описание слайда:

Слайд 29


Гамильтоновы циклы, слайд №29
Описание слайда:

Слайд 30


Гамильтоновы циклы, слайд №30
Описание слайда:

Слайд 31


Гамильтоновы циклы, слайд №31
Описание слайда:

Слайд 32


Гамильтоновы циклы, слайд №32
Описание слайда:

Слайд 33


Гамильтоновы циклы, слайд №33
Описание слайда:

Слайд 34


Гамильтоновы циклы, слайд №34
Описание слайда:

Слайд 35


Гамильтоновы циклы, слайд №35
Описание слайда:

Слайд 36


Гамильтоновы циклы, слайд №36
Описание слайда:

Слайд 37


Гамильтоновы циклы, слайд №37
Описание слайда:

Слайд 38


Гамильтоновы циклы, слайд №38
Описание слайда:

Слайд 39


Гамильтоновы циклы, слайд №39
Описание слайда:

Слайд 40


Гамильтоновы циклы, слайд №40
Описание слайда:

Слайд 41


Гамильтоновы циклы, слайд №41
Описание слайда:

Слайд 42


Гамильтоновы циклы, слайд №42
Описание слайда:

Слайд 43


Гамильтоновы циклы, слайд №43
Описание слайда:

Слайд 44


Гамильтоновы циклы, слайд №44
Описание слайда:

Слайд 45


Гамильтоновы циклы, слайд №45
Описание слайда:

Слайд 46


Гамильтоновы циклы, слайд №46
Описание слайда:

Слайд 47


Гамильтоновы циклы, слайд №47
Описание слайда:

Слайд 48


Гамильтоновы циклы, слайд №48
Описание слайда:

Слайд 49


Гамильтоновы циклы, слайд №49
Описание слайда:

Слайд 50


Гамильтоновы циклы, слайд №50
Описание слайда:

Слайд 51


Кратчайшие пути в графах
Описание слайда:
Кратчайшие пути в графах

Слайд 52


Постановка задачи Дан ориентированный граф; Каждой дуге приписана “длина” – вес дуги; Веса дуг хранятся в матрице смежности, причем, если i-я и j-я...
Описание слайда:
Постановка задачи Дан ориентированный граф; Каждой дуге приписана “длина” – вес дуги; Веса дуг хранятся в матрице смежности, причем, если i-я и j-я вершины не связаны дугой, то A[i,j]=∞ “Длина” или оценка пути = сумме весов дуг, составляющих путь. Требуется находить пути с минимальной оценкой (т.е. кратчайшие).

Слайд 53


Пример: Каков будет кратчайший путь из 1 в 4?
Описание слайда:
Пример: Каков будет кратчайший путь из 1 в 4?

Слайд 54


Контуры отрицательного веса Если граф содержит контуры отрицательного веса, то поиск минимальной длины пути теряет смысл
Описание слайда:
Контуры отрицательного веса Если граф содержит контуры отрицательного веса, то поиск минимальной длины пути теряет смысл

Слайд 55


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

Слайд 56


Соглашение: Мы далее будем рассматривать только графы без контуров отрицательного веса. (но дуги с отрицательной длиной могут существовать)
Описание слайда:
Соглашение: Мы далее будем рассматривать только графы без контуров отрицательного веса. (но дуги с отрицательной длиной могут существовать)

Слайд 57


Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). К...
Описание слайда:
Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). К настоящему времени неизвестен алгоритм, позволяющий найти минимальный путь только для пары вершин. Все алгоритмы требуют определения оценки минимального пути для всех вершин графа.

Слайд 58


Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Для некоторой вершины p обозначим массив кратчайших...
Описание слайда:
Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Предположим,что есть алгоритм определения этого массива для любой вершины графа.

Слайд 59


Алгоритм определения пути Ищем кратчайший путь из i-й вершины в j-ю. Можно найти такую вершину k, что: Di(j)=Di(k)+A[k,j] Таким свойством обладает...
Описание слайда:
Алгоритм определения пути Ищем кратчайший путь из i-й вершины в j-ю. Можно найти такую вершину k, что: Di(j)=Di(k)+A[k,j] Таким свойством обладает предпоследняя вершина кратчайшего пути из i в j. Запомним вершину k в стеке и ищем вершину l, для которой: Di(k)=Di(l)+A[l,j]

Слайд 60


На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. На каждом шаге мы приближаемся к исходной вершине, и, в конце...
Описание слайда:
На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. В стеке будет искомый путь (последовательность вершин).

Слайд 61


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

Слайд 62


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

Слайд 63


Если для вершины k нашли вершину q, такую, что: Если для вершины k нашли вершину q, такую, что: Di(k) > Di(q)+A[k,q], то заменяем Di(k) на сумму...
Описание слайда:
Если для вершины k нашли вершину q, такую, что: Если для вершины k нашли вершину q, такую, что: Di(k) > Di(q)+A[k,q], то заменяем Di(k) на сумму Di(q)+A[k,q]. Процесс завершается, когда дальнейшее улучшение невозможно.

Слайд 64


Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. Описанной схеме не хватает существенного момента – порядка выбора...
Описание слайда:
Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. В реальности этот порядок важен, т.к. от него существенно зависит эффективность алгоритма.

Слайд 65


Алгоритм Форда-Беллмана Этот алгоритм применим к любому ориентированному графу без контуров отрицательной длины
Описание слайда:
Алгоритм Форда-Беллмана Этот алгоритм применим к любому ориентированному графу без контуров отрицательной длины

Слайд 66


Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем...
Описание слайда:
Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. (N-2) раза повторяем следующие действия: Для всех вершин q (кроме i) Для всех вершин w вычисляем: Di[q]=min(Di[q],Di[w]+A[w,q])

Слайд 67


Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2). Если веса всех дуг графа...
Описание слайда:
Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2). Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2).

Слайд 68


Алгоритм Дейкстры
Описание слайда:
Алгоритм Дейкстры

Слайд 69


Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем...
Описание слайда:
Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Обозначим через T совокупность вершин графа без вершины i. Выполнять, пока T не пусто, следующие действия: - искать в T вершину u, для которой величина Di[u] минимальна; - исключить u из T; - для всех оставшихся вершин w из T вычислить: Di[w]=min(Di[w],Di[w]+A[u,w]

Слайд 70


Алгоритм Дейкстры имеет сложность Алгоритм Дейкстры имеет сложность O(N2)
Описание слайда:
Алгоритм Дейкстры имеет сложность Алгоритм Дейкстры имеет сложность O(N2)

Слайд 71


Является ли этот граф бесконтурным?
Описание слайда:
Является ли этот граф бесконтурным?

Слайд 72


А этот?
Описание слайда:
А этот?

Слайд 73


Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p. Бесконтурные...
Описание слайда:
Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p. Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p.

Слайд 74


Гамильтоновы циклы, слайд №74
Описание слайда:

Слайд 75


Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Cуществует эффективный...
Описание слайда:
Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Сложность этого алгоритма = O(N+M). Для “правильного” бесконтурного графа расстояния считаются очень просто.

Слайд 76


Гамильтоновы циклы, слайд №76
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию