Дискретная математика
Задача на нахождение кратчайшего пути. Определение нижней границы гамильтоновых циклов множества с помощью операции редукции. Изучение процесса разложения матрицы по маршрутным строкам. Определение, изображение оптимальной длины маршрута коммивояжёра.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 16.01.2016 |
| Размер файла | 29,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
САНКТ-ПЕТЕРБУРГСКИЙ УНИВЕРСИТЕТ
УПРАВЛЕНИЯ И ЭКОНОМИКИ
Институт экономики, менеджмента и информационных технологий
Кафедра информационных технологий и математики
КОНТРОЛЬНАЯ РАБОТА
«Дискретная математика»
Выполнил студент
2573/3-2 группы 3 курса
заочного отделения
Горбунов Алексей Дмитриевич
Проверил: Гармашов А.В.
Санкт-Петербург 2016
1. Задача коммивояжера
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 30 + 26 + 29 + 27 + 19 + 21 = 152
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
30 |
25 |
27 |
39 |
18 |
18 |
|
|
2 |
31 |
M |
26 |
25 |
30 |
45 |
25 |
|
|
3 |
28 |
27 |
M |
29 |
21 |
43 |
21 |
|
|
4 |
41 |
19 |
21 |
M |
27 |
25 |
19 |
|
|
5 |
29 |
23 |
25 |
31 |
M |
19 |
19 |
|
|
6 |
21 |
40 |
35 |
16 |
19 |
M |
16 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
12 |
7 |
9 |
21 |
0 |
|
|
2 |
6 |
M |
1 |
0 |
5 |
20 |
|
|
3 |
7 |
6 |
M |
8 |
0 |
22 |
|
|
4 |
22 |
0 |
2 |
M |
8 |
6 |
|
|
5 |
10 |
4 |
6 |
12 |
M |
0 |
|
|
6 |
5 |
24 |
19 |
0 |
3 |
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
12 |
7 |
9 |
21 |
0 |
|
|
2 |
6 |
M |
1 |
0 |
5 |
20 |
|
|
3 |
7 |
6 |
M |
8 |
0 |
22 |
|
|
4 |
22 |
0 |
2 |
M |
8 |
6 |
|
|
5 |
10 |
4 |
6 |
12 |
M |
0 |
|
|
6 |
5 |
24 |
19 |
0 |
3 |
M |
|
|
dj |
5 |
0 |
1 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
12 |
6 |
9 |
21 |
0 |
|
|
2 |
1 |
M |
0 |
0 |
5 |
20 |
|
|
3 |
2 |
6 |
M |
8 |
0 |
22 |
|
|
4 |
17 |
0 |
1 |
M |
8 |
6 |
|
|
5 |
5 |
4 |
5 |
12 |
M |
0 |
|
|
6 |
0 |
24 |
18 |
0 |
3 |
M |
Сумма констант приведения определяет нижнюю границу H:
H = ?di + ?dj
H = 18+25+21+19+19+16+5+0+1+0+0+0 = 124
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ? 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ?dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
12 |
6 |
9 |
21 |
0(6) |
|
|
2 |
1 |
M |
0(1) |
0(0) |
5 |
20 |
|
|
3 |
2 |
6 |
M |
8 |
0(5) |
22 |
|
|
4 |
17 |
0(5) |
1 |
M |
8 |
6 |
|
|
5 |
5 |
4 |
5 |
12 |
M |
0(4) |
|
|
6 |
0(1) |
24 |
18 |
0(0) |
3 |
M |
d(1,6) = 6 + 0 = 6; d(2,3) = 0 + 1 = 1; d(2,4) = 0 + 0 = 0; d(3,5) = 2 + 3 = 5; d(4,2) = 1 + 4 = 5; d(5,6) = 4 + 0 = 4; d(6,1) = 0 + 1 = 1; d(6,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (6 + 0) = 6 для ребра (1,6), следовательно, множество разбивается на два подмножества (1,6) и (1*,6*).
Исключение ребра (1,6) проводим путем замены элемента d16 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,6*), в результате получим редуцированную матрицу.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
12 |
6 |
9 |
21 |
M |
|
|
2 |
1 |
M |
0 |
0 |
5 |
20 |
|
|
3 |
2 |
6 |
M |
8 |
0 |
22 |
|
|
4 |
17 |
0 |
1 |
M |
8 |
6 |
|
|
5 |
5 |
4 |
5 |
12 |
M |
0 |
|
|
6 |
0 |
24 |
18 |
0 |
3 |
M |
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,6*) = 124 + 6 = 130
Включение ребра (1,6) проводится путем исключения всех элементов 1-ой строки и 6-го столбца, в которой элемент d61 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
2 |
3 |
4 |
5 |
di |
|
|
2 |
1 |
M |
0 |
0 |
5 |
0 |
|
|
3 |
2 |
6 |
M |
8 |
0 |
0 |
|
|
4 |
17 |
0 |
1 |
M |
8 |
0 |
|
|
5 |
5 |
4 |
5 |
12 |
M |
4 |
|
|
6 |
M |
24 |
18 |
0 |
3 |
0 |
|
|
dj |
1 |
0 |
0 |
0 |
0 |
5 |
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 5
Нижняя граница подмножества (1,6) равна:
H(1,6) = 124 + 5 = 129 ? 130
Поскольку нижняя граница этого подмножества (1,6) меньше, чем подмножества (1*,6*), то ребро (1,6) включаем в маршрут с новой границей H = 129
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
1 |
2 |
3 |
4 |
5 |
di |
|
|
2 |
0(0) |
M |
0(1) |
0(0) |
5 |
0 |
|
|
3 |
1 |
6 |
M |
8 |
0(4) |
1 |
|
|
4 |
16 |
0(1) |
1 |
M |
8 |
1 |
|
|
5 |
0(0) |
0(0) |
1 |
8 |
M |
0 |
|
|
6 |
M |
24 |
18 |
0(3) |
3 |
3 |
|
|
dj |
0 |
0 |
1 |
0 |
3 |
0 |
d(2,1) = 0 + 0 = 0; d(2,3) = 0 + 1 = 1; d(2,4) = 0 + 0 = 0; d(3,5) = 1 + 3 = 4; d(4,2) = 1 + 0 = 1; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(6,4) = 3 + 0 = 3;
Наибольшая сумма констант приведения равна (1 + 3) = 4 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*). Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.
|
i j |
1 |
2 |
3 |
4 |
5 |
di |
|
|
2 |
0 |
M |
0 |
0 |
5 |
0 |
|
|
3 |
1 |
6 |
M |
8 |
M |
1 |
|
|
4 |
16 |
0 |
1 |
M |
8 |
0 |
|
|
5 |
0 |
0 |
1 |
8 |
M |
0 |
|
|
6 |
M |
24 |
18 |
0 |
3 |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
3 |
4 |
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 129 + 4 = 133
Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
2 |
3 |
4 |
di |
|
|
2 |
0 |
M |
0 |
0 |
0 |
|
|
4 |
16 |
0 |
1 |
M |
0 |
|
|
5 |
0 |
0 |
M |
8 |
0 |
|
|
6 |
M |
24 |
18 |
0 |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
0 |
Сумма констант приведения сокращенной матрицы: ?di + ?dj = 0
Нижняя граница подмножества (3,5) равна: H(3,5) = 129 + 0 = 129 ? 133
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 129 Шаг №3. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
1 |
2 |
3 |
4 |
di |
|
|
2 |
0(0) |
M |
0(1) |
0(0) |
0 |
|
|
4 |
16 |
0(1) |
1 |
M |
1 |
|
|
5 |
0(0) |
0(0) |
M |
8 |
0 |
|
|
6 |
M |
24 |
18 |
0(18) |
18 |
|
|
dj |
0 |
0 |
1 |
0 |
0 |
d(2,1) = 0 + 0 = 0; d(2,3) = 0 + 1 = 1; d(2,4) = 0 + 0 = 0; d(4,2) = 1 + 0 = 1; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(6,4) = 18 + 0 = 18;
Наибольшая сумма констант приведения равна (18 + 0) = 18 для ребра (6,4), следовательно, множество разбивается на два подмножества (6,4) и (6*,4*).
Исключение ребра (6,4) проводим путем замены элемента d64 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,4*), в результате получим редуцированную матрицу.
|
i j |
1 |
2 |
3 |
4 |
di |
|
|
2 |
0 |
M |
0 |
0 |
0 |
|
|
4 |
16 |
0 |
1 |
M |
0 |
|
|
5 |
0 |
0 |
M |
8 |
0 |
|
|
6 |
M |
24 |
18 |
M |
18 |
|
|
dj |
0 |
0 |
0 |
0 |
18 |
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 0
Нижняя граница подмножества (6,4) равна:
H(6,4) = 129 + 0 = 129 ? 147
Чтобы исключить подциклы, запретим следующие переходы: (4,1),
Поскольку нижняя граница этого подмножества (6,4) меньше, чем подмножества (6*,4*), то ребро (6,4) включаем в маршрут с новой границей H = 129
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
1 |
2 |
3 |
di |
|
|
2 |
0(0) |
M |
0(1) |
0 |
|
|
4 |
M |
0(1) |
1 |
1 |
|
|
5 |
0(0) |
0(0) |
M |
0 |
|
|
dj |
0 |
0 |
1 |
0 |
d(2,1) = 0 + 0 = 0; d(2,3) = 0 + 1 = 1; d(4,2) = 1 + 0 = 1; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (2,3), следовательно, множество разбивается на два подмножества (2,3) и (2*,3*). редукция матрица маршрут гамильтоновой
Исключение ребра (2,3) проводим путем замены элемента d23 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,3*), в результате получим редуцированную матрицу.
|
i j |
1 |
2 |
3 |
di |
|
|
2 |
0 |
M |
M |
0 |
|
|
4 |
M |
0 |
1 |
0 |
|
|
5 |
0 |
0 |
M |
0 |
|
|
dj |
0 |
0 |
1 |
1 |
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,3*) = 129 + 1 = 130
Включение ребра (2,3) проводится путем исключения всех элементов 2-ой строки и 3-го столбца, в которой элемент d32 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
2 |
di |
|
|
4 |
M |
0 |
0 |
|
|
5 |
0 |
0 |
0 |
|
|
dj |
0 |
0 |
0 |
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 0
Нижняя граница подмножества (2,3) равна:
H(2,3) = 129 + 0 = 129 ? 130
Поскольку нижняя граница этого подмножества (2,3) меньше, чем подмножества (2*,3*), то ребро (2,3) включаем в маршрут с новой границей H = 129
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,2) и (5,1).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,6), (6,4), (4,2), (2,3), (3,5), (5,1), Длина маршрута равна F(Mk) = 129
Задача на нахождение кратчайшего пути
|
Вершина |
Окончательная метка |
Кратчайший путь |
Кратчайшее расстояние L0i |
|
|
X2 |
9;х1 |
х1---х2 |
9 |
|
|
X3 |
8;х4 |
х1---х4---х3 |
8 |
|
|
X4 |
5;х1 |
х1---х4 |
5 |
|
|
X5 |
14;х4 |
х1---х4---х5 |
14 |
|
|
X6 |
13;х2 |
х1---х4---х6 |
13 |
|
|
X7 |
11;х3 |
х1---х4---х3---х7 |
11 |
|
|
X8 |
20;х4 |
х1---х4---х8 |
20 |
|
|
X9 |
13;х7 |
х1---х4---х3---х7---х9 |
13 |
|
|
X10 |
17;х7 |
х1---х4---х3---х7---х10 |
17 |
Размещено на http://www.allbest.ru/
Размещено на Allbest.ru
...Подобные документы
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Алгоритм упорядочивания множества. Определение декартового произведения, его графическая интерпретация. Обратное декартово произведение множеств. Проецирование на оси координат и на координатные плоскости. Область определения и область значений.
лекция [126,5 K], добавлен 18.12.2013Определение длины стороны треугольника, нахождение координаты вектора в заданном трехмерном базисе, решение системы уравнений с помощью обратной матрицы, вычисление предельных значений, исследование функции методами дифференциального исчисления.
контрольная работа [1,1 M], добавлен 04.05.2010Задача о ханойской башне. Задача о разрезании пиццы. Задача Иосифа Флавия. Дискретная математика. Теория возвратных последовательностей - особая глава математики. Исчисление конечных разностей. Последовательности.
дипломная работа [276,8 K], добавлен 08.08.2007Пути наиболее адекватной газификации села, разработка кратчайшего пути прокладывания газопровода. Оптимизация маршрута доставки груза. Определение минимального срока работ по новому направлению предприятия, срок окупаемости и возврата кредита в банк.
контрольная работа [378,6 K], добавлен 10.02.2009Решение системы линейных уравнений по правилу Крамера и с помощью обратной матрицы. Нахождение ранга матрицы. Вычисление определителя с помощью теоремы Лапласа. Исследование на совместимость системы уравнений, нахождение общего решения методом Гауса.
контрольная работа [97,3 K], добавлен 24.05.2009Граф как совокупность объектов со связями между ними. Характеристики ориентированного и смешанного графов. Алгоритм поиска кратчайшего пути между вершинами, алгоритм дейкстры. Алгебраическое построение матрицы смежности, фундаментальных резервов и циклов.
методичка [29,4 M], добавлен 07.06.2009Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
контрольная работа [740,3 K], добавлен 09.03.2015Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Определение понятия множеств Г. Кантора, их примеры и обозначения. Способы задания, включение и равенство множеств, операции над ними: объединение, пересечения, разность, дополнение, их определение и наглядное представление на диаграмме Эйлера-Венна.
реферат [70,9 K], добавлен 11.03.2009Классификация способов нахождения обратной матрицы, полученной в системе MathCAD с помощью миноров и алгебраических дополнений: разбиения ее на клетки и на произведение 2-х треугольных матриц; с помощью модели Гаусса. Вычисление погрешности методов.
лабораторная работа [380,9 K], добавлен 31.10.2012Изучение понятий, действий (сумма, разность, произведение), свойств квадратной матрицы. Определение и признаки ранга матрицы. Анализ методов окаймляющих миноров и преобразований. Расчет системы линейных уравнений согласно методам Крамера и матричному.
реферат [178,9 K], добавлен 01.02.2010Определение матрицы, решение систем уравнений методом Гаусса и по формулам Крамера. Определение параметров треугольника, его графическое построение. Задача приведения уравнения кривой второго порядка к каноническому виду и ее построение.
контрольная работа [126,8 K], добавлен 08.05.2009Математика и информатика. Решение системы линейных алгебраических уравнений методом Крамера. Работа в текстовом редакторе MS WORD. Рисование с помощью графического редактора. Определение вероятности. Построение графика функции с помощью MS Excel.
контрольная работа [443,3 K], добавлен 10.01.2009Алгоритм решения задач по теме "Матрицы". Исследование на совместность системы линейных алгебраических уравнений, пример их решения по правилу Крамера. Определение величины угла при вершине в треугольнике, длины вектора. Исследование сходимости рядов.
контрольная работа [241,6 K], добавлен 19.03.2011Конспект лекций по дискретной математике
курс лекций [73,1 K], добавлен 07.08.2007Множеством именуется некоторая совокупность элементов, объединенных по какому-либо признаку. Над множествами определяют операции, во многом сходные с арифметическими. Операции над множествами интерпретируют геометрически с помощью диаграмм Эйлера-Венна.
реферат [15,8 K], добавлен 03.02.2009Вычисление и построение матрицы алгебраических дополнений. Решение системы линейных уравнений по формулам Крамера, с помощью обратной матрицы и методом Гаусса. Определение главной и проверка обратной матрицы. Аналитическая геометрия на плоскости.
контрольная работа [126,9 K], добавлен 20.04.2016
