- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Гамильтоновы циклы презентация
Содержание
- 1. Гамильтоновы циклы
- 2. Определение Граф называется гамильтоновым, если он содержит
- 3. Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе…
- 4. Постановка задачи Дан связный неориентированный граф. Найти все гамильтоновы циклы (если они есть).
- 5. “Простой” способ поиска: Сгенерируем все перестановки вершин
- 6. Рассмотрим пример: Пусть у графа, скажем, 20
- 7. А если вершин 100? Число перестановок будет равно: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ≈ 9.3•10157
- 8. Это не все… Чтобы проверить каждую из
- 9. Конечно, “лобовое” решение крайне нерационально. Ведь при
- 10. Структуры данных: Будем использовать два массива целых:
- 11. Алгоритм Будем предполагать, что поиск циклов мы
- 12. Алгоритм Центральной процедурой алгоритма является рекурсивная функция
- 13. Алгоритм 1. Функция берет последнюю добавленную в
- 14. Алгоритм 3. Если найдена вершина, связанная с
- 15. На каждом шаге к массиву Arr добавляется
- 16. for (j=1; j
- 17. Рассмотрим граф: Этот граф имеет два гамильтоновых
- 18. На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин
- 19. В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины
- 22. Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла.
- 26. Какую вершину будем добавлять?
- 29. Какую вершину будем добавлять?
- 34. Какую вершину будем добавлять?
- 42. Следующей будет добавлена 5-я вершина
- 51. Кратчайшие пути в графах
- 52. Постановка задачи Дан ориентированный граф; Каждой дуге
- 53. Пример: Каков будет кратчайший путь из 1
- 54. Контуры отрицательного веса Если граф содержит контуры
- 55. Если мы ищем кратчайший путь из 1
- 56. Соглашение: Мы далее будем рассматривать только графы
- 57. Обозначим длину минимального пути между i-й и
- 58. Для некоторой вершины p обозначим массив кратчайших
- 59. Алгоритм определения пути Ищем кратчайший путь из
- 60. На каждом шаге мы приближаемся к исходной
- 61. Таким образом, если для каждой вершины известен
- 62. Общая схема такова: Пусть зафиксирована i-я вершина,
- 63. Если для вершины k нашли вершину q,
- 64. Описанной схеме не хватает существенного момента –
- 65. Алгоритм Форда-Беллмана Этот алгоритм применим к любому
- 66. Первоначально присваиваем всем элементам массива Di[k] значения
- 67. Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2).
- 68. Алгоритм Дейкстры Исходные данные алгоритма: Орграф
- 69. Первоначально присваиваем всем элементам массива Di[k] значения
- 70. Алгоритм Дейкстры имеет сложность O(N2) Имеется
- 71. Является ли этот граф бесконтурным? Нет. Контур выделен.
- 72. А этот?
- 73. Бесконтурные графы обладают замечательным свойством: их вершины
- 74. У нашего графа есть “неправильная” дуга (2-1):
- 75. Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного
- 76. http://catstail.narod.ru/lec/lec-12.zip
Слайд 2Определение
Граф называется гамильтоновым, если он содержит цикл, включающий все вершины графа.
Этот
цикл тоже называется гамильтоновым.
Не все связные графы гамильтоновы.
Не все связные графы гамильтоновы.
Слайд 3Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла
в произвольном графе…
Слайд 4Постановка задачи
Дан связный неориентированный граф.
Найти все гамильтоновы циклы
(если они есть).
Слайд 5“Простой” способ поиска:
Сгенерируем все перестановки вершин графа.
Дальше можно просто проверить
каждую, не является ли она гамильтоновым циклом.
Так ли это просто?
Так ли это просто?
Слайд 6Рассмотрим пример:
Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин?
20!=2432902008176640000
≈ 2.4•1018
Число перестановок N предметов равно N!
Слайд 7А если вершин 100?
Число перестановок будет равно:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
≈ 9.3•10157
Слайд 8Это не все…
Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно
затратить еще N операций.
Таким образом, “лобовое” решение требует
N•N! операций.
Это число растет с ростом N очень быстро…
Таким образом, “лобовое” решение требует
N•N! операций.
Это число растет с ростом N очень быстро…
Слайд 9Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин
не используется информация о том, какие из вершин связаны друг с другом.
Есть более рациональный алгоритм…
Есть более рациональный алгоритм…
Слайд 10Структуры данных:
Будем использовать два массива целых:
Arr[N] – в этом массиве будет
находиться последовательность вершин;
Nnew[N] – если i-й элемент этого массива есть 0, значит на текущем шаге i-я вершина графа еще не посещалась.
Для задания структуры графа будем использовать матрицу смежности Matr[N][N]
Nnew[N] – если i-й элемент этого массива есть 0, значит на текущем шаге i-я вершина графа еще не посещалась.
Для задания структуры графа будем использовать матрицу смежности Matr[N][N]
Слайд 11Алгоритм
Будем предполагать, что поиск циклов мы ведем c вершины 1.
На очередном
шаге в массиве Arr находится последовательность связанных друг с другом вершин, которые, возможно, являются началом гамильтонова цикла.
Слайд 12Алгоритм
Центральной процедурой алгоритма является рекурсивная функция Step.
Эта функция принимает один целый
параметр – номер шага.
Слайд 13Алгоритм
1. Функция берет последнюю добавленную в массив Arr вершину, делает ее
текущей, и ищет (в цикле по матрице смежности) вершины, связанные с текущей.
2. Если номер шага = N+1, а текущая вершина связана с первой вершиной, то в Arr находится гамильтонов цикл. Его можно вывести, а затем выйти из Step.
2. Если номер шага = N+1, а текущая вершина связана с первой вершиной, то в Arr находится гамильтонов цикл. Его можно вывести, а затем выйти из Step.
Слайд 14Алгоритм
3. Если найдена вершина, связанная с текущей и еще непосещенная, то:
Эта
новая вершина добавляется в “хвост” Arr;
Новая вершина отмечается как посещенная;
Вызывается процедура Step cо значением параметра, увеличенным на 1;
После возврата новая вершина вновь отмечается, как непосещенная.
4. Если все вершины, связанные с текущей уже посещались, то осуществляется выход из Step.
Новая вершина отмечается как посещенная;
Вызывается процедура Step cо значением параметра, увеличенным на 1;
После возврата новая вершина вновь отмечается, как непосещенная.
4. Если все вершины, связанные с текущей уже посещались, то осуществляется выход из Step.
Слайд 15На каждом шаге к массиву Arr добавляется еще не посещенная вершина.
Поскольку число вершин конечно, то процесс должен рано или поздно закончиться.
Смущает то, что после возврата из функции Step, последняя вершина помечается как непосещённая.
Не приведет ли это к зацикливанию?..
Смущает то, что после возврата из функции Step, последняя вершина помечается как непосещённая.
Не приведет ли это к зацикливанию?..
Слайд 16for (j=1; j
{
…
if (Nnew[j]==0) // сюда управление
{ // попадет при каждом j
Arr[k]=j; // не более 1 раза!
Nnew[j]=1;
Step(k+1);
Nnew[j]=0;
}
…
if (Nnew[j]==0) // сюда управление
{ // попадет при каждом j
Arr[k]=j; // не более 1 раза!
Nnew[j]=1;
Step(k+1);
Nnew[j]=0;
}
Слайд 17Рассмотрим граф:
Этот граф имеет два гамильтоновых цикла:
(1,2,3,4,5)
и
(1,5,4,2,1)
Посмотрим, как будет работать
описанный алгоритм с возвратами…
Слайд 52Постановка задачи
Дан ориентированный граф;
Каждой дуге приписана “длина” – вес дуги;
Веса дуг
хранятся в матрице смежности, причем, если i-я и j-я вершины не связаны дугой, то A[i,j]=∞
“Длина” или оценка пути = сумме весов дуг, составляющих путь.
Требуется находить пути с минимальной оценкой (т.е. кратчайшие).
“Длина” или оценка пути = сумме весов дуг, составляющих путь.
Требуется находить пути с минимальной оценкой (т.е. кратчайшие).
Слайд 53Пример:
Каков будет кратчайший путь из 1 в 4?
Путь (1-3-2-4). Его
длина = 6. Другие пути длиннее.
Слайд 54Контуры отрицательного веса
Если граф содержит контуры отрицательного веса, то поиск минимальной
длины пути теряет смысл
Слайд 55Если мы ищем кратчайший путь из 1 в 5, то проходя
контур 3-4-2-3 несколько раз, можно сделать путь 1-5 меньше любой наперед заданной величины.
Слайд 56Соглашение:
Мы далее будем рассматривать только графы без контуров отрицательного веса.
(но дуги
с отрицательной длиной могут существовать)
Слайд 57Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j).
К
настоящему времени неизвестен алгоритм, позволяющий найти минимальный путь только для пары вершин.
Все алгоритмы требуют определения оценки минимального пути для всех вершин графа.
Все алгоритмы требуют определения оценки минимального пути для всех вершин графа.
Слайд 58Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных
вершин через Dp.
Предположим,что есть алгоритм определения этого массива для любой вершины графа.
Предположим,что есть алгоритм определения этого массива для любой вершины графа.
Слайд 59Алгоритм определения пути
Ищем кратчайший путь из i-й вершины в j-ю.
Можно найти
такую вершину k, что:
Di(j)=Di(k)+A[k,j]
Таким свойством обладает предпоследняя вершина кратчайшего пути из i в j.
Запомним вершину k в стеке и ищем вершину l, для которой:
Di(k)=Di(l)+A[l,j]
Di(j)=Di(k)+A[k,j]
Таким свойством обладает предпоследняя вершина кратчайшего пути из i в j.
Запомним вершину k в стеке и ищем вершину l, для которой:
Di(k)=Di(l)+A[l,j]
Слайд 60На каждом шаге мы приближаемся к исходной вершине, и, в конце
концов, дойдем до нее.
В стеке будет искомый путь (последовательность вершин).
В стеке будет искомый путь (последовательность вершин).
Слайд 61Таким образом, если для каждой вершины известен массив кратчайших расстояний до
всех вершин графа, можно построить кратчайший путь.
Но как определить массив
кратчайших расстояний?
Но как определить массив
кратчайших расстояний?
Слайд 62Общая схема такова:
Пусть зафиксирована i-я вершина, для которой мы ищем массив
кратчайших расстояний.
Для каждой вершины j вычисляем верхние ограничения Di(j) на расстояние (i – j).
Далее стараемся улучшить эти ограничения.
Для каждой вершины j вычисляем верхние ограничения Di(j) на расстояние (i – j).
Далее стараемся улучшить эти ограничения.
Слайд 63Если для вершины k нашли вершину q, такую, что:
Di(k) > Di(q)+A[k,q],
то
заменяем Di(k) на сумму Di(q)+A[k,q].
Процесс завершается, когда дальнейшее улучшение невозможно.
Процесс завершается, когда дальнейшее улучшение невозможно.
Слайд 64Описанной схеме не хватает существенного момента – порядка выбора вершин k
и q.
В реальности этот порядок важен, т.к. от него существенно зависит эффективность алгоритма.
В реальности этот порядок важен, т.к. от него существенно зависит эффективность алгоритма.
Слайд 65Алгоритм Форда-Беллмана
Этот алгоритм применим к любому ориентированному графу без контуров отрицательной
длины
Исходные данные алгоритма:
Орграф без контуров отрицательной длины;
Матрица весов дуг;
Фиксированная вершина i
Результат:
- Расстояние (кратчайшее) от всех вершин графа до фиксированной вершины i.
Слайд 66Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем
значение 0.
(N-2) раза повторяем следующие действия:
Для всех вершин q (кроме i)
Для всех вершин w вычисляем:
Di[q]=min(Di[q],Di[w]+A[w,q])
(N-2) раза повторяем следующие действия:
Для всех вершин q (кроме i)
Для всех вершин w вычисляем:
Di[q]=min(Di[q],Di[w]+A[w,q])
Чему равна временная сложность этого алгоритма?
N-кратное повторение трех вложенных циклов дает порядок O(N3)
Слайд 67Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить
до производительности O(N2).
Слайд 68Алгоритм Дейкстры
Исходные данные алгоритма:
Орграф с дугами неотрицательной длины;
Матрица весов дуг;
Фиксированная
вершина i
Результат:
- Расстояние (кратчайшее) от всех вершин графа до фиксированной вершины i.
Результат:
- Расстояние (кратчайшее) от всех вершин графа до фиксированной вершины i.
Слайд 69Первоначально присваиваем всем элементам массива 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]
Обозначим через 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).
Это бесконтурные графы
(ориентированные графы без циклов)
Это бесконтурные графы
(ориентированные графы без циклов)
Слайд 73Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что
для любой дуги (p,q) всегда будет q > p.
Слайд 74У нашего графа есть “неправильная” дуга (2-1):
Если сделать вершину 1 вершиной
2, а вершину 2 – вершиной 1, то граф станет “правильным”:
Слайд 75Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его
в “правильный” граф.
Сложность этого алгоритма = O(N+M).
Для “правильного” бесконтурного графа расстояния считаются очень просто.
Сложность этого алгоритма = O(N+M).
Для “правильного” бесконтурного графа расстояния считаются очень просто.
