- •1. Понятие логического высказывания. Элементарное и сложное высказывание. Логические выражения (формулы) и логические операции. Диаграммы Венна.
- •2. Представление логических выражений в дизьюнктивной (коньюнктивной) нормальной форме. Теорема Шеннона и принцип двойственности.
- •3. Логические законы (тавтологии).
- •4.Множества и подмножества.Универсально множество.Основные определения и свойства.Мощность множества,степень множества.
- •5 Операции над множествами, их свойства. Связь с логическими законами.
- •6.Описание числовых множеств на плоскости.Диаграммы Эйлера.
- •10.Понятие функции как специального вида отношений. Инъекцивная, сюрьективная, биективная функции
- •8. Бинарные отношения. Основные определения и способы задания отношений. Обратное отношение. Композиция отношений.
- •7.Кортеж, прямое произведение множеств. Понятие графика и свойства графиков.
- •11. Алгебраические системы. Алгебра множеств и булева алгебра.
- •22. Элементы цикломатики. Фундаментальная система циклов, цикломатическое и коциклическое число.
- •13.Понятие изоморфизма графов. Основные инварианты графа. Теорема Эйлера о степенях вершин. Подграфы и операции над графами.
- •24. Гамильтоновы графы. Достаточные условия существования гамильтонова цикла.
- •15. Вершинная и реберная связность графа. Мосты, блоки, точки сочленения. Разделяющие множества и разрезы. Теорема Менгера в вершинной и реберной форме
- •16. Двудольные графы и паросочетания. Свойства двудольных графов. Теорема Холла о совершенном паросочетании.
- •17. Неориентированные (свободные) и ориентированные (корневые) деревья. Свойства деревьев.
- •19. Способы представления деревьев в эвм. Упорядоченные и бинарные деревья, их свойства.
- •20.Поиск кратчайших путей на взвешенных графах. Алгоритм Форда-Беллмана и алгоритм Дейкстры.
- •21. Сети и потоки в сетях. Топологическая сортировка сети. Определение потока. Теорема Форда-Фалкерсона.
- •25. Задача коммивояжера. Решение задачи методом ветвей и границ.
- •27. Задача о раскраске графа. Понятие хроматического числа, его связь с валентностью вершин. Примеры графов с известным хроматическим числом. Теорема о раскраске планарных графов
- •23. Эйлеровы и полуэйлеровы графы. Алгоритм построения эйлерова цикла в эйлеровом графе.
25. Задача коммивояжера. Решение задачи методом ветвей и границ.
задача коммивояжера.
Предположим, что наш граф гамильтонов и на его дугах заданы веса cij, которые могут обозначать, например, стоимость проезда между населенными пунктами. Коммивояжер (бродячий торговец) должен побывать во всех этих пунктах и вернуться назад, затратив при этом минимум средств. То есть речь идет о построении гамильтонова цикла минимального веса.
В общем случае предполагается, что cij cji, то есть граф может быть и ориентированным, причем веса дуг (u,v) и (v,u) могут отличаться.
Решение задачи «в лоб» предполагает перебор всех возможных вариантов, то есть p! операций. Но если граф большой, это слишком дорогое удовольствие, поэтому разработаны приемы сокращения перебора. Наиболее распространенный из таких методов ограниченного перебора носит название «метод ветвей и границ».
Решение задачи коммивояжера методом ветвей и границ.
Рассмотрим дерево перебора (дерево решений) и назовем его T, как мы называли упорядоченные корневые деревья. Общий принцип решения методом ветвей и границ такой: на каждом шаге дерево решений разбивается на подмножества ветвей Затем вычисляется некоторая оценка, которая служит критерием отсечения заведомо бесперспективных ветвей.
|
1 |
3 |
1 |
2 |
2 |
|
5 |
4 |
6 |
2 |
4 |
|
6 |
1 |
3 |
1 |
5 |
|
4 |
3 |
2 |
4 |
1 |
|
Основной операцией, на основе которой выполняется необходимая оценка, является приведение матрицы весов. Что это означает? Рассмотрим по шагам.
Введем обозначения: z – искомый гамильтонов цикл, l(z) – вес такого гамильтонова цикла.
Шаг 1. Получение нижней l0(z) и верхней L(z) оценок веса искомого гамильтонова цикла (построение границ решения).
Начнем с получения нижней оценки, так как именно она наиболее важна для решения задачи.
1.1. Выбираем min по каждой строке матрицы весов. Строка i у нас, как всегда, соответствует выходам из вершины vi, а столбец i - входам. То есть мы выбираем сначала минимальный по весу выход из каждой вершины.
Теперь из каждой строки матрицы вычтем соответствующее этой строке минимальное значение.
Получаем матрицу:
|
0 |
2 |
0 |
1 |
0 |
|
3 |
2 |
4 |
1 |
3 |
|
5 |
0 |
2 |
0 |
4 |
|
3 |
2 |
1 |
3 |
0 |
|
1.2. Выбираем min по каждому столбцу, то есть рассматриваем все дуги, по которым можно войти в каждую вершину vj. Повторяем то, что делали на первом шаге, только теперь для столбцов.
|
0 |
0 |
0 |
1 |
0 |
|
1 |
2 |
4 |
1 |
3 |
|
5 |
0 |
2 |
0 |
2 |
|
3 |
2 |
1 |
1 |
0 |
|
Полученный результат показывает, что минимальная дуга, по которой мы можем войти в вершину 3, - это c13=2. Теперь уже ясно, что l(z) l0(z)+ c13=8.
Таким образом, мы получили нижнюю оценку веса гамильтонова цикла. То, что мы проделали, называется приведением матриц по строке и столбцу. В приведенной матрице ненулевые значения представляют собой превышения над минимумом при входе и выходе из каждой вершины.
1.3. Для получения верхней оценки L(z) построим произвольный цикл методом поиска в глубину и посчитаем его вес по исходной матрице весов.
L(z)= c12+ c23+ c34+ c45+ c51=1+5+6+4+3=19.
Если бы мы получили, что l(z)=L(z), то это и был бы искомый гамильтонов цикл минимального веса. Но в нашем примере это не так. Мы, всего-навсего, имеем 8l(z)19, и нам придется продолжать поиск.
Шаг 2. Ветвление (разбиение дерева решений на подмножества). Теперь будем добавлять в цикл по одному ребру на основе следующей схемы.
Рассмотрим два случая(рис.3.27).: 1) гамильтонов цикл z проходит через некоторую минимальную по весу дугу (vi,vj); 2) гамильтонов цикл z не проходит через эту дугу. Назовем эти два варианта z(i,j) и соответственно. Они образуют две ветви решений.
Рассмотрим оценки для каждой из этих ветвей. Для ветви z(i,j) остается нижняя оценка l(z)=8. Рассмотрим теперь оценку для ветви . Если путь не проходит через (i,j), то мы должны выйти из вершины i по какой-то дуге (i,k) и войти в вершину j по какой-то дуге (m,j). В наиболее удачном случае это будут дуги минимальных весов. Тогда
Таким образом, для каждого уже обнуленного перехода по ребру (i,j) можно получить нижнюю оценку превышения над минимумом, если мы пройдем мимо этого ребра.
Вычисляем такие оценки для всех дуг, обнуленных в процессе приведения матрицы, и в качестве альтернативы перехода выбираем вариант с максимальным значением ij. То есть, включаем в цикл то ребро, у которого альтернативный путь заведомо будет самым плохим.
Посмотрим, что получается в нашем примере. Для всех нулевых элементов нашей приведенной матрицы cij берем ребро с минимальным значением (по i-й строке), по которому можно выйти из вершины i в любую вершину, кроме j, и ребро с минимальным значением (по j-му столбцу), по которому можно войти в вершину j из любой вершины, кроме i.
12=0+0=0; 13=0+1=1; 14=0+0=0; 21=1+1=2; 35=1+1=2; 42=2+0=2; 54=1+0=1.
У нас получилось 3 одинаковых значения, берем первое: 21. После первого шага z={(2,1)}.
Теперь «склеим» вершины 2 и 1, чтобы вывести дугу (2,1) из рассмотрения. Для этого удалим из матрицы 2-ю строку и 1-й
|
0 |
0 |
1 |
3 |
|
5 |
0 |
0 |
2 |
|
3 |
1 |
1 |
0 |
|
Теперь опять приводим полученную матрицу по строке и столбцу и вычисляем оценки ij.
Итак, нижняя оценка l(z) остается прежней: l10(z)=8.
Вычисляем оценки: 13=0+1=1; 14=0+0=0; 35=3+1=4; 42=2+1=3; 54=1+0=1.
Имеем: max=4, то есть, выбираем c35.
|
0 |
0 |
0 |
2 |
|
1 |
|
0 |
После приведения этой матрицы нижняя оценка веса цикла остается прежней. Вычисляем оценки ij: 13=0+2=2; 14=0+0=0; 42=0+0=0.
Выбираем c13. Склеиваем вершины 1 и 3, удаляя первую строку и третий столбец. Получаем
0 |
|
1 |
0 |
Итак, мы получили следующий гамильтонов цикл: (3,5),(5,4),(4,2),(2,1),(1,3). Вес этого цикла равен l(z)=1+1+1+2+3=8, что удовлетворяет ранее найденной нижней оценке.
Дерево решений для рассмотренного примера выглядит так, как показано на рис.3.28.
В рассмотренном нами случае мы имели полный набор вариантов перехода, поэтому использовали только нижнюю оценку границы решений. Но если граф не полный, то, действуя по рассмотренной схеме, на каком-то шаге после приведения матрицы мы можем получить превышение нижней оценки веса цикла над L(z). В этом случае цикл, построенный для верхней оценки L(z), и будет искомым решением задачи.