2015-10-13
459
Алгоритмов на графах для решения задач
Тема 2.1 Использование алгоритмов генерирования
Перестановок, множества всех подмножеств
Множества, к-элементных подмножеств множества,
Разбиения множества на подмножества для решения
Задач
Использование алгоритмов генерирования перестановок, множества всех подмножеств множества, к-элементных подмножеств множества, разбиения множества на подмножества для решения задач
Литература: [5, с. 5-70]; [7, с. 25-65]
Тема 2.2 Задачи, основанные на поиске в ширину и в глубину
В графе
Понятие графа. Основные свойства графов
Способы представления графов в памяти ЭВМ
Поиск в глубину. Поиск в ширину
Литература: [3, с. 436-453]
Тема 2.3 Алгоритмы поиска кратчайших расстояний в графе
Алгоритм поиска кратчайшего пути между парой вершин
Алгоритм поиска кратчайших путей между всеми парами вершин
Литература: [3, с. 479-523]
Тема 2.4 Алгоритмы нахождения максимального потока и
Потока минимальной стоимости
|
|
|
Понятие максимального потока
Алгоритм нахождения максимального потока Форда-Фанкерсона
Алгоритм нахождения потока минимальной стоимости
Литература: [3, с. 535-552]
Тема 2.5 Задачи, решаемые полным перебором. Методы
Сокращения полного перебора
Общая схема полного перебора. Дерево поиска
Задачи, решаемые полным перебором: задача о коммивояжере, задача о шахматном коне, задача о лабиринте
Методы сокращения полного перебора
Литература: [9, с. 211-228]; [7, с. 79-96]
Тема 2.6 Алгоритмы с возвращением, их реализация
Понятие рекурсии. Вычислительная схема алгоритмов перебора с возвращением
Задача о расстановке ферзей на шахматной доске
Литература: [4, с. 221-231]
Тема 2.7 Динамическое программирование, задачи решаемые
Методом динамического программирования
Понятие реккурентного соотношения
Технологии динамического программирования: восходящее динамическое программирование, нисходящее динамическое программирование
Задачи решаемые методом динамического программирования: задача о ранце, числа Фибоначчи, наибольшая общая последовательность
Литература: [3, с. 287-312]; [7, с. 96-105]
Тема 2.8 Метод ветвей и границ
Вычислительная схема метода ветвей и границ
Литература: [9, с. 228-231]; [7, с. 105-109]
Тема 2.9 Жадные алгоритмы
Принцип жадного выбора
Коды Хоффмана. Задача о расписании
Жадный алгоритм поиска кратчайшего пути между двумя вершинами графа
Жадный алгоритм в задаче о сумме элементов подмножества
Литература: [3, с. 313-336]; [6, с. 250-259]
Вопросы для самоконтроля
1 По каким правилам создаются всевозможные комбинации предметов определенного типа из набора данных?
|
|
|
2 В каких случаях возможно сформировать перестановки с повторениями?
3 В чем проявляется рекурсивность метода перебора с возвратом?
4 Почему полный метод перебора с возвратом гарантирует отыскание всех решений задачи?
5 Как формируется рекурсивная база метода возвратной рекурсии?
6 Дайте определение графа и его основным компонентам.
7 Дайте определение матрице смежности. Как формируется матрица? Примеры
8 Дайте определение матрице инцидентности. Как формируется матрица? Примеры.
9 Дайте определение матрице расстояний. Как формируется матрица? Примеры
10 С какими видами графов работают алгоритмы Дейкстры, Флойда и переборные алгоритмы?
11 Как от представления графа зависит эффективность алгоритма его обхода?
12 За счет чего поиск в ширину является достаточно ресурсоемким алгоритмом?
13 В чем преимущества алгоритмов обхода графа в ширину?
14 Каким образом в алгоритме перебора с возвратом при обходе графа обрабатывается посещение тупиковых вершин?
