Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Структуры данных.docx
X
- •Элементарные алгоритмы для работы с графами
- •Работа алгоритма[править | править вики-текст]
- •Неформальное описание[править | править вики-текст]
- •Формальное описание[править | править вики-текст]
- •Алгоритм поиска в глубину[править | править вики-текст]
- •Нерекурсивные варианты[править | править вики-текст]
- •Общая идея
- •[Править]Пошаговое представление
- •[Править]Реализация
- •[Править]Время работы
- •[Править]Цвета вершин
- •Топологическая сортировка и сильно связные компоненты
- •↑ Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка
- •Пример работы алгоритма[править | править вики-текст]
- •Алгоритмы[править | править вики-текст]
- •Минимальные остовные деревья (мst)
- •Введение
- •Постановка задачи
- •Кратчайшие пути
- •Давайте придумаем что-нибудь простое
- •А если я педант?
- •Задача о максимальном потоке
- •[Править]Определение потока
- •[Править]Пример
- •Увеличивающие пути. Теорема Бержа
- •Алгоритм Эдмондса. Сжатие цветков
- •Эффективная реализация
- •Оптимизация: предварительное построение паросочетания
- •Случай двудольного графа
- •Дальнейшая оптимизация
- •[Править]Реализация
- •[Править]Оценка производительности
- •[Править]Пример несходящегося алгоритма
- •[Править]Оценка быстродействия
- •[Править]Литература
- •Максимальные паросочетания[править | править вики-текст]
- •Описание алгоритма Необходимые определения
- •Теорема Бержа
- •Алгоритм Куна
- •Время работы
- •Реализация
- •Улучшенная реализация
- •[Править]Постановка задачи
- •[Править]Решение
- •[Править]Псевдокод
- •Префиксы и суффиксы строки
- •Прямые переходы
- •[Править]Суффиксные ссылки
- •Основные определения и описание структуры[править | править вики-текст]
- •Свойства суффиксных деревьев[править | править вики-текст]
- •Требования суффиксного дерева к памяти[править | править вики-текст]
- •[Править]Недостатки
- •Метод хеширования
- •[Править]Алгоритм
- •[Править]Псевдокод
- •[Править]Время работы
- •[Править]Надёжность
- •Автоматные модели в программировании
- •[Править]Переходы между состояниями [править]Прямые переходы
- •[Править]Суффиксные ссылки
- •[Править]Псевдокод
- •[Править]Пример использования
- •[Править]Псевдокод
- •[Править]Пример
- •[Править]Время работы
- •[Править]Эффективный алгоритм
- •[Править]Псевдокод
- •[Править]Время работы
- •[Править]Построение префикс-функции по z-функции [править]Постановка задачи
- •[Править]Описание алгоритма
- •Приближенные алгоритмы решения np-трудных задач
Приближенные алгоритмы решения np-трудных задач
Понятие NP-трудности, NP-полноты
Задача коммивояжера
Приближенный алгоритм решения задачи коммивояжера
Эволюционные алгоритмы
Решение задачи коммивояжера с помощью эволюционного алгоритма
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]